Session I.3 - Graph Theory and Combinatorics
Talks
Monday, June 12, 14:00 ~ 15:00
Exponential improvement on diagonal ramsey numbers
Marcelo Campos
University of Oxford, England - This email address is being protected from spambots. You need JavaScript enabled to view it.
The Ramsey Number $R(k)$ is the minimum $n$ such that every red/blue coloring of the edges of $K_n$ contains a monochromatic $K_k$. In this talk I will discuss a recent work where we show that \[R(k)\leq (4-c)^k,\] for some $c \gt 0$. This is the first exponential improvement on the Erd\H{o}s and Szekeres upper bound proved in 1935.
Joint work with Simon Griffiths (PUC - Rio, Brazil), Robert Morris (IMPA, Brazil) and Julian Sahasrabudhe (University of Cambridge, England).
Monday, June 12, 15:00 ~ 15:30
On percolation in locally dependent random graphs
Victor Falgas-Ravry
Umeå University, Sweden - This email address is being protected from spambots. You need JavaScript enabled to view it.
Consider a random subgraph of the square integer lattice $\mathbb{Z}^2$ obtained by including each edge independently at random with probability $p$, and omitting it otherwise. The Harris--Kesten theorem states that if $p\leq 1/2$, then almost surely all connected components in this random graph model are finite, while if $p \gt 1/2$ then almost surely the model percolates and there exists a unique infinite connected component.
But now what if we introduced some local dependencies between the edges? More precisely, suppose each edge still has a probability $p$ of being included in our random subgraph, but its state (present/absent) may depend on the states of nearby edges. To what extent can we exploit such local dependencies to delay the emergence of an infinite component?
In this talk I will discuss this question, which first arose in work of Balister, Bollobás and Walters in 2005, as well as some recent progress around it.
Joint work with A. Nicholas Day (Umeå University, Sweden), Robert Hancock (Heidelberg Universität, Germany) and Vincent Pfenninger (University of Birmingham, UK).
Monday, June 12, 15:30 ~ 16:00
Minimum degree edge-disjoint Hamilton cycles in random directed graphs
Adva Mond
Cambridge University, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
At most how many edge-disjoint Hamilton cycles does a given directed graph contain? A trivial upper bound is the minimum between the minimum out- and in-degrees. We show that a typical random directed graph $D(n,p)$ contains precisely this many edge-disjoint Hamilton cycles, given that $p \gt = (\log^C n)/n$ where $C$ is a fixed integer, which is optimal up to a factor of $\operatorname{polylog} n$. Our proof provides a randomised algorithm to generate the cycles and uses a (relatively) recent "online sprinkling" idea, as was introduced by Ferber and Vu, to generate $D(n,p)$, allowing us to control some key properties of the graph.
Joint work with Asaf Ferber (University of California, Irvine) and Kaarel Haenni (Caltech).
Monday, June 12, 16:30 ~ 17:30
Flag Algebras and Weighted Turán Theorems
Bernard Lidický
Iowa State University, United States - This email address is being protected from spambots. You need JavaScript enabled to view it.
We study extensions of Turán Theorem in edge-weighted settings. A particular case of interest is when constraints on the weight of an edge come from the order of the largest clique containing it. These problems are motivated by Ramsey-Turán type problems. Using these results, we prove several new upper bounds on the Ramsey-Turán density of cliques. The talk will include an introduction to flag algebras that is one of the techniques useful for these type of problems.
Joint work with József Balogh (University of Illinois, USA) and Domagoj Bradač (ETH, Switzerland).
Monday, June 12, 17:30 ~ 18:00
New Ramsey Multiplicity Bounds and Search Heuristics
Olaf Parczyk
FU Berlin, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
We study two related problems concerning the number of monochromatic cliques in two-colorings of the complete graph that go back to questions of Erdős. Most notably, we provide the fist substantial improvement on the 25-year-old upper bounds of Thomason on the Ramsey multiplicity of $K_4$ and $K_5$ and we settle the minimum number of independent sets of size $4$ in graphs with clique number at most $4$. Motivated by the elusiveness of the symmetric Ramsey multiplicity problem, we also introduce an off-diagonal variant and obtain tight results when counting monochromatic $K_4$ or $K_5$ in only one of the colors and triangles in the other. The extremal constructions for each problem turn out to be blow-ups of a finite graph and were found through search heuristics. They are complemented by lower bounds and stability results established using Flag Algebras, resulting in a fully computer-assisted approach. More broadly, these problems lead us to the study of the region of possible pairs of clique and independent set densities that can be realized as the limit of some sequence of graphs.
Joint work with Sebastian Pokutta (ZIB Berlin and TU Berlin), Christoph Spiegel (ZIB Berlin) and Tibor Szabó (FU Berlin).
Monday, June 12, 18:00 ~ 18:30
The total domination game
Leo Versteegen
University of Cambridge, UK - This email address is being protected from spambots. You need JavaScript enabled to view it.
The total domination game is a game played on a graph $G$ by 2 players, Dominator and Staller, who alternate in selecting vertices until each vertex in the graph $G$ has a neighbor in the set of selected vertices. Dominator's aim is to arrive at this state in as few moves as possible, while Staller wants to achieve the opposite. Henning, Klavžar, and Rall conjectured that if $G$ has $n$ vertices, then Dominator has a strategy to finish the game on $G$ within at most $3n/4$ moves. In this talk, I will sketch a proof of this conjecture, highlighting its use of linear programming.
Joint work with Julien Portier (University of Cambridge).
Tuesday, June 13, 14:00 ~ 15:00
Nearly all k-SAT functions are unate
Jozsef Balogh
University of Illinois, United States - This email address is being protected from spambots. You need JavaScript enabled to view it.
Abstract: We prove that 1-o(1) fraction of all k-SAT functions on n Boolean variables are unate (i.e., monotone after first negating some variables), for any fixed positive integer k and as n tends to infinity. This resolves a conjecture by Bollobas, Brightwell, and Leader. The proof uses among others the container method and the method of (computer-free) flag algebras.
Joint work with Dingding Dong (Harvard), Bernard Lidicky (Iowa State University), Nitya Mani (MIT) and Yufei Zhao (MIT).
Tuesday, June 13, 15:00 ~ 15:30
6th diagonal Ramsey number is at most 147
Jan Volec
Czech Technical University in Prague, Czeh Republic - This email address is being protected from spambots. You need JavaScript enabled to view it.
The diagonal Ramsey number $R(k)$ is the smallest order of a complete graph such that any $2$-coloring of its edges contain a monchromatic complete subgraph of order $k$. It is well known that \[a \cdot k 2^{k/2} \lt R(k) \lt (4-b)^k\] for some absolute constants $a \gt 0$ and $b \gt 0$. On the other extreme, we know that $R(3)=6$ and $R(4)=18$, but already the exact value of $R(5)$ is not known. Determining the exact value of $R(k)$ for small values of $k\ge5$ is a challenging problem, and a well known quote of Erdős says that if aliens invade the Earth and demand within a year the exact value of $R(6)$, then we should rather attempt to destroy the aliens than determine $R(6)$. In this talk, we use the flag algebra method to show $R(6)$ is at most $147$ improving on the previous upper bound $R(6) \le 161$.
Joint work with Sergey Norin (McGill University) and Jeremie Turcotte (McGill University).
Tuesday, June 13, 15:30 ~ 16:00
Forcing Generalized Quasirandom Graphs Efficiently
Andrzej Grzesik
Jagiellonian University, Poland - This email address is being protected from spambots. You need JavaScript enabled to view it.
The classical result on quasirandom graphs states that a sequence of graphs is quasirandom with density $p$ if and only if the homomorphism densities of the edge and the 4-cycle in this sequence converge to their expected densities in the random graph with density $p$. Shortly speaking, the structure of quasirandom graphs is forced by homomorphism densities of graphs with at most 4 vertices. We will consider analogous concept for generalized quasirandom graphs whose vertex set consists of $q$ parts (of not necessarily the same sizes) with edges within each part and between each pair of parts distributed quasirandomly. Such graphs correspond to the stochastic block model studied in statistics and network science.
We will show that the structure of generalized quasirandom graphs with $q\ge 2$ parts is forced by homomorphism densities of graphs with at most $4q^2-q$ vertices. This improves earlier bounds of orders $q^q$ by Lovász and Sós and $q^8$ by Lovász. Additionally, we will show that if vertices in distinct parts have distinct degrees, then $2q+1$ vertices suffice, which improves the bound of $8q-4$ due to Spencer.
Joint work with Daniel Král’ (Masaryk University, Czech Republic) and Oleg Pikhurko (University of Warwick, United Kingdom).
Tuesday, June 13, 16:30 ~ 17:00
Common linear patterns are rare
Nina Kamčev
University of Zagreb, Croatia - This email address is being protected from spambots. You need JavaScript enabled to view it.
Several classical results in Ramsey theory (including famous theorems of Schur, van der Waerden, Rado) deal with finding monochromatic linear patterns in two-colourings of the integers. Our topic will be quantitative extensions of such results. A linear system $L$ over $\mathbb{F}_q$ is common if the number of monochromatic solutions to $L=0$ in any two-colouring of $\mathbb{F}_q^n$ is asymptotically at least the expected number of monochromatic solutions in a random two-colouring of $\mathbb{F}_q^n$. Motivated by existing results for specific systems (such as Schur triples and arithmetic progressions), as well as extensive research on common and Sidorenko graphs, the systematic study of common systems of linear equations was recently initiated by Saad and Wolf. Fox, Pham and Zhao characterised common linear equations.
I will talk about recent progress towards a classification of common systems of two or more linear equations. In particular, any system containing a four-term arithmetic progression is uncommon. This follows from a more general result which allows us to deduce the uncommonness of a general system from certain properties of one- or two-equation subsystems.
Joint work with Anita Liebenau (UNSW Sydney, Australia) and Natasha Morrison (University of Victoria, Canada).
Tuesday, June 13, 17:00 ~ 17:30
Towards flag algebras in additive combinatorics
Christoph Spiegel
Zuse Institute Berlin, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
We study an analogue of the Ramsey multiplicity problem for additive structures, in particular establishing the minimum number of monochromatic $3$-APs in 3-colorings of $\mathbb{F}_3^n$ as well as obtaining the first non-trivial lower bound for the minimum number of monochromatic $4$-APs in 2-colorings of $\mathbb{F}_5^n$. The former parallels results by Cumings et al (2013) in extremal graph theory and the latter improves upon results of Saad and Wolf (2017) The lower bounds are notably obtained by extending the flag algebra calculus of Razborov (2007) to additive structures in vector spaces over finite fields.
This work is available on arXiv: https://arxiv.org/abs/2304.00400
Joint work with Juanjo Rué (Universitat Politècnica de Catalunya and Centre de Recerca Matemàtica, Spain).
Tuesday, June 13, 17:30 ~ 18:30
Graph classes and their Asymptotic Dimension
Marthe Bonamy
CNRS, Université de Bordeaux, France - This email address is being protected from spambots. You need JavaScript enabled to view it.
Introduced in 1993 by Gromov in the context of geometric group theory, the asymptotic dimension of a graph class measures how much ``contact'' is necessary between balls of ``bounded'' diameter covering a graph in that class. This concept has connections with clustered coloring or weak diameter network decompositions. While it seems surprisingly fundamental, much remains unknown about this parameter and it displays intriguing behaviours. We will provide a gentle exposition to the area: from the state of the art to the main tools and questions, including some answers. We will introduce and discuss minors in graphs and related concepts.
Wednesday, June 14, 14:00 ~ 14:30
Reconstructing 3D cube complexes from boundary distances
Jane Tan
University of Oxford, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
Given a quadrangulation of a disc, suppose we know all the pairwise distances (measured by the graph metric) between vertices on the boundary of the disc. Somewhat surprisingly, a result of Haslegrave states that this is enough information to recover the whole interior structure of the quadrangulation when all internal vertex degrees are at least 4, providing a discrete analogue to boundary rigidity results from Riemannian geometry. In this talk, we look at a generalisation of this result to 3 dimensions, where we show that it is possible to reconstruct cube complexes that are homeomorphic to a ball from the pairwise distances between all points on the boundary sphere as long as a certain curvature condition holds. We’ll also discuss some plausible variants that turn out to be false, and generalisations that should be true.
Joint work with John Haslegrave (University of Oxford), Alex Scott (University of Oxford) and Youri Tamitegama (University of Oxford).
Wednesday, June 14, 14:30 ~ 15:00
The 4-color Ramsey Multiplicity of Triangles
Aldo Kiem
Zuse Institute Berlin and TU Berlin, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
In 1959 Goodman established that asymptotically, in any two-edge-coloring of the complete graph, at least a quarter of all triangles must be monochromatic. This initiated the much studied Ramsey Multiplicity Problem and was extended in 2013 by Cummings et al. to three-edge-colorings. In this talk, we will extend this results to triangles in four-edge-colorings and explore the computational challenges of scaling up flag-algebra based proofs.
Joint work with Sebastian Pokutta (Zuse Institute Berlin and TU Berlin, Germany) and Christoph Spiegel (Zuse Institute Berlin, Germany).
Wednesday, June 14, 15:30 ~ 16:00
The fragmentation technique on the ranks of tensors and its applications.
Thomas Karam
University of Oxford, United Kingdom - This email address is being protected from spambots. You need JavaScript enabled to view it.
The notion of rank on matrices has been extended in several ways to notions of rank on higher-dimensional tensors. Well-known among these generalisations are in particular the tensor rank, the slice rank, and the partition rank. The most relevant notion of rank heavily depends on one's motivation and context, and in particular no notion of rank is viewed as a canonical generalisation of matrix rank. However, the definitions of many of them (and in particular the three which we have previously mentioned) can be unified, as follows. For $d \ge 2$ an integer and $\mathrm{R}$ a non-empty set of partitions of $[d]$ we say that an order-$d$ tensor $T$ has $\mathrm{R}$-rank at most $1$ if we can write the entries of $T$ as a product of functions \[T(x_1, \dots, x_d) = \prod_{I \in P} a_I(x_i: i \in I)\] for some partition $P \in \mathrm{R}$. We then define the $\mathrm{R}$-rank of $T$ as the smallest nonnegative integer $k$ such that we can write $T$ as a sum of $k$ tensors with $\mathrm{R}$-rank at most $1$. For instance, the tensor rank corresponds to the case where $\mathrm{R}$ contains only the discrete partition of $[d]$, whereas the partition rank allows $\mathrm{R}$ to contain all bipartitions of $[d]$.
Rather than studying any of these notions of rank individually, we will heavily involve the relations between them. We will focus on and answer the following question: given positive integers $d$,$s$ and some sets of partitions $\mathrm{R}_1, \dots, \mathrm{R}_s$ of $[d]$, for which sets $\mathrm{R}$ of partitions of $[d]$ is it true that if an order-$d$ tensor has bounded $\mathrm{R}_i$-rank for each $i=1,\dots,s$, then it must have bounded $\mathrm{R}$-rank ? Settling the case $s=1$ will involve making some progress on a related question of Naslund. Then, in the case $s=2$ (which suffices to conclude for all $s$) the converse implication will involve its own difficulties.
In both parts, the central tool involved will be a fragmentation result allowing us to pass from a statement that the $\mathrm{R}$-rank of a tensor $T$ is bounded for some set $\mathrm{R}$ to a statement that the $\mathrm{R}'$-rank of $T$ is bounded, for some set $\mathrm{R}'$ corresponding to a notion of rank which is finer than that of $\mathrm{R}$, under the assumption that in some direction, all slices of $T$ with some fixed lower dimension than $d$ have bounded partition rank. For instance, it will say that if an order-$3$ tensor $T$ is such that all its order-$2$ slices have bounded rank, then it is equivalent to say that its tensor rank and slice rank of $T$ are bounded.
Wednesday, June 14, 16:30 ~ 17:30
A SAT Approach to the Hadwiger-Nelson Problem
Marijn Heule
Carnegie Mellon University, United States - This email address is being protected from spambots. You need JavaScript enabled to view it.
Progress in satisfiability (SAT) solving has made it possible to answer long-standing open questions in mathematics. In this talk, we apply SAT techniques to the Hadwiger-Nelson problem, also known as the chromatic number of the plane. We will highlight the effectiveness of SAT to reduce the size of unit-distance graphs while preserving the chromatic number. The presented techniques were able to produce a 5-chromatic unit-distance graph with 510 vertices, which is the smallest certificate for the current lower bound of the Hadwiger-Nelson problem. We will also present a SAT-based approach to improve upper-bound results on unit-distance strips. Finally, we will discuss the challenges to increasing the lower bound of the chromatic number of the plane to 6 using automated reasoning.
Posters
A polynomial-time algorithm to find a minimal word representing a tree permutationally
Khyodeno Mozhui
Indian Institute of Technology Guwahati, India - This email address is being protected from spambots. You need JavaScript enabled to view it.
A word-representable graph is a simple graph $G$ that can be represented by a word $w$ over its vertices such that any two vertices are adjacent in $G$ if and only if they alternate in $w$. The class of comparability graphs, i.e., the graphs which admit a transitive orientation, play a vital role in the theory of word-representable graphs. The class of comparability graphs is precisely the class of graphs that can be represented by a concatenation of permutations of their vertices. The minimum number of such permutations of vertices of a comparability graph is its permutation-representation number. Finding the permutation-representation number of a comparability graph is NP-hard. Hence, finding the permutation-representation number of certain special classes of comparability graphs is of interest in the literature. The permutation-representation number of bipartite graphs is an open problem. In this work, we study the permutation-representation number of a special class of bipartite graphs, viz. trees. In this connection, we devise a polynomial-time algorithm to construct a minimal word that represents a given tree permutationally. Accordingly, we provide the permutation-representation number of trees.
Joint work with K. V. Krishna (Indian Institute of Technology Guwahati, India).
Sorting Signed Permutations by Tandem Duplication Random Loss and Inverse Tandem Duplication Random Loss
Bruno J. Schmidt
Max Planck Institute for Mathematics in the Sciences, Leipzig, Germany - This email address is being protected from spambots. You need JavaScript enabled to view it.
Tandem duplication random loss (TDRL) and inverse tandem duplication random loss (iTDRL) are mechanisms of mitochondrial genome rearrangement that can be modeled as simple operations on signed permutations. Informally, they comprise the duplication of a subsequence of a permutation, where in the case of iTDRL the copy is inserted with inverted order and signs. In the second step, one copy of each duplicate element is removed, such that the result is again a signed permutation. The TDRL/iTDRL sorting problem consists in finding the minimal number of TDRL or iTDRL operations necessary to convert the identity permutation $\iota$ into a given permutation $\pi$. We introduce a simple signature, called the misc-encoding, of permutation $\pi$. This construction is used to design an $\mathcal{O}(n\log{}n)$ algorithm to solve the TDRL/iTDRL sorting problem
Joint work with Tom Hartmann (Bioinformatics Group, Department of Computer Science &, Interdisciplinary Center for Bioinformatics, Leipzig University, Leipzig, Germany), Peter F. Stadler (Bioinformatics Group, Department of Computer Science & Interdisciplinary Center for Bioinformatics Leipzig University, Leipzig, Germany; Max Planck Institute for Mathematics in the, Sciences, Leipzig, Germany; Center for Scalable Data Analytics and Artificial Intelligence, Dresden/Leipzig, Germany; Department of Theoretical Chemistry, University of Vienna, Vienna, Austria; Facultad de Ciencias, Universidad National de Colombia, Bogota, Colombia; Santa and Fe Institute, Santa Fe, NM, USA).
Rainbow Clique Subdivisions
Yan Wang
Shanghai Jiao Tong University, China - This email address is being protected from spambots. You need JavaScript enabled to view it.
In this talk, we show that for any integer $t \ge 2$, every properly edge colored $n$-vertex graph with average degree at least $(\log n)^{2+o(1)}$ contains a rainbow subdivision of a complete graph of size $t$. Note that this bound is within a log factor of the lower bound. This also implies a result on the rainbow Turán number of cycles.
Complete non-ambiguous trees and associated permutations: connections through the Abelian sandpile model
Haoyue Zhu
Xi'an Jiaotong-Liverpool University, China - This email address is being protected from spambots. You need JavaScript enabled to view it.
Complete non-ambiguous trees (CNATs) were originally introduced by Aval et al. (2014) as a special case of tree-like tableaux. We can associate a permutation to a CNAT by keeping only its leaf dots. In recent work, Chen and Ohlig (2022) initiated the first in-depth combinatorial study of this relationship, notably showing that the number of $n$-permutations that are associated with exactly one CNAT is $2^{n−2}$. We extend this work by enumerating permutations associated with exactly $k$ CNATs for various values of $k \gt 1$, via bijective approaches. Our results rely on a connection to the so-called Abelian sandpile model (see Dukes et al., 2019). We also exhibit a new bijection between $(n−1)$-permutations and CNATs whose permutation is the decreasing permutation $n(n−1)\cdots 1$. This bijection maps the left-to-right minima of the permutation to dots on the bottom row of the corresponding CNAT, and descents of the permutation to empty rows of the CNAT.
References\\ Jean-Christophe Aval, Adrien Boussicault, Mathilde Bouvel, and Matteo Silimbani. Combinatorics of non-ambiguous trees. Adv. App. Math., 56:78–108, 2014.\\ Daniel Chen and Sebastian Ohlig. Associated permutations of complete non-ambiguous trees and Zubieta's conjecture, preprint, 2022.\\ Mark Dukes, Thomas Selig, Jason P. Smith, and Einar Steingrimsson. Permutation graphs and the abelian sandpile model, tiered trees and non-ambiguous binary trees. Electron. J. Comb., 26(3):research paper p3.29, 25, 2019.
Joint work with Thomas Selig (Xi'an Jiaotong-Liverpool University, China).