Discrete Mathematics Meeting 2025

The Discrete Mathematics Meeting is a series of joint meetings of research groups from Brno/Leipzig, Graz, ISTA, Passau, and Vienna, centred around probabilistic and extremal combinatorics as well as graph theory.

In the year 2025, the meeting will take place on the 29th and 30th of September at TU Graz. All the scientific program will take place in the seminar room STEG050 (AE06) on the ground floor (EG) of the Mathematics Building located at Steyrergasse 30, A-8010 Graz, on the Neue Technik Campus of TU Graz. There will be a joint dinner at Restaurant Glöcklbräu (Glockenspielplatz 2-3, A-8010 Graz). External participants will stay at Ibis hotel (Waltendorfer Guertel 8, A-8010 Graz).


Speakers


Program

The program will start on Monday, 29 September, around lunchtime and end on Tuesday, 30 September, at lunchtime.

Monday, 29 September
12:00 Lunch TU Mensa
13:00-13:45 Coffee and get-together AE06, TU Graz
13:45-14:00 Welcome and Introduction AE06, TU Graz
14:00-14:35 Matija Bucić:  On Graham's rearrangement conjecture AE06, TU Graz
14:35-15:10 Lina Simbaqueba:  Quasirandom forcing in regular tournaments AE06, TU Graz
15:10-15:40 Coffee break AE06, TU Graz
15:40-16:15 Mihalis Sarantis:  On the number of antichains in $\{0,1,2\}^n$ AE06, TU Graz
16:15-16:50 Aleksandr Grebennikov:  Geometric Littlewood-Offord problems via lattice point counting AE06, TU Graz
17:00-17:30 Open problem session AE06, TU Graz
17:30-17:40 Group photo TU Graz
19:00 Joint dinner Glöcklbräu
Tuesday, 30 September
09:00-09:35 Kalina Petrova:  Packing subdivisions into regular graphs AE06, TU Graz
09:35-10:10 Yangyang Cheng:  Equitable Coloring and the Chen-Lih-Wu conjecture AE06, TU Graz
10:10-10:40 Coffee break AE06, TU Graz
10:40-11:15 James Davies:  Riemannian planes and string graphs are quasi-isometric to planar graphs AE06, TU Graz
11:15-11:50 Ronen Wdowinski:  Hall's theorem for reconfigurations via colorful simplices AE06, TU Graz
11:50-12:25 Lyuben Lichev:  The power of choice: a geometric perspective AE06, TU Graz
12:30 Lunch TU Mensa
14:00 Optional walk up Schlossberg City Center

Abstracts (in the order of talks)

Matija Bucić: On Graham's rearrangement conjecture

A well-known question in combinatorial group theory, going back to a conjecture of Graham from 1971, asks if given a subset $S$ of some group $(G,+)$, it is possible to order $S$ as $s_1, s_2,...,s_t$ so that the partial sums $s_1 + s_2+ ... + s_j$ are all distinct for each $j < t$. We discuss recent progress on this question based on a synergy between ideas from additive combinatorics and graph theory. Based on a joint work with Benjamin Bedert, Alp Muyesser, Noah Kravitz, and Richard Montgomery.

Lina Simbaqueba: Quasirandom forcing in regular tournaments

A sequence of tournaments is said to be quasirandom if it behaves as a sequence of random tournaments would. In 1991, Chung, Graham, and Wilson provided a list of equivalent properties that any sequence of random tournaments satisfies with high probability. We say that a tournament H forces quasirandomness if every sequence that asymptotically has the expected number of copies of H is quasirandom. Nevertheless, it was shown that almost only transitive tournaments are quasirandom forcing. We then modify the definition of quasirandom forcing by considering only sequences of nearly regular tournaments and characterize all tournaments on at most five vertices that force quasirandomness in this new setting.

Mihalis Sarantis: On the number of antichains in $\{0,1,2\}^n$

In 1897 Dedekind posed the question of enumerating the number of antichains of the Boolean lattice. This was answered, almost a century later by Korshunov, and Sapozhenko simplified his proof by using what is now known as the graph container method. Sapozhenko asked whether the same approach can be applied to the product of chains of 3 elements. Counting the antichains of $\{0,1,2\}^n$ was also asked independently by Noel, Scott and Sudakov, who obtained the asymptotics on the logarithmic scale. In our work, we provide sharp asymptotics for this number. As a tool, we prove a container type lemma to bound the number of expanding sets in a class of irregular graphs and isoperimetric estimates for generalizations of the Boolean lattice that may be of independent interest. This is joint work with Matthew Jenssen and Jinyoung Park.

Aleksandr Grebennikov: Geometric Littlewood-Offord problems via lattice point counting

