Seminar iz diskretne matematike

Vodji seminarja: Boštjan Brešar in Sandi Klavžar
Predavanja potekajo ob ponedeljkih ob 15:15 v seminarski sobi P1 (Gosposvetska cesta 84, v 4. nadstropju).

Bodoča predavanja

Minula predavanja

Klasifikacija 2-prekrižno kritičnih grafov

20. 01. 2014

Predavatelj: Drago Bokal

It is very well-known that there are precisely two minimal non-planar
graphs: K_5 and K_{3,3} (degree 2 vertices being irrelevant in this
context). In the language of crossing numbers, these are the only
1-crossing-critical graphs: they each have crossing number at least one,
and every proper subgraph has crossing number less than one. In 1987,
Kochol exhibited an infi nite family of 3-connected, simple
2-crossing-critical graphs. Recently, a complete characterization of
2-crossing-critical graphs was finalized by Richter, Salazar, Oporowski,
and Bokal. An overview of this characterization will be presented in the
talk. In particular, we will introduce the concepts and some shorter
arguments needed in the proof of the following:

Let G be a 2-crossing-critical graph.
1. Then G has minimum degree at least two and is a subdivision of a
2-crossing-critical graph with minimum degree at least three.
Moreover, suppose G has minimum degree at least three. Then:
2. if G is 3-connected, then either G has a subdivision of V_{10} and a
very particular tile structure or has at most 3 million vertices; or
3. G is not 3-connected and is one of 49 particular examples; or
4. G is 2- but not 3-connected and is obtained from a 3-connected
example by replacing digons with digonal paths.

Symmetry breaking in infinite graphs

02. 12. 2013

Predavatelj: Wilfried Imrich (Montanuniversitaet, Leoben, Avstrija)

A coloring of the vertices of a graph G is called distinguishing if the stabilizer
of the coloring in the automorphism group of G is trivial. Tom Tucker
conjectured that, if every automorphim of a connected, locally finite graph moves
infinitely many vertices, then there exists a distinguishing 2-coloring, that is, a coloring
using only two colors. This is known as the infinite Motion Conjecture.
Despite many
intriguing partial results, it is still open in general.

This conjecture, its generalizations to uncountable graphs, to groups
acting on structures, and to endomorphims of countable and uncountable graphs and structures,
has become an inspiring topic and spawned numerous papers.

In this talk I will present generalizations of the Infinite Motion
Conjecture, to
random colorings on countable graphs, and other generalizations to
uncountable graphs. I will also shortly describe some of the methods used to obtain solutions
for various classes of graphs, this includes the permutation toplogy on countable sets and related topological spaces, in particular Polish spaces.

Grünberg-Kegel graphs and their applications

07. 10. 2013

Predavatelj: Anatolij Kondratjev (Ruska akademija znanosti, Jekaterinburg, Rusija)

Abstract: The prime graph of a group H, also known as the Gruenberg-Kegel graph GK(H), after Karl Gruenberg (1928-2007) and Otto Kegel (1934-), has as its vertex set all the prime divisors of the order |H| and two distinct vertices p, q are adjacent exactly when the group H contains an element of order pq. A survey of the main properties of Gruenberg-Kegel graphs will be given and some their applications to the finite group theory will be presented.
Vsi seminarji
Accessibility