Xichao Shu: Four-coloring Eulerian triangulations of the torus

Hutchinson, Richter, and Seymour showed that every Eulerian triangulation of an orientable surface with a sufficiently high representativity is 4-colorable. We give an explicit bound on the representativity in the case of the torus by proving that every Eulerian triangulation of the torus with representativity at least 10 is 4-colorable. We also observe that the bound on the representativity cannot be decreased to less than 8 as there exists a non-4-colorable Eulerian triangulation of the torus with representativity 7.

This is joint work with Marcin Barański, Daniel Kráľ, and Ander Lamaison.

Vincent Pfenninger: The Law of the circumference of sparse binomial random graphs

In this talk, we will introduce a new method to prove central limit theorems in sparse binomial random graphs. In particular, our method allows us to show that the circumference of G(n,p) satisfies a central limit theorem when p = c/n for each constant c >= 20.

This is joint work with Michael Anastos, Joshua Erde, and Mihyun Kang.

Yiting Wang: Counting perfect matchings in Dirac k-uniform hypergraphs

A celebrated theorem of Cuckler and Kahn states that the number of perfect matchings in a Dirac graph is tightly controlled up to exp(o(n)) by a quantity named graph entropy. We extend this result to k-uniform Dirac hypergraphs.

A k-uniform hypergraph is called d-Dirac if its minimum d-degree exceeds the d-Dirac threshold by a constant factor. For all 1 ≤ d ≤ k − 1, we prove the number of perfect matchings in a d-Dirac k-uniform hypergraph is tightly controlled up to exp(o(n)) by the (hyper)graph entropy. This result answers a question raised by Glock, Gould, Joos, Kühn and Osthus on whether the entropy bound can be extended to hypergraphs. As an application, we show the number of perfect matchings in a d-Dirac k-uniform hypergraph matches the expected number of perfect matchings in a random hypergraph with corresponding density up to exp(o(n)) for all d ≥ k/2. Previously this was only known for d = k-1.

This is a joint work with Matthew Kwan and Roodabeh Safavi.

Kalina Petrova: The Hamilton space of pseudorandom graphs

We show that if n is odd and p >= C\log(n)/n, then with high probability the Hamilton cycles in the binomial random graph G(n,p) span its cycle space. More generally, we show this holds for a class of graphs satisfying certain natural pseudorandom properties. The proof is based on a novel idea of parity-switchers, which can be thought of as analogues of absorbers in the context of cycle spaces. As another application of our method, we show that Hamilton cycles in a near-Dirac graph G, that is, a graph G with odd n vertices and minimum degree n/2 + C for a sufficiently large constant C, span its cycle space.

This is joint work with Micha Christoph and Rajko Nenadov.

Amedeo Sgueglia: Spanning spheres in Dirac hypergraphs

We provide a topological extension of Dirac’s theorem and show that a k-uniform hypergraph H on n vertices has a spanning (k −1)-dimensional sphere, provided that H has no isolated vertices and each set of k-1 vertices supported by an edge is in fact supported by at least (1/2+o(1))n edges. This asymptotically confirms a conjecture of Georgakopoulos, Haslegrave, Montgomery and Narayanan.

This is joint work with Freddie Illingworth, Richard Lang, Alp Muyesser and Olaf Parczyk

Dominik Schmid: Building spanning graphs in the semirandom tree process

The semirandom process is a randomized graph process that constructs a graph according to a mixture of random and strategic choices. There has been much recent interest in how the addition of strategic agency can affect the evolution of this process, and in particular, accelerate the time at which certain substructures appear. In this talk, we consider a variant of the semirandom process, introduced by Burova and Lichev, called the semirandom tree process, where in a series of rounds a player (Builder) is offered the edge set of a uniformly chosen tree on n vertices and chooses an edge to keep. We show that for any n-vertex graph H with maximum degree Δ, Builder has a strategy such that with probability tending to one as n tends to infinity, they can construct a copy of H in (1+o_Δ(1))(Δn)/2 rounds of the semirandom tree process, which can be seen to be asymptotically optimal in Δ.

This is joint work with Michael Anastos, Maurício Collares, Joshua Erde, Mihyun Kang, and Gregory Sorkin.

Igor Balla: MaxCut, orthonormal representations, and extension complexity of polytopes

In this talk, we will discuss several extremal problems involving concepts like MaxCut, the Lovász theta function, minimum semidefinite rank, and extension complexity of polytopes. We will show how a bipartite generalization of Alon and Szegedy’s nearly orthogonal vectors implies strong bounds for these problems. Some of the results that will be presented are in joint work with Letzter and Sudakov, or Janzer and Sudakov.

Lyuben Lichev: Explosive appearance of cores and bootstrap percolation on lattices

In many dynamical probabilistic systems exhibiting a sharp threshold, the first time when a particular substructure appears can be pinned down to a single time step at which a simple necessary condition becomes satisfied. In this talk, we will focus on a similar hitting time result. Consider the process where the n^2 vertices of a square 2-dimensional torus appear consecutively in a random order. We will see that the size of the 3-core of the corresponding induced unit-distance graph (that is, the maximum subgraph of minimum degree 3) transitions from 0 to n^2-o(n^2) within a single step. Equivalently, by infecting the vertices of the torus in a random order under 2-neighbour bootstrap percolation, the size of the infected set transitions instantaneously from o(n^2) to n^2. If time allows, we will discuss an approach towards recovering the same phenomenon for a much more general class of bootstrap percolation rules.

The talk is based on a joint work with Ivailo Hartarsky.

For any questions and comments, please reach out to Marek Filakovský or Jan Grebík via email or via phone - the contacts have been shared by e-mail with registered participants.