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

Polluted modified bootstrap percolation

02. 12. 2024

Predavatelj: Janko Gravner (UC Davis, ZDA)

Povzetek: In the polluted modified bootstrap percolation model on d-dimensional lattice, sites are independently initially occupied with probability p or closed with probability q. A site becomes occupied at a subsequent step if it is not closed and has at least one occupied nearest neighbor in each of the d coordinates. The main quantity of interest is final density of occupied sites when p and q are both small. This density is expected to change from high to low as q increases over a critical power of p, possibly with logarithmic corrections. In the two-dimensional case, these logarithmic corrections are indeed present in the modified rule, by contrast with the standard rule.

This is joint work with A. Holroyd, S. Lee, and D. Sivakoff.

Portier and Versteegen’s proof of the 3/4-conjecture

16. 01. 2023

Predavateljica: Vesna Iršič

Povzetek: Recently, Portier and Versteegen proved the 3/4-conjecture for the total domination game which states that for every graph $G$ without isolated vertices or edges, the game total domination number is at most $\frac{3}{4} |V(G)|$. In this talk, the outline of the proof will be presented.

Asymmetrizing infinite trees

17. 10. 2022

Predavatelj: Wilfried Imrich (about joint work with Florian Lehner, Rafal Kalinowski, Monika Pilsniak and Marcin Stawiski)

Povzetek: The talk is a continuation of the seminar talk of November 12, 2018 about automorphism breaking of countable trees. One says a tree, or more generally a graph,  is asymmetrizable if there exists a 2-coloring of its vertices that is only preserved by the identity automorphism. The talk outlines a proof that each infinite tree whose degrees are bounded by 2^m, where m is an arbitrary infinite cardinal, is asymmetrizable if all non-identity automorphisms move at least m vertices.

The talk begins with a few remarks about infinite cardinals, successor cardinals, regular and singular cardinals, the Generalized Continuum Hypothesis, results of Babai, Sabidussi and Polat and then presents the main result.

Vsi seminarji
Accessibility