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

Krepki vozliščni razpon dreves (Strong vertex span of trees)

20. 04. 2026

Predavatelj: Andrej Taranenko

Abstract: The strong vertex (edge) span of a given graph $G$ is the maximum distance that two players can maintain at all times while visiting all vertices (edges) of $G$ and moving either to an adjacent vertex or staying in the current position independently of each other. We introduce the notions of switching walks and triod size of a tree, which are used to determine the strong vertex and the strong edge span of an arbitrary tree. The obtained results ar​e used in an algorithm that computes the strong vertex (edge) span of the input tree in linear time.

Partitioning dodecahedral spaces: a combinatorial (and pictorial) excursion

06. 10. 2025

Predavatelj: Andrés David Santamaría-Galvis (UP FAMNIT)

Povzetek: In this talk, we take a combinatorial journey through three closely related 3-manifolds: real projective 3-dimensional space, the Poincaré homology 3-sphere, and the Weber-Seifert space. Each of these spaces emerges from quotienting on the dodecahedron’s geometry. We explore triangulations of these manifolds, focusing on their partitionability—a combinatorial property with deep topological implications.  The techniques we introduce are conceptually simple yet broadly usable, offering tools for constructing partitionable triangulations of more complex spaces. This presentation emphasizes the interplay between topology and combinatorics, illustrated through some visual examples designed to spark intuition and insight.

Joint work with Russ Woodroofe

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.

Vsi seminarji
Accessibility