Raziskovalni matematični seminar - Arhiv
The course is an introduction to the Polya’s theory in order to answer
questions such as:
-Up to isomorphism, how many graphs on n vertices are there?
-Up to rotational symmetry, how many ways can we color the faces of a cube?
-How many necklaces can be formed using 8 beads of 3 different colors?
The mini-course will be self-contained, and will start by reviewing definitions and main results involving group actions and permutation groups. Important results from permutation groups such as orbit-stabilizer theorem, Burnside's theorem and Polya's enumeration theorem will be proved. These theorems will be followed by many examples and interesting applications.
The updated schedule is as follows:
Wednesday, 28.02.2018: 16:00 - 18:30 - Lecture room: Muzejski 1
Thursday, 01.03.2018: 10:00 - 11:30 - Lecture room: FAMNIT - POŠTA
Friday, 02.03.2018: 10:00 - 12:30 - Lecture room: Muzejski 1
Wednesday, 7.3.2018: 16:00 - 18:30 - Lecture room: Muzejski 4
Thursday, 8.3.2018: 9:30 - 11:00 - Lecture room: FAMNIT-VP
Friday, 9.3.2018: 10:00 - 12:30 - Lecture room: Muzejski 1
(Joint work with Roman Nedela)
Bi-Cayley graphs are graphs admitting a semiregular group of automorphisms with two orbits. A notable cubic subclass of bi-Cayley graphs is the so-called generalized Petersen graphs. Castagna and Prins proved in 1972 that all generalized Petersen graphs except for the Petersen graph itself can be properly 3-edge-colored. In this talk, we are going to discuss the extension of this result to all connected cubic bi-Cayley graphs over solvable groups. Our theorem is a bi-Cayley analogue of similar results obtained by Nedela and Škoviera for Cayley graphs any by Potočnik for vertex-transitive graphs.
An automorphism of a graph is said to be even/odd if it acts on the vertex set of the graph as an even/odd permutation. In this talk, I will present the formula for the number of non-isomorphic graphs of order n admitting an odd automorphism, together with some asymptotic estimates. We will then focus on the existence of odd automorphisms in the class of vertex-transitive graphs. A positive integer n is a Cayley number if every vertex-transitive graph of order n is a Cayley graph. By analogy, a positive integer n is said to be a vertex-transitive-odd number (in short, a VTO-number) if every vertex-transitive graph of order n admits an odd automorphism. We will prove that Cayley numbers congruent to 2 modulo 4, cube-free nilpotent Cayley numbers congruent to 3 modulo 4, and numbers of the form 2p, for p a prime, are VTO numbers. At the other extreme, it is possible that the complete graph K_n is the only connected vertex-transitive graph of order n>2 admitting an odd automorphism. We will prove that this happens if and only if n is a Fermat prime.
This is joint work with Klavdija Kutnar and Dragan Marušič.