Consider nonzero vectors $a_{1},\dots,a_{n}\in \mathbb{C}^{k}$, independent Rademacher random variables $\xi_{1},\dots,\xi_{n}$, and a set $S\subseteq \mathbb{C}^{k}$. What upper bounds can we prove on the probability that the random sum $\xi_{1}a_{1}+\dots+\xi_{n}a_{n}$ lies in $S$? We develop a general framework that allows us to reduce problems of this type to counting lattice points in $S$. We apply this framework with known results from diophantine geometry to prove various bounds when $S$ is a set of points in convex position, an algebraic variety, or a semialgebraic set. In particular, this resolves conjectures of Fox-Kwan-Spink and Kwan-Sauermann. We also obtain some corollaries for the polynomial Littlewood-Offord problem, for polynomials that have bounded Chow rank (i.e., can be written as a polynomial of a bounded number of linear forms). For example, one of our results confirms a conjecture of Nguyen and Vu in the special case of polynomials with bounded Chow rank: if a bounded-degree polynomial $F\in\mathbb{C}[x_{1},\dots,x_{n}]$ has bounded Chow rank and ''robustly depends on at least $b$ of its variables'', then $\mathbb{P}[F(\xi_{1},\dots,\xi_{n})=0] = O(1/\sqrt{b})$. We also prove significantly stronger bounds when $F$ is ''robustly irreducible'', towards a conjecture of Costello. Based on joint work with Matthew Kwan.

Kalina Petrova: Packing subdivisions into regular graphs

We show that, for any graph $F$ and $\eta>0$, there exists a $d_0=d_0(F,\eta)$ such that every $n$-vertex $d$-regular graph with $d \geq d_0$ has a collection of vertex-disjoint $F$-subdivisions covering at least $(1-\eta)n$ vertices. This verifies a conjecture of Verstra\"ete from 2002 and improves a recent result of Letzter, Methuku and Sudakov which additionally required $d$ to be at least polylogarithmic in $n$. This is joint work with Richard Montgomery, Arjun Ranganathan, and Jane Tan.

Yangyang Cheng: Equitable Coloring and the Chen-Lih-Wu conjecture

An equitable coloring of a graph is a proper vertex coloring where the sizes of any two different color classes do not differ by more than one. Chen, Lih, and Wu conjectured that for $k\geq 3$, the only connected graphs with maximum degree at most $k$ that are not equitably $k$-colorable are $K_{k,k}$ (for odd $k$) and $K_{k+1}$. Kierstead and Kostochka strengthened it to an ore-type version and proposed the following conjecture. Let $k\geq 3$. If $G$ is an $n$-vertex graph satisfying $d(x) + d(y)\leq 2k$ for every edge $xy$ and $G$ has no equitable $k$-coloring, then $G$ contains either $K_{k+1}$ or $K_{m,2k-m}$ for some odd $m$. We prove that for any constant $c>0$ and any sufficiently large $n\ge n_0(c)$, the above conjecture holds for every $k\geq cn$. This talk is based on joint work with Zhenyu Li, Wanting Sun and Guanghui Wang.

James Davies: Riemannian planes and string graphs are quasi-isometric to planar graphs

It is a folklore result that for every complete Riemannian surface S there is a countable locally finite graph G with positive real edge lengths that has an embedding in S so that the embedding is also a quasi-isometry between G and S. The condition that the edge lengths are positive reals and not just uniformly equal to 1 is necessary. We construct a complete Riemannian surface in which no such embedding of a graph that has edge lengths uniformly equal to 1 exists. On the other hand, we show that embeddings of such graphs do exist for complete Riemannian surfaces with bounded Euler genus. This is one of the applications of a more technical result which is also used to show for example that string graphs are quasi-isometric to planar graphs. The talk assumes no knowledge of Riemannian geometry.

Ronen Wdowinski: Hall's theorem for reconfigurations via colorful simplices

In combinatorial reconfigurations, one seeks to determine for a given problem when one feasible solution can be transformed into another feasible solution in step-by-step fashion while always maintaining a feasible solution. Such problems are usually framed in terms of a reconfiguration graph, and the goal is often to show that this graph is connected. We give a topological approach for showing that reconfiguration graphs are connected in various natural combinatorial settings. Our method is based on a variation of a topological Hall-type theorem due to Aharoni, Haxell, and Meshulam, on colorful simplices in vertex-colored simplicial complexes. We describe applications to some reconfiguration problems in graph theory and discrete geometry.

Lyuben Lichev: The power of choice: a geometric perspective

We will consider a random geometric graph process where random points are embedded consecutively in the d-dimensional unit torus and every two points at distance at most r form an edge. First, we will explore analogues of well-known hitting time results for connectivity and Hamiltonicity in the Erdős–Rényi graph process when r approaches 0. The main focus of the talk will fall on a discussion of a geometric version of the power of choice where, at each step, an agent is shown two independent random points and is allowed to choose one of them. Related sharp threshold and hitting time results will be considered in an online and an offline version of the choice process. Joint work with Dawid Ignasiak.


Local organisers


For any questions concerning the Discrete Mathematics Meeting 2025 please get in touch with Anna Geisler via

geisler [at] math [dot] tugraz [dot] at.


This is an associated event of the SFB "Discrete random structures: enumeration and scaling limits" and is supported in part by Austrian Science Fund (FWF) [10.55776/F1002] and NAWI Graz.