Raziskovalni matematični seminar - Arhiv

The graph isomorphism problem is a computational problem of deciding whether two given graphs are isomorphic. It’s not known whether the problem can be solved in a polynomial time or it’s an NP- complete. In our lecture we present a well-known Weisfeiller-Leman (WL) algorithm which solves some particular cases of the problem. It will be shown how WL-algorithm yields a special class of colored graphs known as coherent configurations. We’ll show the basic properties of those objects and focus on a special class of them known as association schemes. Association schemes play an important role in algebraic graph theory.

In this PhD thesis we study the isomorphism problem of bi-Cayley graphs and the related question of classifying finite BCI-groups. More precisely, the following questions/problems are considered:

(i) Find effective, sufficient and necessary conditions for the isomorphism of two cyclic bi-Cayley graphs.
(ii) Which groups are 3-BCI-groups?
(iii) Which cubic bi-Cayley graphs are BCI-graphs?
(iv) Which cyclic balanced configurations have the CI-property?
(v) Analytical enumeration of balanced cyclic configurations.

Problem (i) is solved for tetravalent graphs. Problem (ii) is solved for nilpotent groups. We contribute to Problem (iii) by proving that all connected cubic arc-transitive bi-Cayley graphs over abelian groups are BCI-graphs. Regarding Problem (iv), we prove that all cyclic balanced configurations have the CI-property for which the number of points is either a product of two distinct primes, or a prime power. Regarding Problem (v), we derive a close formula for the number of connected cyclic configurations of type (v_3).

The graph isomorphism problem is a computational problem of deciding whether two given graphs are isomorphic. It’s not known whether the problem can be solved in a polynomial time or it’s an NP- complete. In our lecture we present a well-known Weisfeiller-Leman (WL) algorithm which solves some particular cases of the problem. It will be shown how WL-algorithm yields a special class of colored graphs known as coherent configurations. We’ll show the basic properties of those objects and focus on a special class of them known as association schemes. Association schemes play an important role in algebraic graph theory.

DOWNLOAD SLIDES!

The Virtual Element method is a very recent variant of Finite Element Methods, appeared on the scene a couple of years ago. The method could be seen as a combination of Finite Element Methods and Mimetic Finite Differences. In particular it allows, at the same time, the use of very general decompositions of the computational domain (in almost arbitrary polygons or polyhedra), and the use of the (more elegant and more clarifying) Galerkin framework for the analysis and the error estimates. The talk, addressed to a rather general audience of mathematicians, will describe first the general idea of the method on a very simple problem like Poisson problem in 2 dimensions, and then give some very quick hints on various generalizations, including 3D problems, Stokes problem, Kirchhoff plates, variable coefficients, mixed formulations, etc. Much more details could be given, after the lecture, to the interested people. Several papers (both on the basic principles and on further extensions) can be found (and downloaded) on the web page of the speaker: http://www.imati.cnr.it/brezzi/rec_pubbl.html (the newest are at the end).

Lectures will be given by Stephen Wilson throughout the spring semester.

Tentative schedule:

Every Monday, Tuesday and Thursday, starting on Monday, February 16, 2015 and ending on Thursday, June 4, 2015.

Monday:
16:00 - 17:00 FAMNIT-POSTA

Tuesday:
12:00 - 13:00 FAMNIT-MP1

Thursday:
15:00 - 16:00 FAMNIT-MP1

Course overview:

After a brief overview of group actions on sets, we will discuss abstract objects which have relatively large symmetry groups:

Maps:
Rotary, Chiral, Reflexible
Classifications and Families
Automorphism groups of surfaces
Orientable and not
Operators

Polytopes and Maniplexes:
Definitions and relations
Rotary, chiral and reflexible
Orientable and not
Even more operators

Graphs:
Edge-transitivity
Dart-transitive
1/2-arc-transitive
Semisymmetric
Families and sporadic examples

Constructions:
By parameters
From diagrams
from smaller graphs.

Welcome!