European Conference on Combinatorics, Graph Theory and Applications

Foreword

Daniel Král, Jaroslav Nešetřil — Mon, 28 Aug 2023 00:00:00 +0200

On the number of tangencies among 1-intersecting curves

Eyal Ackerman, Balázs Keszegh — Mon, 28 Aug 2023 00:00:00 +0200

Let $\mathcal{C}$ be a set of curves in the plane such that no three curves in $\mathcal{C}$ intersect at a single point and every pair of curves in $\mathcal{C}$ intersect at exactly one point which is either a crossing or a touching point. According to a conjecture of János Pach the number of pairs of curves in $\mathcal{C}$ that touch each other is $O(|\mathcal{C}|)$. We prove this conjecture for $x$-monotone curves.

Partition Universality for Hypergraphs of Bounded Degeneracy and Degree

Peter Allen, Julia Böttcher, Domenico Mergoni Cecchelli — Mon, 28 Aug 2023 00:00:00 +0200

We consider the following question. When is the random $k$-uniform hypergraph $\Gamma=G^{(k)}(N,p)$ likely to be $r$-partition universal for $k$-uniform hypergraphs of bounded degree and degeneracy? That is, for which $p$ can we guarantee asymptotically almost surely that in any $r$-colouring of $E(\Gamma)$ there exists a colour $\chi$ such that in $\Gamma$ there are $\chi$-monochromatic copies of all $k$-uniform hypergraphs of maximum vertex degree $\Delta$, degeneracy at most $D$, and $cN$ vertices for some constant $c=c(D,\Delta)>0$. We show that if $\mu>0$ is fixed, then $p\ge N^{-1/D+\mu}$ suffices for a positive answer if $N$ is large. On the other hand, for $p=o(N^{-1/D})$ we show that $G^{(k)}(N,p)$ is likely not to contain some graphs of maximum degree $\Delta$ and degeneracy $D$ on $cN$ vertices at all. This improves the best upper bounds on the minimum number of edges required for a $k$-uniform hypergraph to be partition universal (even for $k=2$) and also for the size-Ramsey problem for most $k$-uniform hypergraphs of bounded degree and degeneracy.

Expander graphs, strong blocking sets and minimal codes

Noga Alon, Anurag Bishnoi, Shagnik Das, Alessandro Neri — Mon, 28 Aug 2023 00:00:00 +0200

We give a new explicit construction of strong blocking sets in finite projective spaces using expander graphs and asymptotically good linear codes. Using the recently found equivalence between strong blocking sets and linear minimal codes, we give the first explicit construction of $\mathbb{F}_q$-linear minimal codes of length $n$ and dimension $k$ such that $n$ is at most a constant times $q k$. This solves one of the main open problems on minimal codes.

Moderate deviations of triangle counts – the lower tail

José D. Alvarado, Gabriel D. Do Couto, Simon Griffiths — Mon, 28 Aug 2023 00:00:00 +0200

Two recent papers \cite{GGS} and \cite{NRS22} study the lower tail of triangle count deviations in random graphs $G(n,m)$ with positive density $t:=m/\binom{n}{2}\in (0,1)$. Let us write $D_{\triangle}(G)$ for the deviation of the triangle count from its mean. Results of \cite{GGS} and \cite{NRS22} determine the order of magnitude of the log probability $\log(\mathbb{P}(D_{\triangle}(G(n,m)) \, < \, - \tau\binom{n}{3}))$ for the ranges $n^{-3/2}\ll \tau\ll n^{-1}$ and $n^{-3/4}\ll\tau\ll 1$ respectively. Furthermore, in \cite{NRS22} it is proved that the log probability is at least $\Omega(\tau^2 n^{3})$ in the ``missing‘‘ range $n^{-1}\ll \tau\ll n^{-3/4}$, and they conjectured that this result gives the correct order of magnitude. Our main contribution is to prove this conjecture.

Constructing Hamilton cycles and perfect matchings efficiently

Michael Anastos — Mon, 28 Aug 2023 00:00:00 +0200

Starting with the empty graph on $[n]$, at each round, a set of $K=K(n)$ edges is presented chosen uniformly at random from the ones that have not been presented yet. We are then asked to choose at most one of the presented edges and add it to the current graph. Our goal is to construct a Hamiltonian graph with $(1+o(1))n$ edges within as few rounds as possible. We show that in this process, one can build a Hamiltonian graph of size $(1+o(1))n$ in $(1+o(1))(1+(\log n)/2K) n$ rounds w.h.p. The case $K=1$ implies that w.h.p. one can build a Hamiltonian graph by choosing $(1+o(1))n$ edges in an online fashion as they appear along the first $(0.5+o(1))n\log n$ rounds of the random graph process. This answers a question of Frieze, Krivelevich and Michaeli. Observe that the number of rounds is asymptotically optimal as the first $0.5n\log n$ edges do not span a Hamilton cycle w.h.p. The case $K=\Theta(\log n)$ implies that the Hamiltonicity threshold of the corresponding Achlioptas process is at most $(1+o(1))(1+(\log n)/2K) n$. This matches the $(1-o(1))(1+(\log n)/2K) n$ lower bound due to Krivelevich, Lubetzky and Sudakov and resolves the problem of determining the Hamiltonicity threshold of the Achlioptas process with $K=\Theta(\log n)$. We also show that in the above process one can construct a graph $G$ that spans a matching of size $\lfloor V(G)/2) \rfloor$ and $(0.5+o(1))n$ edges within $(1+o(1))(0.5+(\log n)/2K) n$ rounds w.h.p. Our proof relies on a robust Hamiltonicity property of the strong $4$-core of the binomial random graph which we use as a black-box. This property allows it to absorb paths covering vertices outside the strong $4$-core into a cycle.

Algorithms for subgraph complementation to some classes of graphs

Dhanyamol Antony, Sagartanu Pal, R.B. Sandeep — Mon, 28 Aug 2023 00:00:00 +0200

For a class $\mathcal{G}$ of graphs, the objective of Subgraph Complementation to $\mathcal{G}$ is to find whether there exists a subset $S$ of vertices of the input graph $G$ such that modifying $G$ by complementing the subgraph induced by $S$ results in a graph in $\mathcal{G}$. We obtain a polynomial-time algorithm for the problem when $\mathcal{G}$ is the class of graphs with minimum degree at least $k$, for a constant $k$, answering an open problem by Fomin et al. (Algorithmica, 2020). When $\mathcal{G}$ is the class of graphs without any induced copies of the star graph on $t+1$ vertices (for any constant $t\geq 3$) and diamond, we obtain a polynomial-time algorithm for the problem. This is in contrast with a result by Antony et al. (Algorithmica, 2022) that the problem is NP-complete and cannot be solved in subexponential-time (assuming the Exponential Time Hypothesis) when $\mathcal{G}$ is the class of graphs without any induced copies of the star graph on $t+1$ vertices, for every constant $t\geq 5$.

A lower bound for set-colouring Ramsey numbers

Mon, 28 Aug 2023 00:00:00 +0200

The set-colouring Ramsey number $R_{r,s}(k)$ is defined to be the minimum $n$ such that if each edge of the complete graph $K_n$ is assigned a set of $s$ colours from $\{1,\ldots,r\}$, then one of the colours contains a monochromatic clique of size $k$. The case $s = 1$ is the usual $r$-colour Ramsey number, and the case $s = r - 1$ was studied by Erdős, Hajnal and Rado in 1965, and by Erdős and Szemerédi in 1972. The first significant results for general $s$ were obtained only recently, by Conlon, Fox, He, Mubayi, Suk and Verstraëte, who showed that $R_{r,s}(k) = 2^{\Theta(kr)}$ if $s/r$ is bounded away from $0$ and $1$. In the range $s = r - o(r)$, however, their upper and lower bounds diverge significantly. In this note we introduce a new (random) colouring, and use it to determine $R_{r,s}(k)$ up to polylogarithmic factors in the exponent for essentially all $r$, $s$ and $k$.

Type-respecting amalgamation and big Ramsey degrees

Wed, 09 Aug 2023 00:00:00 +0200

We give an infinitary extension of the Nešetřil-Rödl theorem for category of relational structures with special type-respecting embeddings.

Cycles of every length and orientation in randomly perturbed digraphs

Igor Araujo, József Balogh, Robert Krueger, Simón Piga, Andrew Treglown — Mon, 28 Aug 2023 00:00:00 +0200

In 2003, Bohman, Frieze, and Martin initiated the study of randomly perturbed graphs and digraphs. For digraphs, they showed that for every $\alpha>0$, there exists a constant $C$ such that for every $n$-vertex digraph of minimum semi-degree at least $\alpha n$, if one adds $Cn$ random edges then asymptotically almost surely the resulting digraph contains a consistently oriented Hamilton cycle. We generalize their result, showing that the hypothesis of this theorem actually asymptotically almost surely ensures the existence of every orientation of a cycle of every possible length, simultaneously. Moreover, we prove that we can relax the minimum semi-degree condition to a minimum total degree condition when considering orientations of a cycle that do not contain a large number of vertices of indegree $1$.

Tiling problems in edge-ordered graphs

Igor Araujo, Simón Piga, Andrew Treglown, Zimu Xiang — Mon, 28 Aug 2023 00:00:00 +0200

Given graphs $F$ and $G$, a perfect $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$ that together cover all the vertices in $G$. The study of the minimum degree threshold forcing a perfect $F$-tiling in a graph $G$ has a long history, culminating in the Kühn-Osthus theorem [Combinatorica 2009] which resolves this problem, up to an additive constant, for all graphs $F$. We initiate the study of the analogous question for edge-ordered graphs. In particular, we characterize for which edge-ordered graphs $F$ this problem is well-defined. We also apply the absorbing method to asymptotically determine the minimum degree threshold for forcing a perfect $P$-tiling in an edge-ordered graph, where $P$ is any fixed monotone path.

Graphs without a rainbow path of length 3

Sebastian Babiński, Andrzej Grzesik — Mon, 28 Aug 2023 00:00:00 +0200

In 1959 Erdős and Gallai proved the asymptotically optimal bound for the maximum number of edges in graphs not containing a path of a fixed length. We investigate a rainbow version of the theorem, in which one considers $k \geq 1$ graphs on a common set of vertices not creating a path having edges from different graphs and asks for the maximum number of edges in each graph. We prove the asymptotically optimal bound in the case of a path on three edges and any $k \geq 1$.

Directed graphs without rainbow triangles

Sebastian Babiński, Andrzej Grzesik, Magdalena Prorok — Mon, 28 Aug 2023 00:00:00 +0200

One of the most fundamental questions in graph theory is Mantel‘s theorem which determines the maximum number of edges in a triangle-free graph of a given order. Recently a colorful variant of this problem has been solved. In such a variant we consider $c$ graphs on a common vertex set, thinking of each graph as edges in a distinct color, and want to determine the smallest number of edges in each color which guarantees the existence of a rainbow triangle. Here, we solve the analogous problem for directed graphs without rainbow triangles, either directed or transitive, for any number of colors. The constructions and proofs essentially differ for $c=3$ and $c \geq 4$ and the type of the forbidden triangle.

On ordered Ramsey numbers of matchings versus triangles

Martin Balko, Marian Poljak — Mon, 28 Aug 2023 00:00:00 +0200

For graphs $G^<$ and $H^<$ with linearly ordered vertex sets, the ordered Ramsey number $r_<(G^<,H^<)$ is the smallest $N \in \mathbb{N}$ such that any red-blue coloring of the edges of the complete ordered graph $K^<_N$ on $N$ vertices contains either a blue copy of $G^<$ or a red copy of $H^<$. Motivated by a problem of Conlon, Fox, Lee, and Sudakov (2017), we study the numbers $r_<(M^<,K^<_3)$ where $M^<$ is an $n$-vertex ordered matching. We prove that almost all $n$-vertex ordered matchings $M^<$ with interval chromatic number 2 satisfy $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{5/4})$ and $r_<(M^<,K^<_3) \in O(n^{7/4})$, improving a recent result by Rohatgi (2019). We also show that there are $n$-vertex ordered matchings $M^<$ with interval chromatic number at least 3 satisfying $r_<(M^<,K^<_3) \in \Omega((n/\log n)^{4/3})$, which asymptotically matches the best known lower bound on these ordered Ramsey numbers for general $n$-vertex ordered matchings.

On the sizes of t-intersecting k-chain-free families

József Balogh, William Linz, Balazs Patkos — Mon, 28 Aug 2023 00:00:00 +0200

A set system ${\mathcal F}$ is $t$-intersecting, if the size of the intersection of every pair of its elements has size at least $t$. A set system ${\mathcal F}$ is $k$-Sperner, if it does not contain a chain of length $k+1$. Our main result is the following: Suppose that $k$ and $t$ are fixed positive integers, where $n+t$ is even and $n$ is large enough. If ${\mathcal F}\subseteq 2^{[n]}$ is a $t$-intersecting $k$-Sperner family, then ${\mathcal F}$ has size at most the size of the sum of $k$ layers, of sizes $(n+t)/2,\ldots, (n+t)/2+k-1$. This bound is best possible. The case when $n+t$ is odd remains open.

Isoperimetric stability in lattices

Ben Barber, Joshua Erde, Peter Keevash, Alexander Roberts — Mon, 28 Aug 2023 00:00:00 +0200

We obtain isoperimetric stability theorems for general Cayley digraphs on $\mathbb{Z}^d$. For any fixed $B$ that generates $\mathbb{Z}^d$ over $\mathbb{Z}$, we characterise the approximate structure of large sets $A$ that are approximately isoperimetric in the Cayley digraph of $B$: we show that $A$ must be close to a set of the form $kZ \cap \mathbb{Z}^d$, where for the vertex boundary $Z$ is the conical hull of $B$, and for the edge boundary $Z$ is the zonotope generated by $B$.

Nonrepetitive colorings of R^d

Kathleen Barsse, Daniel Gonçalves, Matthieu Rosenfeld — Mon, 28 Aug 2023 00:00:00 +0200

The results of Thue state that there exists an infinite sequence over 3 symbols without 2 identical adjacent blocks, which we call a 2-nonrepetitive sequence, and also that there exists an infinite sequence over 2 symbols without 3 identical adjacent blocks, which is a 3-nonrepetitive sequence. An $r$-repetition is defined as a sequence of symbols consisting of $r$ identical adjacent blocks, and a sequence is said to be $r$-nonrepetitive if none of its subsequences are $r$-repetitions. Here, we study colorings of Euclidean spaces related to the work of Thue. A coloring of $\mathbb{R}^d$ is said to be $r$-nonrepetitive of no sequence of colors derived from a set of collinear points at distance 1 is an $r$-repetition. In this case, the coloring is said to avoid $r$-repetitions. It was proved in \cite{NonrepetitivePlanOG} that there exists a coloring of the plane that avoids 2-repetitions using 18 colors, and conversely, it was proved in \cite{GrytczuckEtAlMain} that there exists a coloring of the plane that avoids 43-repetitions using only 2 colors. We specifically study $r$-nonrepetitive colorings for fixed number of colors : for a fixed number of colors $k$ and dimension $d$, the aim is to determine the minimum multiplicity of repetition $r$ such that there exists an $r$-nonrepetitive coloring of $\mathbb{R}^d$ using $k$ colors. We prove that the plane, $\mathbb{R}^2$, admits a 2- and a 3-coloring avoiding 33- and 18-repetitions, respectively.

Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron

Paul Bastide, Carla Groenland, Hugo Jacob, Tom Johnston — Mon, 28 Aug 2023 00:00:00 +0200

For given positive integers $k$ and $n$, a family $\mathcal{F}$ of subsets of $\{1,\dots,n\}$ is $k$-antichain saturated if it does not contain an antichain of size $k$, but adding any set to $\mathcal{F}$ creates an antichain of size $k$. We use sat$^*(n, k)$ to denote the smallest size of such a family. For all $k$ and sufficiently large $n$, we determine the exact value of sat$^*(n, k)$. Our result implies that sat$^*(n, k)=n(k-1)-\Theta(k\log k)$, which confirms several conjectures on antichain saturation. Previously, exact values for sat$^*(n,k)$ were only known for $k$ up to $6$. We also prove a strengthening of a result of Lehman-Ron which may be of independent interest. We show that given $m$ disjoint chains in the Boolean lattice, we can create $m$ disjoint skipless chains that cover the same elements (where we call a chain skipless if any two consecutive elements differ in size by exactly one). The complete version of the paper can be found here \cite{antichainsaturation}.

Chromatic number of intersection graphs of segments with two slopes

Sudatta Bhattacharya, Zdenek Dvorak, Fariba Noorizadeh — Mon, 28 Aug 2023 00:00:00 +0200

A $d$-dir graph is an intersection graph of segments, where the segments have at most $d$ different slopes. It is easy to see that a $d$-dir graph with clique number $\omega$ has chromatic number at most $d\omega$. We study the chromatic number of $2$-dir graphs in more detail, proving that this upper bound is tight even in the fractional coloring setting.

Big Ramsey degrees in the metric setting

Tristan Bice, Jan Hubička, Matěj Konečný, Noé de Rancourt — Mon, 28 Aug 2023 00:00:00 +0200

Oscillation stability is an important concept in Banach space theory which happens to be closely connected to discrete Ramsey theory. For example, Gowers proved oscillation stability for the Banach space $c_0$ using his now famous Ramsey theorem for $\mathrm{FIN}_k$ as the key ingredient. We develop the theory behind this connection and introduce the notion of compact big Ramsey degrees, extending the theory of (discrete) big Ramsey degrees. We prove existence of compact big Ramsey degrees for the Banach space $\ell_\infty$ and the Urysohn sphere, with an explicit characterization in the case of $\ell_\infty$.

On a recolouring version of Hadwiger’s conjecture

Marthe Bonamy, Marc Heinrich, Clément Legrand-Duchesne, Jonathan Narboni — Mon, 28 Aug 2023 00:00:00 +0200

We prove that for any $\varepsilon>0$, for any large enough $t$, there is a graph $G$ that admits no $K_t$-minor but admits a $(\frac32-\varepsilon)t$-colouring that is ``frozen‘‘ with respect to Kempe changes, i.e. any two colour classes induce a connected component. This disproves three conjectures of Las Vergnas and Meyniel from 1981.

The Localization game on locally finite trees

Anthony Bonato, Florian Lehner, Trent Marbach, Jd Nir — Mon, 28 Aug 2023 00:00:00 +0200

We study the Localization game on locally finite graphs and trees, where each vertex has finite degree. As in finite graphs, we prove that any locally finite graph contains a subdivision where one cop can capture the robber. In contrast to the finite case, for $n$ a positive integer, we construct a locally finite tree with localization number $n$ for any choice of $n$. Such trees contain uncountably many ends, and we show this is necessary by proving that graphs with countably many ends have localization number at most 2. We finish with questions on characterizing the localization number of locally finite trees.

Twin-width and permutations

Mon, 28 Aug 2023 00:00:00 +0200

Inspired by a width invariant on permutations defined by Guillemot and Marx, Bonnet, Kim, Thomassé, and Watrigant introduced the twin-width of graphs, which is a parameter describing its structural complexity. This invariant has been further extended to binary structures, in several (basically equivalent) ways. We prove that a class of binary relational structures (that is: edge-colored partially directed graphs) has bounded twin-width if and only if it is a first-order transduction of a proper permutation class. As a by-product, we show that every class with bounded twin-width contains at most $2^{O(n)}$ pairwise non-isomorphic $n$-vertex graphs.

Independent dominating sets in planar triangulations

Fábio Botler, Cristina Fernandes, Juan Gutiérrez — Mon, 28 Aug 2023 00:00:00 +0200

In 1996, Matheson and Tarjan proved that every planar triangulation on $n$ vertices contains a dominating set, i.e., a set $S$ that contains a neighbor of every vertex not in $S$, of size at most $n/3$, and conjectured that this upper bound can be reduced to $n/4$ when $n$ is sufficiently large. In this paper, we consider the analogous problem for independent dominating sets: What is the minimum $ε$ for which every planar triangulation on $n$ vertices contains an independent dominating set of size at most $ε n$? We prove that $2/7 \leq ε \leq 3/8$.

Biclique immersions in graphs with independence number 2

Mon, 28 Aug 2023 00:00:00 +0200

The analogue of Hadwiger‘s Conjecture for the immersion relation states that every graph $G$ contains an immersion of $K_{\chi(G)}$. For graphs with independence number 2, this is equivalent to stating that every such $n$-vertex graph contains an immersion of $K_{\lceil n/2 \rceil}$. We show that every $n$-vertex graph with independence number 2 contains every complete bipartite graph on $\lceil n/2 \rceil$ vertices as an immersion.

A resolution of the Kohayakawa--Kreuter conjecture for the majority of cases

Candida Bowtell, Robert Hancock, Joseph Hyde — Mon, 28 Aug 2023 00:00:00 +0200

For graphs $G, H_1,\dots,H_r$, write $G \to (H_1, \ldots, H_r)$ to denote the property that whenever we $r$-colour the edges of $G$, there is a monochromatic copy of $H_i$ in colour $i$ for some $i \in \{1,\dots,r\}$. Mousset, Nenadov and Samotij proved an upper bound on the threshold function for the property that $G(n,p) \to (H_1,\dots,H_r)$, thereby resolving the $1$-statement of the Kohayakawa-Kreuter conjecture. We show that to prove the $0$-statement it suffices to prove a deterministic colouring result, which says that if $G$ is not too dense then $G \not \to (H_1,\dots,H_r)$. We extend upon the many partial results for the $0$-statement, by resolving it for a large number of cases, which in particular includes (but is not limited to) when $r \geq 3$, when $H_2$ is strictly $2$-balanced and not bipartite, or when $H_1$ and $H_2$ have the same $2$-densities.

Tight path, what is it (Ramsey-)good for? Absolutely (almost) nothing!

Simona Boyadzhiyska, Allan Lo — Mon, 28 Aug 2023 00:00:00 +0200

Given a pair of $k$-uniform hypergraphs $(G,H)$, the Ramsey number of $(G,H)$, denoted by $R(G,H)$, is the smallest integer $n$ such that in every red/blue-colouring of the edges of $K_n^{(k)}$ there exists a red copy of $G$ or a blue copy of $H$. Burr showed that, for any pair of graphs $(G,H)$, where $G$ is large and connected, the Ramsey number $R(G,H)$ is bounded below by $(v(G)-1)(\chi(H)-1)+\sigma(H)$, where $\sigma(H)$ stands for the minimum size of a colour class over all proper $\chi(H)$-colourings of $H$. Together with Erdős, he then asked when this lower bound is attained, introducing the notion of Ramsey goodness and its systematic study. We say that $G$ is $H$-good if the Ramsey number of $(G,H)$ is equal to the general lower bound. Among other results, it was shown by Burr that, for any graph $H$, every sufficiently long path is $H$-good. Our goal is to explore the notion of Ramsey goodness in the setting of 3-uniform hypergraphs. Motivated by Burr‘s result concerning paths and a recent result of Balogh, Clemen, Skokan, and Wagner, we ask: what 3-graphs $H$ is a (long) tight path good for? We demonstrate that, in stark contrast to the graph case, long tight paths are generally not $H$-good for various types of 3-graphs $H$. Even more, we show that the ratio $R(P_n, H)/n$ for a pair $(P_n, H)$ consisting of a tight path on $n$ vertices and a 3-graph $H$ cannot in general be bounded above by any function depending only on $\chi(H)$. We complement these negative results with a positive one, determining the Ramsey number asymptotically for pairs $(P_n, H)$ when $H$ belongs to a certain family of hypergraphs.

Effective bounds for induced size-Ramsey numbers of cycles

Domagoj Bradac, Nemanja Draganic, Benny Sudakov — Mon, 28 Aug 2023 00:00:00 +0200

The induced size-Ramsey number $\hat{r}_\text{ind}^k(H)$ of a graph $H$ is the smallest number of edges a (host) graph $G$ can have such that for any $k$-coloring of its edges, there exists a monochromatic copy of $H$ which is an induced subgraph of $G$. In 1995, in their seminal paper, Haxell, Kohayakawa and Łuczak showed that for cycles, these numbers are linear for any constant number of colours, i.e., $\hat{r}_\text{ind}^k(C_n)\leq Cn$ for some $C=C(k)$. The constant $C$ comes from the use of the regularity lemma, and has a tower type dependence on $k$. In this paper we significantly improve these bounds, showing that $\hat{r}_\text{ind}^k(C_n)\leq O(k^{102})n$ when $n$ is even, thus obtaining only a polynomial dependence of $C$ on $k$. We also prove $\hat{r}_\text{ind}^k(C_n)\leq e^{O(k\log k)}n$ for odd $n$, which almost matches the lower bound of $e^{\Omega(k)}n$. Finally, we show that the ordinary (non-induced) size-Ramsey number satisfies $\hat{r}^k(C_n)=e^{O(k)}n$ for odd $n$. This substantially improves the best previous result of $e^{O(k^2)}n$, and is best possible, up to the implied constant in the exponent. To achieve our results, we present a new host graph construction which, roughly speaking, reduces our task to finding a cycle of approximate given length in a graph with local sparsity.

Single-conflict colorings of degenerate graphs

Peter Bradshaw, Tomáš Masařík — Mon, 28 Aug 2023 00:00:00 +0200

We consider the single-conflict coloring problem, in which each edge of a graph receives a forbidden ordered color pair. The task is to find a vertex coloring such that no two adjacent vertices receive a pair of colors forbidden at an edge joining them. We show that for any assignment of forbidden color pairs to the edges of a $d$-degenerate graph $G$ on $n$ vertices of edge-multiplicity at most $\log \log n$, $O(\sqrt{ d } \log n)$ colors are always enough to color the vertices of $G$ in a way that avoids every forbidden color pair. This answers a question of Dvořák, Esperet, Kang, and Ozeki for simple graphs (Journal of Graph Theory 2021).

Monadic NIP in monotone classes of relational structures

Samuel Braunfeld, Anuj Dawar, Ioannis Eleftheriadis, Aris Papadopoulos — Mon, 28 Aug 2023 00:00:00 +0200

We prove that for any monotone class of finite relational structures, the first-order theory of the class is NIP in the sense of stability theory if, and only if, the collection of Gaifman graphs of structures in this class is nowhere dense. This generalises results previously known for graphs to relational structures and answers an open question posed by Adler and Adler (2014). The result is established by the application of Ramsey-theoretic techniques and shows that the property of being NIP is highly robust for monotone classes. We also show that the model-checking problem for first-order logic is intractable on any monotone class of structures that is not (monadically) NIP. This is a contribution towards the conjecture that the hereditary classes of structures admitting fixed-parameter tractable model-checking are precisely those that are monadically NIP.

Decomposition horizons: from graph sparsity to model-theoretic dividing lines

Sam Braunfeld, Jaroslav Nešetřil, Patrice Ossona de Mendez, Sebastian Siebertz — Mon, 28 Aug 2023 00:00:00 +0200

Low treedepth decompositions are central to the structural characterizations of bounded expansion classes and nowhere dense classes, and the core of main algorithmic properties of these classes, including fixed-parameter (quasi) linear-time algorithms checking whether a fixed graph $F$ is an induced subgraph of the input graph $G$. These decompositions have been extended to structurally bounded expansion classes and structurally nowhere dense classes, where low treedepth decompositions are replaced by low shrubdepth decompositions. In the emerging framework of a structural graph theory for hereditary classes of structures based on tools from model theory, it is natural to ask how these decompositions behave with the fundamental model theoretical notions of dependence (alias NIP) and stability. In this work, we prove that the model theoretical notions of NIP and stable classes are transported by decompositions. Precisely: Let $\mathscr C$ be a hereditary class of graphs. Assume that for every $p$ there is a hereditary NIP class $\mathscr D_p$ with the property that the vertex set of every graph $G\in\mathscr C$ can be partitioned into $N_p=N_p(G)$ parts in such a way that the union of any $p$ parts induce a subgraph in $\mathscr D_p$ and $\log N_p(G)\in o(\log |G|)$. We prove that then $\mathscr C$ is (monadically) NIP. Similarly, if every $\mathscr D_p$ is stable, then $\mathscr C$ is (monadically) stable. Results of this type lead to the definition of decomposition horizons as closure operators. We establish some of their basic properties and provide several further examples of decomposition horizons.

Countable ultrahomogeneous 2-colored graphs consisting of disjoint unions of cliques

Sofia Brenner, Irene Heinrich — Mon, 28 Aug 2023 00:00:00 +0200

We classify the countable ultrahomogeneous $2$-vertex-colored graphs in which the color classes form disjoint unions of cliques. This generalizes work by Jenkinson et. al. \cite{JEN12}, Lockett and Truss \cite{LOC14} as well as Rose \cite{ROS11} on ultrahomogeneous $n$-graphs. As the key aspect in such a classification, we identify a concept called piecewise ultrahomogeneity. We prove that there are two specific graphs whose occurrence essentially dictates whether a graph is piecewise ultrahomogeneous, and we exploit this fact to prove the classification.

Raising the roof on the threshold for Szemerédi‘s theorem with random differences

Jop Briët, Davi Castro-Silva — Mon, 28 Aug 2023 00:00:00 +0200

Using recent developments on the theory of locally decodable codes, we prove that the critical size for Szemerédi‘s theorem with random differences is bounded from above by $N^{1-\frac{2}{k} + o(1)}$ for length-$k$ progressions. This improves the previous best bounds of $N^{1-\frac{1}{\lceil{k/2}\rceil} + o(1)}$ for all odd $k$.

Random restrictions of high-rank tensors and polynomial maps

Jop Briët, Davi Castro-Silva — Mon, 28 Aug 2023 00:00:00 +0200

Motivated by a problem in computational complexity, we consider the behavior of rank functions for tensors and polynomial maps under random coordinate restrictions. We show that, for a broad class of rank functions called natural rank functions, random coordinate restriction to a dense set will typically reduce the rank by at most a constant factor.

Strict Erdős-Ko-Rado for simplicial complexes

Denys Bulavka, Russ Woodroofe — Mon, 28 Aug 2023 00:00:00 +0200

We show that the strict Erdős-Ko-Rado property holds for sequentially Cohen-Macaulay near-cones. In particular, this implies that chordal graphs with at least one isolated vertex satisfy the strict Erdős-Ko-Rado property.

Exact enumeration of graphs and bipartite graphs with degree constraints

Emma Caizergues, Elie de Panafieu — Mon, 28 Aug 2023 00:00:00 +0200

We provide a new explicit formula enumerating graphs with constraints on their degrees, such as regular graphs, and extend it to bipartite graphs. It relies on generating function manipulations and Hadamard products. Keywords: regular graphs, exact enumeration, D-finite, differentiably finite

A precise condition for independent transversals in bipartite covers

Stijn Cambie, Penny Haxell, Ross J. Kang, Ronen Wdowinski — Mon, 28 Aug 2023 00:00:00 +0200

Given a bipartite graph $H=(V=V_A\cup V_B,E)$ in which any vertex in $V_A$ (resp. $V_B$) has degree at most $D_A$ (resp. $D_B$), suppose there is a partition of $V$ that is a refinement of the bipartition $V_A\cup V_B$ such that the parts in $V_A$ (resp. $V_B$) have size at least $k_A$ (resp. $k_B$). We prove that the condition $D_A/k_A+D_B/k_B\le 1$ is sufficient for the existence of an independent set of vertices of $H$ that is simultaneously transversal to the partition, and show moreover that this condition is sharp.

Chordal graphs with bounded tree-width

Jordi Castellví, Michael Drmota, Marc Noy, Clément Requilé — Mon, 28 Aug 2023 00:00:00 +0200

Given $t\ge 2$ and $0\le k\le t$, we prove that the number of labelled $k$-connected chordal graphs with $n$ vertices and tree-width at most $t$ is asymptotically $c n^{-5/2} \gamma^n n!$, as $n\to\infty$, for some constants $c,\gamma >0$ depending on $t$ and $k$. Additionally, we show that the number of $i$-cliques ($2\le i\le t$) in a uniform random $k$-connected chordal graph with tree-width at most $t$ is normally distributed as $n\to\infty$. The asymptotic enumeration of graphs of tree-width at most $t$ is wide open for $t\ge 3$. To the best of our knowledge, this is the first non-trivial class of graphs with bounded tree-width where the asymptotic counting problem is solved. Our starting point is the work of Wormald [Counting Labelled Chordal Graphs, Graphs and Combinatorics (1985)], were an algorithm is developed to obtain the exact number of labelled chordal graphs on $n$ vertices..

A compactification of the set of sequences of positive real numbers with applications to limits of graphs

David Chodounsky, Lluis Vena — Mon, 28 Aug 2023 00:00:00 +0200

We introduce compactification results on the set of sequences of positive real numbers: under the continuum hypothesis, one can find a totally ordered set of sequences whose elements can be used as test sequences to capture every possible asympthotic growth, perhaps along a subsequence; this behaviour mimics the statement that, in a compact set of $\mathbb{R}$, every sequence has a convergent partial subsequence. These compactification results allows us to unify two notions of convergence for graphs into a single graph-convergence notion, while retaining the property that each sequence of graphs have a convergent partial subsequence. These convergent notions are the Benjamini-Schramm convergence for bounded degree graphs, regarding the distribution of r-neighbourhoods of the vertices, and the left-convergence for dense graphs, regarding the existence, for each fixed graph $F$, of a limiting probability that a random mapping from $F$ to $\{G_i\}$ is a graph homomorphism.

A direct bijection between two-stack sortable permutations and fighting fish

Lapo Cioni, Luca Ferrari, Corentin Henriet — Mon, 28 Aug 2023 00:00:00 +0200

We define a bijection between two-stack sortable permutations and fighting fish, enriching the garden of bijections linking the numerous combinatorial classes counted by the sequence $A000139$ of the OEIS. Our bijection is (up to symmetry) the non-recursive version of the one of Fang (2018). Along the way, we encounter labeled sorting trees, a new class of trees that appear to have nice properties that seem worth to explore.

Counting tournament score sequences

Anders Claesson, Mark Dukes, Atli Fannar Franklín, Sigurður Örn Stefánsson — Mon, 28 Aug 2023 00:00:00 +0200

The score sequence of a tournament is the sequence of the out-degrees of its vertices arranged in nondecreasing order. The problem of counting score sequences of a tournament with $n$ vertices is more than 100 years old (MacMahon 1920). In 2013 Hanna conjectured a surprising and elegant recursion for these numbers. We settle this conjecture in the affirmative by showing that it is a corollary to our main theorem, which is a factorization of the generating function for score sequences with a distinguished index. We also derive a closed formula and a quadratic time algorithm for counting score sequences.

The k-XORSAT threshold revisited

Amin Coja-Oghlan, Mihyun Kang, Lena Krieg, Maurice Rolvien — Mon, 28 Aug 2023 00:00:00 +0200

We provide a simplified proof of the random $k$-XORSAT satisfiability threshold theorem. As an extension we also determine the full rank threshold for sparse random matrices over finite fields with precisely $k$ non-zero entries per row. This complements a result from [Ayre, Coja-Oghlan, Gao, Müller: Combinatorica 2020]. The proof combines physics-inspired message passing arguments with a surgical moment computation. Msc: 60B20, 15B52

Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄

Linda Cook, Tomáš Masařík, Marcin Pilipczuk, Amadeus Reinald, Uéverton S. Souza — Mon, 28 Aug 2023 00:00:00 +0200

An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. The Gyárfás-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest $F$, there is some function $f$ such that every $F$-free graph $G$ with clique number $\omega(G)$ has chromatic number at most $f(\omega(G))$. Aboulker, Charbit, and Naserasr [Extension of Gyárfás-Sumner Conjecture to Digraphs; E-JC 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph $D$ is the minimum number of colors required to color the vertex set of $D$ so that no directed cycle in $D$ is monochromatic. Aboulker, Charbit, and Naserasr‘s $\overrightarrow{\chi}$-boundedness conjecture states that for every oriented forest $F$, there is some function $f$ such that every $F$-free oriented graph $D$ has dichromatic number at most $f(\omega(D))$, where $\omega(D)$ is the size of a maximum clique in the graph underlying $D$. In this paper, we perform the first step towards proving Aboulker, Charbit, and Naserasr‘s $\overrightarrow{\chi}$-boundedness conjecture by showing that it holds when $F$ is any orientation of a path on four vertices.

Higher degree Erdős distinct evaluations problem

Simone Costa, Stefano Della Fiore, Andrea Ferraguti — Mon, 28 Aug 2023 00:00:00 +0200

Let $\Sigma=\{a_1, . . . , a_n\}$ be a set of positive integers with $a_1 < \dots < a_n$ such that all $2^n$ subset sums are distinct. A famous conjecture by Erdős states that $a_n>c\cdot 2^n$ for some constant $c$, while the best result known to date is of the form $a_n>c\cdot 2^n/\sqrt{n}$. In this paper, we propose a generalization of the Erdős distinct sum problem that is in the same spirit as those of the Davenport and the Erdős-Ginzburg-Ziv constants recently introduced in \cite{CGS} and in \cite{CS}. More precisely, we require that the non-zero evaluations of the $m$-th degree symmetric polynomial are all distinct over the sub-sequences of $\Sigma$. Even though these evaluations can not be seen as the values assumed by the sum of independent random variables, surprisingly, the variance method works to provide a nontrivial lower bound on $a_n$. Indeed, the main result here presented is to show that $$a_n>c_m\cdot 2^{\frac{n}{m}}/n^{1-\frac{1}{2m}}.$$

Monochromatic configurations on a circle

Gábor Damásdi, Nora Frankl, Janos Pach, Dömötör Pálvölgyi — Mon, 28 Aug 2023 00:00:00 +0200

For $k\geq 3$, call a $k$-tuple $(d_1,d_2,\dots,d_k)$ with $d_1\geq d_2\geq \dots \geq d_k>0$ and $\sum_{i=1}^k d_i=1$ a Ramsey $k$-tuple if the following is true: in every two-colouring of the circle of unit perimeter, there is a monochromatic $k$-tuple of points in which the distances of cyclically consecutive points, measured along the arcs, are $d_1,d_2,\dots,d_k$ in some order. By a conjecture of Stromquist, if $d_i=\frac{2^{k-i}}{2^k-1}$, then $(d_1,\dots,d_k)$ is Ramsey. Our main result is a proof of the converse of this conjecture. That is, we show that if $(d_1,\dots,d_k)$ is Ramsey, then $d_i=\frac{2^{k-i}}{2^k-1}$. We do this by finding connections of the problem to certain questions from number theory about partitioning $\mathbb{N}$ into so-called Beatty sequences. We also disprove a majority version of Stromquist‘s conjecture, study a robust version, and discuss a discrete version.

Beyond the Erdős–Sós conjecture

Akbar Davoodi, Diana Piguet, Hanka Řada, Nicolás Sanhueza-Matamala — Mon, 28 Aug 2023 00:00:00 +0200

We prove an asymptotic version of a tree-containment conjecture of Klimošová, Piguet and Rozhoň [European J. Combin. 88 (2020), 103106] for graphs with quadratically many edges. The result implies that the asymptotic version of the Erdős-Sós conjecture in the setting of dense graphs is correct.

Dispersion on the Complete Graph

Umberto De Ambroggio, Tamas Makai, Konstantinos Panagiotou — Mon, 28 Aug 2023 00:00:00 +0200

We consider a synchronous process of particles moving on the vertices of a graph $G$, introduced by Cooper, McDowell, Radzik, Rivera and Shiraga (2018). Initially, $M$ particles are placed on one vertex of $G$. At the beginning of each time step, for every vertex inhabited by at least two particles, each of these particles moves independently to a neighbour chosen uniformly at random. The process ends at the first step when no vertex is inhabited by more than one particle. Cooper et al. showed that when the underlying graph is the complete graph on $n$ vertices, then there is a phase transition when the number of particles $M = n/2$. They showed that if $M<(1-\varepsilon)n/2$ for some fixed $\varepsilon>0$, then the process finishes in a logarithmic number of steps, while if $M>(1+\varepsilon)n/2$, an exponential number of steps are required with high probability. In this paper we provide a thorough analysis of the distribution of the dispersion time in the barely critical regime, where $\varepsilon =o(1)$, and describe the fine details of the transition between logarithmic and exponential time. As a consequence of our results we establish, for example, that the dispersion time is in probability and in expectation $\Theta(n^{1/2})$ when $|\varepsilon| = O(n^{-1/2})$, and provide qualitative bounds for its tail behavior.

The root cluster after percolation on preferential attachment trees

Colin Desmarais, Cecilia Holmgren, Stephan Wagner — Mon, 28 Aug 2023 00:00:00 +0200

The class of linear preferential attachment trees includes recursive trees, plane-oriented recursive trees, binary search trees, and increasing $d$-ary trees. Bond percolation with parameter $p$ is performed by considering every edge in a graph independently, and either keeping the edge with probability $p$ or removing it otherwise. The resulting connected components are called clusters. In this extended abstract, we demonstrate how to use methods from analytic combinatorics to compute limiting distributions, after rescaling, for the size of the cluster containing the root. These results are part of a larger work on broadcasting induced colorings of preferential attachment trees.

Cycles through two edges in signed graphs

Matt DeVos, Kathryn Nurse — Mon, 28 Aug 2023 00:00:00 +0200

We give a characterization of when a signed graph $G$ with a pair of distinguished edges $e_1, e_2 \in E(G)$ has the property that all cycles containing both $e_1$ and $e_2$ have the same sign. This answers a question of Zaslavsky.

Powers of planar graphs, product structure, and blocking partitions

Marc Distel, Robert Hickingbotham, Michał T. Seweryn, David R. Wood — Mon, 28 Aug 2023 00:00:00 +0200

We show that there exist a constant $c$ and a function $f$ such that the $k$-power of a planar graph with maximum degree $\Delta$ is isomorphic to a subgraph of $H \boxtimes P \boxtimes K_{f(\Delta, k)}$ for some graph $H$ with treewidth at most $c$ and some path $P$. This is the first product structure theorem for $k$-powers of planar graphs, where the treewidth of $H$ does not depend on $k$. We actually prove a stronger result, which implies an analogous product structure theorem for other graph classes, including $k$-planar graphs (of arbitrary degree). Our proof uses a new concept of blocking partitions which is of independent interest. An $\ell$-blocking partition of a graph $G$ is a partition of the vertex set of $G$ into connected subsets such that every path in $G$ of length greater than $\ell$ contains two vertices in one set of the partition. The key lemma in our proof states that there exists a positive integer $\ell$ such that every planar graph of maximum degree $\Delta$ has an $\ell$-blocking partition with parts of size bounded in terms of $\Delta$.

When is Cartesian product a Cayley graph?

Edward Dobson, Ademir Hujdurović, Wilfried Imrich, Ronald Ortner — Mon, 28 Aug 2023 00:00:00 +0200

A graph is said to be a Cayley graph if its automorphism group admits a regular subgroup. Automorphisms of the Cartesian product of graphs are well understood, and it is known that Cartesian product of Cayley graphs is a Cayley graph. It is natural to ask the reverse question, namely whether all the factors of Cartesian product that is a Cayley graph have to be Cayley graphs. The main purpose of this paper is to initiate the study of this question.

A generalization of Bondy’s pancyclicity theorem

Nemanja Draganić, David Munha Correia, Benny Sudakov — Mon, 28 Aug 2023 00:00:00 +0200

The bipartite independence number of a graph $G$, denoted as $\tilde\alpha(G)$, is the minimal number $k$ such that there exist positive integers $a$ and $b$ with $a+b=k+1$ with the property that for any two sets $A,B\subseteq V(G)$ with $|A|=a$ and $|B|=b$, there is an edge between $A$ and $B$. McDiarmid and Yolov showed that if $\delta(G)\geq\tilde \alpha(G)$ then $G$ is Hamiltonian, extending the famous theorem of Dirac which states that if $\delta(G)\geq |G|/2$ then $G$ is Hamiltonian. In 1973, Bondy showed that, unless $G$ is a complete bipartite graph, Dirac‘s Hamiltonicity condition also implies pancyclicity, i.e., existence of cycles of all the lengths from $3$ up to $n$. In this paper we show that $\delta(G)\geq\tilde \alpha(G)$ implies that $G$ is pancyclic or that $G=K_{\frac{n}{2},\frac{n}{2}}$, thus extending the result of McDiarmid and Yolov, and generalizing the classic theorem of Bondy.

Chvátal-Erdős condition for pancyclicity

Nemanja Draganić, David Munhá Correia, Benny Sudakov — Mon, 28 Aug 2023 00:00:00 +0200

An $n$-vertex graph is Hamiltonian if it contains a cycle that covers all of its vertices and it is pancyclic if it contains cycles of all lengths from $3$ up to $n$. A celebrated meta-conjecture of Bondy states that every non-trivial condition implying Hamiltonicity also implies pancyclicity (up to possibly a few exceptional graphs). We show that every graph $G$ with $\kappa(G) > (1+o(1)) \alpha(G)$ is pancyclic. This extends the famous Chvátal-Erdős condition for Hamiltonicity and proves asymptotically a $30$-year old conjecture of Jackson and Ordaz.

Tower gaps in multicolour Ramsey numbers

Quentin Dubroff, António Girão, Eoin Hurley, Corrine Yap — Mon, 28 Aug 2023 00:00:00 +0200

Resolving a problem of Conlon, Fox, and Rödl, we construct a family of hypergraphs with arbitrarily large tower height separation between their $2$-colour and $q$-colour Ramsey numbers. The main lemma underlying this construction is a new variant of the Erdős-Hajnal stepping-up lemma for a generalized Ramsey number $r_k(t;q,p)$, which we define as the smallest integer $n$ such that every $q$-colouring of the $k$-sets on $n$ vertices contains a set of $t$ vertices spanning fewer than $p$ colours. Our results provide the first tower-type lower bounds on these numbers.

On the minimum number of inversions to make a digraph k-(arc-)strong

Julien Duron, Frédéric Havet, Florian Hörsch, Clément Rambaud — Mon, 28 Aug 2023 00:00:00 +0200

The inversion of a set $X$ of vertices in a digraph $D$ consists of reversing the direction of all arcs of $D\langle X\rangle$. We study $sinv‘_k(D)$ (resp. $sinv_k(D)$) which is the minimum number of inversions needed to transform $D$ into a $k$-arc-strong (resp. $k$-strong) digraph and $sinv‘_k(n) = \max\{sinv‘_k(D) \mid D~\mbox{is a $2k$-edge-connected digraph of order $n$}\}$. We show : (i) $\frac{1}{2} \log (n - k+1) \leq sinv‘_k(n) \leq \log n + 4k -3$ for all $n \in \mathbb{Z}_{\geq 0}$; (ii) for any fixed positive integers $k$ and $t$, deciding whether a given oriented graph $\vec{G}$ satisfies $sinv‘_k(\vec{G}) \leq t$ (resp. $sinv_k(\vec{G}) \leq t$) is NP-complete ; (iii) if $T$ is a tournament of order at least $2k+1$, then $sinv‘_k(T) \leq sinv_k(T) \leq 2k$, and $\frac{1}{2}\log(2k+1) \leq sinv‘_k(T) \leq sinv_k(T)$ for some $T$; (iv) if $T$ is a tournament of order at least $28k-5$ (resp. $14k-3$), then $sinv_k(T) \leq 1$ (resp. $sinv_k(T) \leq 6$); (v) for every $ε>0$, there exists $C$ such that $sinv_k(T) \leq C$ for every tournament $T$ on at least $2k+1 + ε k$ vertices.

Precoloring extension in planar near-Eulerian-triangulations

Zdeněk Dvořák, Benjamin Moore, Michaela Seifrtová, Robert Šámal — Mon, 28 Aug 2023 00:00:00 +0200

We consider the 4-precoloring extension problem in planar near-Eulerian- triangulations, i.e., plane graphs where all faces except possibly for the outer one have length three, all vertices not incident with the outer face have even degree, and exactly the vertices incident with the outer face are precolored. We give a necessary topological condition for the precoloring to extend, and give a complete characterization when the outer face has length at most five and when all vertices of the outer face have odd degree and are colored using only three colors.

Maximum genus orientable embeddings from circuit decompositions of dense eulerian graphs and digraphs

M. N. Ellingham, Joanna Ellis-Monaghan — Mon, 28 Aug 2023 00:00:00 +0200

Suppose we have an eulerian (di)graph with a (directed) circuit decomposition. We show that if the (di)graph is sufficiently dense, then it has an orientable embedding in which the given circuits are facial walks and there are exactly one or two other faces. This embedding has maximum genus subject to the given circuits being facial walks. When there is only one other face, it is necessarily bounded by an euler circuit. Thus, if the numbers of vertices and edges have the same parity, a sufficiently dense (di)graph $D$ with a given (directed) euler circuit $C$ has an orientable embedding with exactly two faces, each bounded by an euler circuit, one of which is $C$. The main theorem encompasses several special cases in the literature, for example, when the digraph is a tournament.

Tangled Paths: A Random Graph Model from Mallows Permutations

Jessica Enright, Kitty Meeks, William Pettersson, John Sylvester — Mon, 28 Aug 2023 00:00:00 +0200

We introduce the random graph $\mathcal{P}(n,q)$ which results from taking the union of two paths of length $n\geq 1$, where the vertices of one of the paths have been relabelled according to a Mallows permutation with real parameter $0<q(n)\leq 1$. This random graph model, the tangled path, goes through an evolution: if $q$ is close to $0$ the graph bears resemblance to a path, and as $q$ tends to $1$ it becomes an expander. In an effort to understand the evolution of $\mathcal{P}(n,q)$ we determine the treewidth and cutwidth of $\mathcal{P}(n,q)$ up to log factors for all $q$. We also show that the property of having a separator of size one has a sharp threshold. In addition, we prove bounds on the diameter, and vertex isoperimetric number for specific values of $q$.

Cop number of random k-uniform hypergraphs

Joshua Erde, Mihyun Kang, Florian Lehner, Bojan Mohar, Dominik Schmid — Mon, 28 Aug 2023 00:00:00 +0200

The game of Cops and Robber is usually played on a graph, in which a group of cops attempt to catch a robber moving along the edges of the graph. The cop number of a graph is the minimum number of cops required to win the game. An important conjecture in this area, due to Meyniel, states that the cop number of an $n$-vertex connected graph is $O(\sqrt{n})$. In 2016, Prałat and Wormald [Meyniel‘s conjecture holds for random graphs, Random Structures Algorithms. 48 (2016), no. 2, 396–421. MR3449604] showed that this conjecture holds with high probability for random graphs above the connectedness threshold. Moreoever, Łuczak and Prałat [Chasing robbers on random graphs: Zigzag theorem, Random Structures Algorithms. 37 (2010), no. 4, 516–524. MR2760362] showed that on a $\log$-scale the cop number demonstrates a surprising zigzag behaviour in dense regimes of the binomial random graph $G(n,p)$. In this paper, we consider the game of Cops and Robber on a hypergraph, where the players move along hyperedges instead of edges. We show that with high probability the cop number of the $k$-uniform binomial random hypergraph $G^k(n,p)$ is $O\left(\sqrt{\frac{n}{k}} \log n \right)$ for a broad range of parameters $p$ and $k$. As opposed to the case of $G(n,p)$, on a $\log$-scale our upper bound on the cop number arises as the minimum of two complementary zigzag curves. Furthermore, we conjecture that the cop number of a connected $k$-uniform hypergraph on $n$ vertices is $O\left(\sqrt{\frac{n}{k}}\right)$.

The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem

Louis Esperet, Ugo Giocanti, Clément Legrand-Duchesne — Mon, 28 Aug 2023 00:00:00 +0200

An infinite graph is quasi-transitive if its vertex set has finitely many orbits under the action of its automorphism group. In this paper we obtain a structure theorem for locally finite quasi-transitive graphs avoiding a minor, which is reminiscent of the Robertson-Seymour Graph Minor Structure Theorem. We prove that every locally finite quasi-transitive graph $G$ avoiding a minor has a tree-decomposition whose torsos are finite or planar; moreover the tree-decomposition is canonical, i.e. invariant under the action of the automorphism group of $G$. As applications of this result, we prove the following. (i) Every locally finite quasi-transitive graph attains its Hadwiger number, that is, if such a graph contains arbitrarily large clique minors, then it contains an infinite clique minor. This extends a result of Thomassen (1992) who proved it in the 4-connected case and suggested that this assumption could be omitted. (ii) Locally finite quasi-transitive graphs avoiding a minor are accessible (in the sense of Thomassen and Woess), which extends known results on planar graphs to any proper minor-closed family. (iii) Minor-excluded finitely generated groups are accessible (in the group-theoretic sense) and finitely presented, which extends classical results on planar groups. (iv) The domino problem is decidable in a minor-excluded finitely generated group if and only if the group is virtually free, which proves the minor-excluded case of a conjecture of Ballier and Stein (2018).

Sharp threshold for embedding balanced spanning trees in random geometric graphs

Alberto Espuny Díaz, Lyuben Lichev, Dieter Mitsche, Alexandra Wesolek — Mon, 28 Aug 2023 00:00:00 +0200

Consider the random geometric graph $\mathcal{G}(n,r)$ obtained by independently assigning a uniformly random position in $[0,1]^2$ to each of the $n$ vertices of the graph and connecting two vertices by an edge whenever their Euclidean distance is at most $r$. We study the event that $\mathcal{G}(n,r)$ contains a spanning copy of a balanced tree $T$ and obtain sharp thresholds for these events. Our methods provide a polynomial-time algorithm for finding a copy of such trees $T$ above the threshold.

Odd-Sunflowers

Peter Frankl, Janos Pach, Dömötör Pálvölgyi — Mon, 28 Aug 2023 00:00:00 +0200

Extending the notion of sunflowers, we call a family of at least two sets an odd-sunflower if every element of the underlying set is contained in an odd number of sets or in none of them. It follows from the Erdős-Szemerédi conjecture, recently proved by Naslund and Sawin, that there is a constant $\mu<2$ such that every family of subsets of an $n$-element set that contains no odd-sunflower consists of at most $\mu^n$ sets. We construct such families of size at least $1.5021^n$.

Upper bounds on Ramsey numbers for vector spaces over finite fields

Bryce Frederickson, Liana Yepremyan — Mon, 28 Aug 2023 00:00:00 +0200

For $B \subseteq \mathbb F_q^m$, let $\mathrm{ex}_{\mathrm{aff}}(n,B)$ denote the maximum cardinality of a set $A \subseteq \mathbb F_q^n$ with no subset which is affinely isomorphic to $B$. Furstenberg and Katznelson proved that for any $B \subseteq \mathbb F_q^m$, $\mathrm{ex}_{\mathrm{aff}}(n,B)=o(q^n)$ as $n \to \infty$. For certain $q$ and $B$, some more precise bounds are known. We connect some of these problems to certain Ramsey-type problems, and obtain some new bounds for the latter. For $s,t \geq 1$, let $R_q(s,t)$ denote the minimum $n$ such that in every red-blue coloring of one-dimensional subspaces of $\mathbb F_q^n$, there is either a red $s$-dimensional subspace of $\mathbb F_q^n$ or a blue $t$-dimensional subspace of $\mathbb F_q^n$. The existence of these numbers is implied by the celebrated theorem of Graham, Leeb, Rothschild. We improve the best known upper bounds on $R_2(2,t)$, $R_3(2,t)$, $R_2(t,t)$, and $R_3(t,t)$.

A general bound for the induced poset saturation problem

Andrea Freschi, Simon Piga, Maryam Sharifzadeh, Andrew Treglown — Mon, 28 Aug 2023 00:00:00 +0200

For a fixed poset $P$, a family $\mathcal F$ of subsets of $[n]$ is induced $P$-saturated if $\mathcal F$ does not contain an induced copy of $P$, but for every subset $S$ of $[n]$ such that $ S\not \in \mathcal F$, then $P$ is an induced subposet of $\mathcal F \cup \{S\}$. The size of the smallest such family $\mathcal F$ is denoted by $\text{sat}^* (n,P)$. Keszegh, Lemons, Martin, Pálvölgyi and Patkós [Journal of Combinatorial Theory Series A, 2021] proved that there is a dichotomy of behaviour for this parameter: given any poset $P$, either $\text{sat}^* (n,P)=O(1)$ or $\text{sat}^* (n,P)\geq \log _2 n$. We improve this general result showing that either $\text{sat}^* (n,P)=O(1)$ or $\text{sat}^* (n,P) \geq 2 \sqrt{n-2}$. Our proof makes use of a Turán-type result for digraphs. Curiously, it remains open as to whether our result is essentially best possible or not. On the one hand, a conjecture of Ivan states that for the so-called diamond poset $\Diamond$ we have $\text{sat}^* (n,\Diamond)=\Theta (\sqrt{n})$; so if true this conjecture implies our result is tight up to a multiplicative constant. On the other hand, a conjecture of Keszegh, Lemons, Martin, Pálvölgyi and Patkós states that given any poset $P$, either $\text{sat}^* (n,P)=O(1)$ or $\text{sat}^* (n,P)\geq n+1$. We prove that this latter conjecture is true for a certain class of posets $P$.

Extremal number of graphs from geometric shapes

Jun Gao, Oliver Janzer, Hong Liu, Zixiang Xu — Mon, 28 Aug 2023 00:00:00 +0200

We study the Turán problem for highly symmetric bipartite graphs arising from geometric shapes and periodic tilings commonly found in nature. (i) The prism $C_{2\ell}^{\square}:=C_{2\ell}\square K_{2}$ is the graph consisting of two vertex disjoint $2\ell$-cycles and a matching pairing the corresponding vertices of these two cycles. We show that for every $\ell\ge 4$, ex$(n,C_{2\ell}^{\square})=\Theta(n^{3/2})$. This resolves a conjecture of He, Li and Feng. (ii) The hexagonal tiling in honeycomb is one of the most natural structures in the real world. We show that the extremal number of honeycomb graphs has the same order of magnitude as their basic building unit 6-cycles. (iii) We also consider bipartite graphs from quadrangulations of the cylinder and the torus. We prove near optimal bounds for both configurations. In particular, our method gives a very short proof of a tight upper bound for the extremal number of the 2-dimensional grid, improving a recent result of Bradač, Janzer, Sudakov and Tomon. Our proofs mix several ideas, including shifting embedding schemes, weighted homomorphism and subgraph counts and asymmetric dependent random choice.

The dimension of the feasible region of pattern densities

Frederik Garbe, Daniel Kral, Alexandru Malekshahian, Raul Penaguiao — Mon, 28 Aug 2023 00:00:00 +0200

A classical result of Erdős, Lovász and Spencer from the late 1970s asserts that the dimension of the feasible region of homomorphic densities of graphs with at most $k$ vertices in large graphs is equal to the number of connected graphs with at most $k$ vertices. Glebov et al. showed that pattern densities of indecomposable permutations are independent, i.e., the dimension of the feasible region of densities of $k$-patterns is at least the number of non-trivial indecomposable permutations of size at most $k$. We identify a larger set of permutations, which are called Lyndon permutations, whose pattern densities are independent, and show that the dimension of the feasible region of densities of $k$-patterns is equal to the number of non-trivial Lyndon permutations of size at most $k$.

On the structure and values of betweenness centrality in dense betweenness-uniform graphs

Mon, 28 Aug 2023 00:00:00 +0200

Betweenness centrality is a network centrality measure based on the amount of shortest paths passing through a given vertex. A graph is betweenness-uniform (BUG) if all vertices have an equal value of betweenness centrality. In this contribution, we focus on betweenness-uniform graphs with betweenness centrality below one. We disprove a conjecture about the existence of a BUG with betweenness value $\alpha$ for any rational number $\alpha$ from the interval $(\frac{3}{4}, \infty)$ by showing that only very few betweenness centrality values below $\frac{6}{7}$ are attained for at least one BUG. Furthermore, among graphs with diameter at least three, there are no betweenness-uniform graphs with a betweenness centrality smaller than one. In graphs of smaller diameter, the same can be shown under a uniformity condition on the components of the complement.

The Minimum Degree Removal Lemma Thresholds

Lior Gishboliner, Benny Sudakov, Zhihan Jin — Mon, 28 Aug 2023 00:00:00 +0200

The graph removal lemma is a fundamental result in extremal graph theory which says that for every fixed graph $H$ and $\varepsilon > 0$, if an $n$-vertex graph $G$ contains $\varepsilon n^2$ edge-disjoint copies of $H$ then $G$ contains $\delta n^{v(H)}$ copies of $H$ for some $\delta = \delta(\varepsilon,H) > 0$. The current proofs of the removal lemma give only very weak bounds on $\delta(\varepsilon,H)$, and it is also known that $\delta(\varepsilon,H)$ is not polynomial in $\varepsilon$ unless $H$ is bipartite. Recently, Fox and Wigderson initiated the study of minimum degree conditions guaranteeing that $\delta(\varepsilon,H)$ depends polynomially or linearly on $\varepsilon$. We answer several questions of Fox and Wigderson on this topic.

Hamilton cycles in pseudorandom graphs

Stefan Glock, David Munha Correia, Benny Sudakov — Mon, 28 Aug 2023 00:00:00 +0200

Finding general conditions which ensure that a graph is Hamiltonian is a central topic in graph theory. An old and well known conjecture in the area states that any $d$-regular $n$-vertex graph $G$ whose second largest eigenvalue in absolute value $\lambda(G)$ is at most $d/C$, for some universal constant $C>0$, has a Hamilton cycle. We obtain two main results which make substantial progress towards this problem. Firstly, we settle this conjecture in full when the degree $d$ is at least a small power of $n$. Secondly, in the general case we show that $\lambda(G) \leq d/ C(\log n)^{1/3}$ implies the existence of a Hamilton cycle, improving the 20-year old bound of $d/ \log^{1-o(1)} n$ of Krivelevich and Sudakov. We use in a novel way a variety of methods, such as a robust Pósa rotation-extension technique, the Friedman-Pippenger tree embedding with rollbacks and the absorbing method, combined with additional tools and ideas. Our results have several interesting applications, giving best bounds on the number of generators which guarantee the Hamiltonicity of random Cayley graphs, which is an important partial case of the well known Hamiltonicity conjecture of Lovász. They can also be used to improve a result of Alon and Bourgain on additive patterns in multiplicative subgroups.

Random perfect matchings in regular graphs

Bertille Granet, Felix Joos — Mon, 28 Aug 2023 00:00:00 +0200

We prove that in all regular robust expanders $G$, every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.

Forcing Generalized Quasirandom Graphs Efficiently

Andrzej Grzesik, Daniel Kráľ, Oleg Pikhurko — Mon, 28 Aug 2023 00:00:00 +0200

We study 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. Lovász and Sós showed that the structure of such graphs is forced by homomorphism densities of graphs with at most $(10q)^q+q$ vertices; subsequently, Lovász refined the argument to show that graphs with $4(2q+3)^8$ vertices suffice. Our results imply 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, and, if vertices in distinct parts have distinct degrees, then $2q+1$ vertices suffice. The latter improves the bound of $8q-4$ due to Spencer.

Refined list version of Hadwiger’s Conjecture

Yangyan Gu, Yiting Jiang, David Wood, Xuding Zhu — Mon, 28 Aug 2023 00:00:00 +0200

Assume $\lambda=\{k_1,k_2, \ldots, k_q\}$ is a partition of $k_{\lambda} = \sum_{i=1}^q k_i$. A $\lambda$-list assignment of $G$ is a $k_\lambda$-list assignment $L$ of $G$ such that the colour set $\bigcup_{v \in V(G)}L(v)$ can be partitioned into $|\lambda|= q$ sets $C_1,C_2,\ldots,C_q$ such that for each $i$ and each vertex $v$ of $G$, $|L(v) \cap C_i| \ge k_i$. We say $G$ is $\lambda$-choosable if $G$ is $L$-colourable for any $\lambda$-list assignment $L$ of $G$. The concept of $\lambda$-choosability is a refinement of choosability that puts $k$-choosability and $k$-colourability in the same framework. If $|\lambda|$ is close to $k_\lambda$, then $\lambda$-choosability is close to $k_\lambda$-colourability; if $|\lambda|$ is close to $1$, then $\lambda$-choosability is close to $k_\lambda$-choosability. This paper studies Hadwiger‘s Conjecture in the context of $\lambda$-choosability. Hadwiger‘s Conjecture is equivalent to saying that every $K_t$-minor-free graph is $\{1 \star (t-1)\}$-choosable for any positive integer $t$. We prove that for $t \ge 5$, for any partition $\lambda$ of $t-1$ other than $\{1 \star (t-1)\}$, there is a $K_t$-minor-free graph $G$ that is not $\lambda$-choosable. We then construct several types of $K_t$-minor-free graphs that are not $\lambda$-choosable, where $k_\lambda - (t-1)$ gets larger as $k_\lambda-|\lambda|$ gets larger.

A general approach to transversal versions of Dirac-type theorems

Pranshu Gupta, Fabian Hamann, Alp Müyesser, Olaf Parczyk, Amedeo Sgueglia — Mon, 28 Aug 2023 00:00:00 +0200

Given a collection of hypergraphs $\textbf{\textup{H}}=(H_1, \ldots, H_m)$ with the same vertex set, an $m$-edge graph $F\subset \cup_{i\in [m]}H_i$ is a transversal if there is a bijection $\phi:E(F)\to [m]$ such that $e\in E(H_{\phi(e)})$ for each $e\in E(F)$. How large does the minimum degree of each $H_i$ need to be so that $\textbf{\textup{H}}$ necessarily contains a copy of $F$ that is a transversal? Each $H_i$ in the collection could be the same hypergraph, hence the minimum degree of each $H_i$ needs to be large enough to ensure that $F\subseteq H_i$. Since its general introduction by Joos and Kim [Bull. Lond. Math. Soc., 2020, 52(3): 498–504], a growing body of work has shown that in many cases this lower bound is tight. In this paper, we give a unified approach to this problem by providing a widely applicable sufficient condition for this lower bound to be asymptotically tight. This is general enough to recover many previous results in the area and obtain novel transversal variants of several classical Dirac-type results for (powers of) Hamilton cycles. For example, we derive that any collection of $rn$ graphs on an $n$-vertex set, each with minimum degree at least $(r/(r+1)+o(1))n$, contains a transversal copy of the $r$-th power of a Hamilton cycle. This can be viewed as a rainbow version of the Pósa-Seymour conjecture.

The maximum number of copies of an even cycle in a planar graph

Ervin Győri, Zhen He, Zequn Lv, Nika Salia, Casey Tompkins, Xiutao Zhu — Mon, 28 Aug 2023 00:00:00 +0200

We resolve a conjecture of Cox and Martin by determining asymptotically for every $k\ge 2$ the maximum number of copies of $C_{2k}$ in an $n$-vertex planar graph.

3-uniform linear hypergraphs without a long Berge path

Ervin Győri, Nika Salia — Mon, 28 Aug 2023 00:00:00 +0200

Extensions of the Erdős-Gallai theorem for general hypergraphs are well studied. In this work, we prove the extension of the Erdős-Gallai theorem for linear hypergraphs. In particular, we show that the number of hyperedges in an $n$-vertex $3$-uniform linear hypergraph, without a Berge path of length $k$ as a subgraph is at most $\frac{(k-1)}{6}n$ for $k\geq 4$. This is an extended abstract for EUROCOMB23 of the manuscript arXiv:2211.16184.

Rooting algebraic vertices of convergent sequences

David Hartman, Tomáš Hons, Jaroslav Nešetřil — Mon, 28 Aug 2023 00:00:00 +0200

Structural convergence is a framework for convergence of graphs by Nešetřil and Ossona de Mendez that unifies the dense (left) graph convergence and Benjamini-Schramm convergence. They posed a problem asking whether for a given sequence of graphs $(G_n)$ converging to a limit $L$ and a vertex $r$ of $L$ it is possible to find a sequence of vertices $(r_n)$ such that $L$ rooted at $r$ is the limit of the graphs $G_n$ rooted at $r_n$. A counterexample was found by Christofides and Král‘, but they showed that the statement holds for almost all vertices $r$ of $L$. We offer another perspective to the original problem by considering the size of definable sets to which the root $r$ belongs. We prove that if $r$ is an algebraic vertex (i.e. belongs to a finite definable set), the sequence of roots $(r_n)$ always exists.

Colouring complete multipartite and Kneser-type digraphs

Ararat Harutyunyan, Gil Puig i Surroca — Mon, 28 Aug 2023 00:00:00 +0200

The dichromatic number of a digraph $D$ is the smallest $k$ such that $D$ can be partitioned into $k$ acyclic subdigraphs, and the dichromatic number of an undirected graph is the maximum dichromatic number over all its orientations. We present bounds for the dichromatic number of Kneser graphs and Borsuk graphs, and for the list dichromatic number of certain classes of Kneser graphs and complete multipartite graphs. The bounds presented are sharp up to a constant factor. Additionally, we give a directed analogue of Sabidussi‘s theorem on the chromatic number of graph products.

The hitting time of clique factors

Annika Heckel, Marc Kaufmann, Noela Müller, Matija Pasch — Mon, 28 Aug 2023 00:00:00 +0200

In \cite{kahn2022hitting}, Kahn gave the strongest possible, affirmative, answer to Shamir‘s problem, which had been open since the late 1970s: Let $r \ge 3 $ and let $n$ be divisible by $r$. Then, in the random $r$-uniform hypergraph process on $n$ vertices, as soon as the last isolated vertex disappears, a perfect matching emerges. In the present work, we prove the analogue of this result for clique factors in the random graph process: At the time that the last vertex joins a copy of the complete graph $K_r$, the random graph process contains a $K_r$-factor. Our proof draws on a novel sequence of couplings which embeds the random hypergraph process into the cliques of the random graph process. An analogous result is proved for clique factors in the $s$-uniform hypergraph process ($s \ge 3$).

Roudneff‘s Conjecture in Dimension 4

Rangel Hernández-Ortiz, Kolja Knauer, Luis Pedro Montejano, Manfred Scheucher — Mon, 28 Aug 2023 00:00:00 +0200

J.-P. Roudneff conjectured in 1991 that every arrangement of $n \ge 2d+1\ge 5$ pseudohyperplanes in the real projective space $\mathbb{P}^d$ has at most $\sum_{i=0}^{d-2} \binom{n-1}{i}$ complete cells (i.e., cells bounded by each hyperplane). The conjecture is true for $d=2,3$ and for arrangements arising from Lawrence oriented matroids. The main result of this manuscript is to show the validity of Roudneff‘s conjecture for $d=4$. Moreover, based on computational data we conjecture that the maximum number of complete cells is only obtained by cyclic arrangements.

Locality in sumsets

Peter van Hintum, Peter Keevash — Mon, 28 Aug 2023 00:00:00 +0200

Motivated by the Polynomial Freiman-Ruzsa (PFR) Conjecture, we develop a theory of locality in sumsets, with several applications to John-type approximation and stability of sets with small doubling. One highlight shows that if $A \subset \mathbb{Z}$ with $|A+A| \le (1-ε) 2^d |A|$ is non-degenerate then $A$ is covered by $O(2^d)$ translates of a $d$-dimensional generalised arithmetic progression ($d$-GAP) $P$ with $|P| \le O_{d,ε}(|A|)$; thus we obtain one of the polynomial bounds required by PFR, under the non-degeneracy assumption that $A$ is not efficiently covered by $O_{d,ε}(1)$ translates of a $(d-1)$-GAP. We also prove a stability result showing for any $ε,α>0$ that if $A \subset \mathbb{Z}$ with $|A+A| \le (2-ε)2^d|A|$ is non-degenerate then some $A‘ \subset A$ with $|A‘|>(1-α)|A|$ is efficiently covered by either a $(d+1)$-GAP or $O_{α}(1)$ translates of a $d$-GAP. This `dimension-free‘ bound for approximate covering makes for a surprising contrast with exact covering, where the required number of translates not only grows with $d$, but does so exponentially. Another highlight shows that if $A \subset \mathbb{Z}$ is non-degenerate with $|A+A| \le (2^d + \ell)|A|$ and $\ell \le 0.1 \cdot 2^d$ then $A$ is covered by $\ell+1$ translates of a $d$-GAP $P$ with $|P| \le O_d(|A|)$; this is tight, in that $\ell+1$ cannot be replaced by any smaller number. The above results also hold for $A \subset \mathbb{R}^d$, replacing GAPs by a suitable common generalisation of GAPs and convex bodies, which we call generalised convex progressions. In this setting the non-degeneracy condition holds automatically, so we obtain essentially optimal bounds with no additional assumption on $A$. Here we show that if $A\subset\mathbb{R}^k$ satisfies $|\frac{A+A}{2}|\leq (1+\delta)|A|$ with $\delta\in(0,1)$, then $\exists A‘\subset A$ with $|A‘|\geq (1-\delta)|A|$ so that $|\operatorname{co}(A‘)|\leq O_{k,1-\delta}(|A|)$. This is a dimensionally independent sharp stability result for the Brunn-Minkowski inequality for equal sets, which hints towards a possible analogue for the Prékopa-Leindler inequality. These results are all deduced from a unifying theory, in which we introduce a new intrinsic structural approximation of any set, which we call the `additive hull‘, and develop its theory via a refinement of Freiman‘s theorem with additional separation properties. A further application that will be published separately is a proof of Ruzsa‘s Discrete Brunn-Minkowski Conjecture \cite{Ruzsaconjecture}.

Fractionally Isomorphic Graphs and Graphons

Jan Hladký, Eng Keat Hng — Mon, 28 Aug 2023 00:00:00 +0200

Fractional isomorphism is a well-studied relaxation of graph isomorphism with a very rich theory. Grebík and Rocha [Combinatorica 42, pp 365-404 (2022)] developed a concept of fractional isomorphism for graphons and proved that it enjoys an analogous theory. In particular, they proved that if $G_1,G_2,\ldots$ converge to a graphon $U$, $H_1,H_2,\ldots$ converge to a graphon $W$ and each $G_i$ is fractionally isomorphic to $H_i$, then $U$ is fractionally isomorphic to $W$. Answering the main question from ibid, we prove the converse of the statement above: If $U$ and $W$ are fractionally isomorphic graphons, then there exist sequences of graphs $G_1,G_2,\ldots$ and $H_1,H_2,\ldots$ which converge to $U$ and $W$ respectively and for which each $G_i$ is fractionally isomorphic to $H_i$. As an easy but convenient corollary of our methods, we get that every regular graphon can be approximated by regular graphs.

Permutation flip processes

Jan Hladký, Hanka Řada — Mon, 28 Aug 2023 00:00:00 +0200

We introduce a broad class of stochastic processes on permutations which we call flip processes. A single step in these processes is given by a local change on a randomly chosen fixed-sized tuple of the domain. We use the theory of permutons to describe the typical evolution of any such flip process $\pi_0,\pi_1,\pi_2,\ldots$ started from any initial permutation $\pi_0\in\mathrm{Sym}(n)$. More specifically, we construct trajectories $\Phi:\mathfrak{P}\times [0,\infty)\rightarrow\mathfrak{P}$ in the space of permutons with the property that if $\pi_0$ is close to a permuton $\gamma$ then for any $T>0$ with high probability $\pi_{Tn}$ is close to $\Phi^{T}(\gamma)$. This view allows to study various questions inspired by dynamical systems.

Twin-width of Planar Graphs; a Short Proof

Petr Hlineny — Mon, 28 Aug 2023 00:00:00 +0200

The fascinating question of the maximum value of twin-width on planar graphs is nowadays not far from a final resolution; there is a lower bound of $7$ coming from a construction by Král‘ and Lamaison [arXiv, September 2022], and an upper bound of $8$ by Hliněný and Jedelský [arXiv, October 2022]. The upper bound (currently best) of $8$, however, is rather complicated and involved. We give a short and simple self-contained proof that the twin-width of planar graphs is at most $11$.

Stack and Queue Numbers of Graphs Revisited

Petr Hlineny, Adam Straka — Mon, 28 Aug 2023 00:00:00 +0200

A long-standing question of the mutual relation between the stack and queue numbers of a graph, explicitly emphasized by Dujmović and Wood in 2005, was ``half-answered‘‘ by Dujmović, Eppstein, Hickingbotham, Morin and Wood in 2022; they proved the existence of a graph family with the queue number at most $4$ but unbounded stack number. We give an alternative very short, and still elementary, proof of the same fact.

Crux, space constraints and subdivisions

Seonghyuk Im, Jaehoon Kim, Younjin Kim, Hong Liu — Mon, 28 Aug 2023 00:00:00 +0200

The existence of $H$-subdivisions within a graph $G$ has deep connections with topological, structural and extremal properties of $G$. One prominent example of such a connection, due to Bollobás and Thomason and independently Komlós and Szemerédi, asserts that the average degree of $G$ being $d$ ensures a $K_{\Omega(\sqrt{d})}$-subdivision in $G$. Although this square-root bound is the best possible, various results showed that much larger clique subdivisions can be found in a graph for many natural classes. We investigate the connection between crux, a notion capturing the essential order of a graph, and the existence of large clique subdivisions. Our main result gives an asymptotically optimal bound on the size of a largest clique subdivision in a generic graph $G$, which is determined by both its average degree and its crux size. As corollaries, we obtain (i) a characterisation of extremal graphs for which the square-root bound above is tight: they are essentially a disjoint union of graphs each of which has the crux size linear in $d$; (ii) a unifying approach to find a clique subdivision of almost optimal size in graphs which do not contain a fixed bipartite graph as a subgraph; (iii) and that the clique subdivision size in random graphs $G(n,p)$ witnesses a dichotomy: when $p = \omega(n^{-1/2})$, the barrier is the space, while when $p=o( n^{-1/2})$, the bottleneck is the density.

Cops and Robber on Hyperbolic Manifolds

Vesna Iršič, Bojan Mohar, Alexandra Wesolek — Mon, 28 Aug 2023 00:00:00 +0200

The Cops and Robber game on geodesic spaces is a pursuit-evasion game with discrete steps which captures the behavior of the game played on graphs, as well as that of continuous pursuit-evasion games. One of the outstanding open problems about the game on graphs is to determine which graphs embeddable in a surface of genus $g$ have largest cop number. It is known that the cop number of genus $g$ graphs is $O(g)$ and that there are examples whose cop number is $\tilde\Omega(\sqrt{g}\,)$. The same phenomenon occurs when the game is played on geodesic surfaces. In this paper we obtain a surprising result when the game is played on a surface with constant curvature. It is shown that two cops have a strategy to come arbitrarily close to the robber, independently of the genus. For special hyperbolic surfaces we also give upper bounds on the number of cops needed to catch the robber. Our results generalize to higher-dimensional hyperbolic manifolds.

How connectivity affects the extremal number of trees

Suyun Jiang, Hong Liu, Nika Salia — Mon, 28 Aug 2023 00:00:00 +0200

The Erdős-Sós conjecture states that the maximum number of edges in an $n$-vertex graph without a given $k$-vertex tree is at most $\frac {n(k-2)}{2}$. Despite significant interest, the conjecture remains unsolved. Recently, Caro, Patkós, and Tuza considered this problem for host graphs that are connected. Settling a problem posed by them, for a $k$-vertex tree $T$, we construct $n$-vertex connected graphs that are $T$-free with at least $(1/4-o_k(1))nk$ edges, showing that the additional connectivity condition can reduce the maximum size by at most a factor of 2. Furthermore, we show that this is optimal: there is a family of $k$-vertex brooms $T$ such that the maximum size of an $n$-vertex connected $T$-free graph is at most $(1/4+o_k(1))nk$.

Semi-algebraic and semi-linear Ramsey numbers

Zhihan Jin, István Tomon — Mon, 28 Aug 2023 00:00:00 +0200

An $r$-uniform hypergraph $H$ is semi-algebraic of complexity $\mathbf{t}=(d,D,m)$ if the vertices of $H$ correspond to points in $\mathbb{R}^{d}$, and the edges of $H$ are determined by the sign-pattern of $m$ degree-$D$ polynomials. Semi-algebraic hypergraphs of bounded complexity provide a general framework for studying geometrically defined hypergraphs. The much-studied semi-algebraic Ramsey number $R_{r}^{\mathbf{t}}(s,n)$ denotes the smallest $N$ such that every $r$-uniform semi-algebraic hypergraph of complexity $\mathbf{t}$ on $N$ vertices contains either a clique of size $s$, or an independent set of size $n$. Conlon, Fox, Pach, Sudakov and Suk proved that $R_{r}^{\mathbf{t}}(n,n)<\mbox{tw}_{r-1}(n^{O(1)})$, where $\mbox{tw}_{k}(x)$ is a tower of 2‘s of height $k$ with an $x$ on the top. This bound is also the best possible if $\min\{d,D,m\}$ is sufficiently large with respect to $r$. They conjectured that in the asymmetric case, we have $R_{3}^{\mathbf{t}}(s,n)n^{(\log n)^{1/3-o(1)}}$ for some complexity $\mathbf{t}$. In addition, motivated by the results of Bukh-Matoušek and Basit-Chernikov-Starchenko-Tao-Tran, we study the complexity of the Ramsey problem when the defining polynomials are linear, that is, when $D=1$. In particular, we prove that $R_{r}^{d,1,m}(n,n)\leq 2^{O(n^{4r^2m^2})}$, while from below, we establish $R^{1,1,1}_{r}(n,n)\geq 2^{\Omega(n^{\lfloor r/2\rfloor-1})}$.

Perfect-matching covers of cubic graphs with colouring defect 3

Ján Karabáš, Edita Macajova, Roman Nedela, Martin Skoviera — Mon, 28 Aug 2023 00:00:00 +0200

The colouring defect of a cubic graph is the smallest number of edges left uncovered by any set of three perfect matchings. While $3$-edge-colourable graphs have defect $0$, those that cannot be $3$-edge-coloured have defect at least $3$. We show that every bridgeless cubic graph with defect $3$ can have its edges covered with at most five perfect matchings, which verifies a long-standing conjecture of Berge for this class of graphs. Moreover, we determine the extremal graphs.

High-rank subtensors of high-rank tensors

Thomas Karam — Mon, 28 Aug 2023 00:00:00 +0200

Let $d \ge 2$ be a positive integer. We show that for a class of notions $R$ of rank for order-$d$ tensors, which includes in particular the tensor rank, the slice rank and the partition rank, there exist functions $F_{d,R}$ and $G_{d,R}$ such that if an order-$d$ tensor has $R$-rank at least $G_{d,R}(l)$ then we can restrict its entries to a product of sets $X_1 \times \dots \times X_d$ such that the restriction has $R$-rank at least $l$ and the sets $X_1, \dots, X_d$ each have size at most $F_{d,R}(l)$. Furthermore, our proof methods allow us to show that under a very natural condition we can require the sets $X_1, \dots, X_d$ to be pairwise disjoint.

Rainbow spanning trees in uniformly coloured perturbed graphs

Kyriakos Katsamaktsis, Shoham Letzter, Amedeo Sgueglia — Mon, 28 Aug 2023 00:00:00 +0200

We consider the problem of finding a copy of a rainbow spanning bounded-degree tree in the uniformly edge-coloured randomly perturbed graph. Let $G_0$ be an $n$-vertex graph with minimum degree at least $\delta n$, and let $T$ be a tree on $n$ vertices with maximum degree at most $d$, where $\delta \in (0,1)$ and $d \ge 2$ are constants. We show that there exists $C = C(\delta, d) > 0$ such that, with high probability, if the edges of the union $G_0 \cup \mathbf{G}(n,C/n)$ are uniformly coloured with colours in $[n-1]$, then there is a rainbow copy of $T$. Our result resolves in a strong form a conjecture of Aigner-Horev, Hefetz and Lahiri.

(Random) Trees of Intermediate Volume Growth

George Kontogeorgiou, Martin Winter — Mon, 28 Aug 2023 00:00:00 +0200

For every sufficiently well-behaved function $g\:\mathbb{R}_{\ge 0}\to\mathbb{R}_{\ge 0}$ that grows at least linearly and at most exponentially we construct a tree $T$ of uniform volume growth $g$, that is, $$C_1\cdot g(r/4)\le |B_G(v,r)| \le C_2\cdot g(4r),\quad\text{for all $r\ge 0$ and $v\in V(T)$},$$ with $C_1,C_2>0$ and where $B_G(v,r)$ denotes the ball of radius $r$ centered at a vertex $v$. In particular, this yields examples of trees of uniform intermediate (\ie\ super-polynomial and sub-exponential) volume growth. We use this construction to provide first examples of unimodular random rooted trees of uniform intermediate growth, answering a question by Itai Benjamini. We find a peculiar change in structural properties for these trees at growth $r^{\log\log r}$. Our results can be applied to obtain triangulations of $\mathbb{R}^2$ with varied growth behaviours and a Riemannian metric on $\mathbb{R}^2$ for the same wide range of growth behaviors.

Finding pairwise disjoint vector pairs in F₂ⁿ with a prescribed sequence of differences

Benedek Kovács — Mon, 28 Aug 2023 00:00:00 +0200

We consider the following question by Balister, Győri and Schelp: given $2^{n-1}$ nonzero vectors in $\mathbb{F}_2^n$ with zero sum, is it always possible to partition $\mathbb{F}_2^n$ into pairs such that the difference between the two elements of the $i$-th pair is equal to the $i$-th given vector? An analogous question in $\mathbb{F}_p$ was resolved by Preissmann and Mischler in 2009. In this paper, we prove the conjecture in $\mathbb{F}_2^n$ in the case when there are at most $n-2\log n-1$ distinct values among the given differences, and also in the case when at least a fraction $\frac{28}{29}$ of the differences are equal.

Avoiding intersections of given size in finite affine spaces AG(n,2)

Benedek Kovács, Zoltán Lóránt Nagy — Mon, 28 Aug 2023 00:00:00 +0200

We study the set of intersection sizes of a $k$-dimensional affine subspace and a point set of size $m \in [0, 2^n]$ of the $n$ dimensional binary affine space $\mathrm{AG}(n,2)$.

Graph covers and generalized snarks

Jan Kratochvil, Roman Nedela — Mon, 28 Aug 2023 00:00:00 +0200

The notion of graph cover, also known as locally bijective homomorphism, is a discretization of covering spaces known from general topology. It is a pair of incidence-preserving vertex- and edge-mappings between two graphs, the edge-component being bijective on the edge-neighborhoods of every vertex and its image. In line with the current trends in topological graph theory and its applications in mathematical physics, graphs are considered in the most relaxed form and as such they may contain multiple edges, loops and semi-edges. Nevertheless, simple graphs (binary structures without multiple edges, loops, or semi-edges) play an important role. The Strong Dichotomy Conjecture of Bok et al. [2022] states that for every fixed graph $H$, deciding if an input graph covers $H$ is either polynomial time solvable for arbitrary input graphs, or NP-complete for simple ones. These authors introduced the following quasi-order on the class of connected graphs: A connected graph $A$ is called stronger than a connected graph $B$ if every simple graph that covers $A$ also covers $B$. Witnesses of $A$ not being stronger than $B$ are generalized snarks in the sense that they are simple graphs that cover $A$ but do not cover $B$. Bok et al. conjectured that if $A$ has no semi-edges, then $A$ is stronger than $B$ if and only if $A$ covers $B$. We prove this conjecture for cubic one-vertex graphs, and we also justify it for all cubic graphs $A$ with at most 4 vertices.

On edge-ordered graphs with linear extremal functions

Gaurav Kucheriya, Gábor Tardos — Mon, 28 Aug 2023 00:00:00 +0200

The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. in 2020. Here we characterize connected edge-ordered graphs with linear extremal functions. This characterization is similar in spirit to results of Füredi et al. (2020) about vertex-ordered and convex geometric graphs.

A polynomial removal lemma for posets

Gabor Kun, Panna Timea Fekete — Mon, 28 Aug 2023 00:00:00 +0200

We prove a removal lemma with polynomial bound for posets. Alon and Shapira proved that every class of undirected graphs closed under the removal of edges and vertices is strongly testable. However, their bounds on the queries are not very effective, since they heavily rely on Szemerédi‘s regularity lemma. The case of posets turns out to be simpler: we show that every class of posets closed under the removal of edges is easily testable, that is, strongly testable with a polynomial bound on the queries. We also give a simple classification: for every class of posets closed under the removal of edges and vertices there is an $h$ such that the class is indistinguishable from the class of posets without chains of length $h$ (by testing with a constant number of queries). The analogous results hold for comparability graphs.

Tiling Dense Hypergraphs

Richard Lang — Mon, 28 Aug 2023 00:00:00 +0200

There are three essentially necessary conditions for perfect tilings in hypergraphs, which correspond to barriers in space, divisibility and covering. It is natural to ask when these conditions are asymptotically sufficient. Our main result confirms this for hypergraph families that are approximately closed under taking a typical induced subgraph of constant order. As an application, we recover and extend a series of well-known results for perfect tilings in hypergraphs and related settings involving vertex orderings and rainbow structures.

On Perfect Subdivision Tilings

Hyunwoo Lee — Mon, 28 Aug 2023 00:00:00 +0200

For a given graph $H$, we say that a graph $G$ has a perfect $H$-subdivision tiling if $G$ contains a collection of vertex-disjoint subdivisions of $H$ covering all vertices of $G.$ Let $\delta_{sub}(n, H)$ be the smallest integer $k$ such that any $n$-vertex graph $G$ with minimum degree at least $k$ has a perfect $H$-subdivision tiling. For every graph $H$, we asymptotically determined the value of $\delta_{sub}(n, H)$. More precisely, for every graph $H$ with at least one edge, there is a constant $1 < \xi^*(H)\leq 2$ such that $\delta_{sub}(n, H) = \left(1 - \frac{1}{\xi^*(H)} + o(1) \right)n$ if $H$ has a bipartite subdivision with two parts having different parities. Otherwise, the threshold may depend on the parity of $n.$

Cycle Partition of Dense Regular Digraphs and Oriented Graphs

Allan Lo, Viresh Patel, Mehmet Akif Yildiz — Mon, 28 Aug 2023 00:00:00 +0200

Magnant and Martin \cite{PathCover} conjectured that every $d$-regular graph on $n$ vertices can be covered by $n/(d+1)$ vertex-disjoint paths. Gruslys and Letzter \cite{GruslysLetzter} verified this conjecture in the dense case, even for cycles rather than paths. We prove the analogous result for directed graphs and oriented graphs, that is, for all $\alpha>0$, there exists $n_0=n_0(\alpha)$ such that every $d$-regular digraph on $n$ vertices with $d \ge \alpha n $ can be covered by at most $n/(d+1)$ vertex-disjoint cycles. Moreover if $G$ is an oriented graph, then $n/(2d+1)$ cycles suffice. This also establishes Jackson‘s long standing conjecture \cite{JacksonConjecture} for large $n$ that every $d$-regular oriented graph on $n$ vertices with $n\leq 4d+1$ is Hamiltonian.

Almost partitioning every 2-edge-coloured complete k-graph into k monochromatic tight cycles

Allan Lo, Vincent Pfenninger — Mon, 28 Aug 2023 00:00:00 +0200

A $k$-uniform tight cycle is a $k$-graph with a cyclic order of its vertices such that every $k$ consecutive vertices from an edge. We show that for $k\geq 3$, every red-blue edge-coloured complete $k$-graph on $n$ vertices contains $k$ vertex-disjoint monochromatic tight cycles that together cover $n – o(n)$ vertices.

Kneser graphs are Hamiltonian

Arturo Merino, Torsten Mütze, - Namrata — Mon, 28 Aug 2023 00:00:00 +0200

For integers $k\geq 1$ and $n\geq 2k+1$, the Kneser graph $K(n,k)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two disjoint sets. It has been conjectured since the 1970s that all Kneser graphs admit a Hamilton cycle, with one notable exception, namely the Petersen graph $K(5,2)$. This problem received considerable attention in the literature, including a recent solution for the sparsest case $n=2k+1$. The main contribution of this paper is to prove the conjecture in full generality. We also extend this Hamiltonicity result to all connected generalized Johnson graphs (except the Petersen graph). The generalized Johnson graph $J(n,k,s)$ has as vertices all $k$-element subsets of an $n$-element ground set, and an edge between any two sets whose intersection has size exactly $s$. Clearly, we have $K(n,k)=J(n,k,0)$, i.e., generalized Johnson graph include Kneser graphs as a special case. Our results imply that all known families of vertex-transitive graphs defined by intersecting set systems have a Hamilton cycle, which settles an interesting special case of Lovász‘ conjecture on Hamilton cycles in vertex-transitive graphs from 1970. Our main technical innovation is to study cycles in Kneser graphs by a kinetic system of multiple gliders that move at different speeds and that interact over time, reminiscent of the gliders in Conway‘s Game of Life, and to analyze this system combinatorially and via linear algebra.

Vizing‘s edge-recoloring conjecture holds.

Jonathan Narboni — Mon, 28 Aug 2023 00:00:00 +0200

In 1964 Vizing proved that starting from any $k$-edge-coloring of a graph $G$ one can reach, using only Kempe swaps, a $(\Delta+1)$-edge-coloring of $G$ where $\Delta$ is the maximum degree of $G$. One year later he conjectured that one can also reach a $\Delta$-edge-coloring of $G$ if there exists one. Bonamy et. al proved that the conjecture is true for the case of triangle-free graphs. In this paper we prove the conjecture for all simple graphs.

Product-free sets in the free group

Miquel Ortega, Juanjo Rué, Oriol Serra — Mon, 28 Aug 2023 00:00:00 +0200

We prove that product-free sets of the free group over a finite alphabet have maximum density $1/2$ with respect to the natural measure that assigns total weight one to each set of irreducible words of a given length. This confirms a conjecture of Leader, Letzter, Narayanan and Walters. In more general terms, we actually prove that strongly $k$-product-free sets have maximum density $1/k$ in terms of the said measure. The bounds are tight.

Minimum vertex degree conditions for loose spanning trees in 3-graphs

Yanitsa Pehova, Kalina Petrova — Mon, 28 Aug 2023 00:00:00 +0200

In 1995, Komlós, Sárközy and Szemerédi showed that for large $n$, every $n$-vertex graph with minimum degree at least $(1/2 + \gamma)n$ contains all spanning trees of bounded degree. We consider a generalization of this result to loose spanning hypertrees, that is, linear hypergraphs obtained by successively appending edges sharing a single vertex with a previous edge, in 3-graphs. We show that for all $\gamma$ and $\Delta$, and $n$ large, every $n$-vertex 3-uniform hypergraph of minimum vertex degree $(5/9 + \gamma)\binom{n}{2}$ contains every loose spanning tree with maximum vertex degree $\Delta$. This bound is asymptotically tight, since some loose trees contain perfect matchings.

Strengthening the Directed Brooks‘ Theorem for oriented graphs and consequences on digraph redicolouring.

Lucas Picasarri-Arrieta — Mon, 28 Aug 2023 00:00:00 +0200

Let $D=(V,A)$ be a digraph. We define $\Delta_{\max}(D)$ as the maximum of $\{ \max(d^+(v),d^-(v)) \mid v \in V \}$ and $\Delta_{\min}(D)$ as the maximum of $\{ \min(d^+(v),d^-(v)) \mid v \in V \}$. It is known that the dichromatic number of $D$ is at most $\Delta_{\min}(D) + 1$. In this work, we prove that every digraph $D$ which has dichromatic number exactly $\Delta_{\min}(D) + 1$ must contain the directed join of $\overleftrightarrow{K_r}$ and $\overleftrightarrow{K_s}$ for some $r,s$ such that $r+s = \Delta_{\min}(D) + 1$, except if $\Delta_{\min}(D) = 2$ in which case $D$ must contain a digon. In particular, every oriented graph $\vec{G}$ with $\Delta_{\min}(\vec{G}) \geq 2$ has dichromatic number at most $\Delta_{\min}(\vec{G})$. Let $\vec{G}$ be an oriented graph of order $n$ such that $\Delta_{\min}(\vec{G}) \leq 1$. Given two 2-dicolourings of $\vec{G}$, we show that we can transform one into the other in at most $n$ steps, by recolouring one vertex at each step while maintaining a dicolouring at any step. Furthermore, we prove that, for every oriented graph $\vec{G}$ on $n$ vertices, the distance between two $k$-dicolourings is at most $2\Delta_{\min}(\vec{G})n$ when $k\geq \Delta_{\min}(\vec{G}) + 1$. We then extend a theorem of Feghali, Johnson and Paulusma to digraphs. We prove that, for every digraph $D$ with $\Delta_{\max}(D) = \Delta \geq 3$ and every $k\geq \Delta +1$, the $k$-dicolouring graph of $D$ consists of isolated vertices and at most one further component that has diameter at most $c_{\Delta}n^2$, where $c_{\Delta} = O(\Delta^2)$ is a constant depending only on $\Delta$.

On asymptotic confirmation of the Faudree-Lehel Conjecture on the irregularity strength of graphs

Jakub Przybyło, Fan Wei — Mon, 28 Aug 2023 00:00:00 +0200

We call a multigraph irregular if it has pairwise distinct vertex degrees. No nontrivial (simple) graph is thus irregular. The irregularity strength of a graph $G$, $s(G)$, is a specific measure of the ``level of irregularity‘‘ of $G$. It might be defined as the least $k$ such that one may obtain an irregular multigraph of $G$ by multiplying any selected edges of $G$, each into at most $k$ its copies. In other words, $s(G)$ is the least $k$ admitting a $\{1,2,\ldots,k\}$-weighting of the edges of $G$ assuring distinct weighted degrees for all the vertices, where the weighted degree of a vertex is the sum of its incident weights. The most well-known open problem concerning this graph invariant is the conjecture posed in 1987 by Faudree and Lehel that there exists an absolute constant $C$ such that $s(G)\leq \frac{n}{d}+C$ for each $d$-regular graph $G$ with $n$ vertices and $d\geq 2$, whereas a straightforward counting argument implies that $s(G)\geq \frac{n}{d}+\frac{d-1}{d}$. Until very recently this conjecture had remained widely open. We shall discuss recent results confirming it asymptotically, up to a lower order term. If time permits we shall also mention a few related problems, such as the 1-2-3 Conjecture or the concept of irregular subgraphs, introduced recently by Alon and Wei, and progress in research concerning these.

On Hypergraph Supports.

Rajiv Raman, Karamjeet Singh — Mon, 28 Aug 2023 00:00:00 +0200

Let $\mathcal{H}=(X,\mathcal{E})$ be a hypergraph. A support is a graph $Q$ on $X$ such that for each $E\in\mathcal{E}$, the subgraph of $Q$ on the elements in $E$ is connected. We consider hypergraphs defined on a host graph. Given a graph $G=(V,E)$, with $c:V\to\{\mathbf{r},\mathbf{b}\}$ and a collection of connected subgraphs $\mathcal{H}$ of $G$, a primal support is a graph $Q$ on $\mathbf{b}(V)$ such that for each $H\in \mathcal{H}$, the subgraph $Q[\mathbf{b}(H)]$ on vertices $\mathbf{b}(H)=H\cap c^{-1}(\mathbf{b})$ is connected. A dual support is a graph $Q^*$ on $\mathcal{H}$ s.t. for each $v\in X$, the subgraph $Q^*[\mathcal{H}_v]$ is connected, where $\mathcal{H}_v=\{H\in\mathcal{H}: v\in H\}$. We present sufficient conditions on the host graph and hyperedges so that the resulting support comes from a restricted family. We primarily study two classes of graphs: $(1)$ If the host graph has genus $g$ and the hypergraphs satisfy a topological condition of being cross-free, then there is a primal and a dual support of genus at most $g$. $(2)$ If the host graph has treewidth $t$ and the hyperedges satisfy a combinatorial condition of being non-piercing, then there exist primal and dual supports of treewidth $O(2^t)$. We show that this exponential blow-up is sometimes necessary. As an intermediate case, we also study the case when the host graph is outerplanar. Finally, we show applications of our results to packing and covering, and coloring problems on geometric hypergraphs.

The Rado Multiplicity Problem in Vector Spaces over Finite Fields

Juanjo Rué, Christoph Spiegel — Mon, 28 Aug 2023 00:00:00 +0200

We study an analogue of the Ramsey multiplicity problem for additive structures, establishing the minimum number of monochromatic $3$-APs in $3$-colorings of $\mathbb{F}_3^n$ and 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. \cite{CummingsEtAl_2013} in extremal graph theory and the latter improves upon results of Saad and Wolf \cite{SaadWolf_2017}. Lower bounds are notably obtained by extending the flag algebra calculus of Razborov \cite{razborov2007flag}.

Unified study of the phase transition for block-weighted random planar maps

Zéphyr Salvy — Mon, 28 Aug 2023 00:00:00 +0200

In [Fleurat, Salvy 2023], we introduced a model of block-weighted random maps that undergoes a phase transition as the density of separating elements changes. The purpose of this note is to demonstrate that the methodology we developed can be extended to many other families of maps. We prove that a phase transition exists and provide detailed information about the size of the largest blocks in each regime.

The Turán Number of Surfaces

Maya Sankar — Mon, 28 Aug 2023 00:00:00 +0200

We show that there is a constant $c$ such that any 3-uniform hypergraph ${\mathcal H}$ with $n$ vertices and at least $cn^{5/2}$ edges contains a triangulation of the real projective plane as a sub-hypergraph. This resolves a conjecture of Kupavskii, Polyanskii, Tomon, and Zakharov. Furthermore, our work, combined with prior results, asymptotically determines the Turán number of all surfaces.

On universal singular exponents in equations with one catalytic parameter of order one

Gilles Schaeffer — Mon, 28 Aug 2023 00:00:00 +0200

Equations with one catalytic variable and one univariate unkown, also known as discrete difference equations of order one, form a familly of combinatorially relevant functional equations first discussed in full generality by Bousquet-Mélou and Jehanne (2006) who proved that their power serie solutions are algebraic. Drmota, Noy and Yu (2022) recently showed that in the non linear case the singular expansions of these series have a universal dominant term of order 3/2, as opposed to the dominant square root term of generic $\mathbb{N}$-algebraic series. Their direct analysis of the cancellation underlying this behavior is a tour de force of singular analysis. We show that the result can instead be given a straightforward explanation by showing that the derivative of the solution series conforms to the standard square root singular behavior. Consequences also include an atypical, but generic in this situation, $n^{^{5 / 4}}$ asymptotic behavior for the cumulated values of the underlying catalytic parameter.

A new approach for the Brown-Erdős-Sós problem

Asaf Shapira, Mykhaylo Tyomkyn — Mon, 28 Aug 2023 00:00:00 +0200

The celebrated Brown-Erdős-Sós conjecture states that for every fixed $e$, every $3$-uniform hypergraph with $\Omega(n^2)$ edges contains $e$ edges spanned by $e+3$ vertices. Up to this date all the approaches towards resolving this problem relied on highly involved applications of the hypergraph regularity method, and yet they supplied only approximate versions of the conjecture, producing $e$ edges spanned by $e+O(\log e/\log \log e)$ vertices. We describe a completely different approach, which reduces the problem to a variant of another well-known conjecture in extremal graph theory. A resolution of the latter would resolve the Brown-Erdős-Sós conjecture up to an absolute additive constant.

Semidegree, edge density and antidirected subgraphs

Maya Stein, Camila Zárate-Guerén — Mon, 28 Aug 2023 00:00:00 +0200

An oriented graph is called anti-directed if it has no directed path with $2$ edges. We prove that asymptotically, any oriented graph $D$ of minimum semidegree greater than $\frac k2$ contains every balanced antidirected tree of bounded degree and with $k$ edges, and $D$ also contains every antidirected subdivision $H$ of a sufficiently small complete graph $K_h$, with a mild restriction on the lengths of the antidirected paths in $H$ replacing the edges of $K_h$, and with $H$ having a total of $k$ edges. Further, we address a conjecture of Addario-Berry, Havet, Linhares Sales, Reed and Thomassé stating that every digraph on $n$ vertices and with more than $(k-1)n$ edges contains all antidirected trees with $k$ edges. We show that their conjecture is asymptotically true in oriented graphs for balanced antidirected trees of bounded degree and size linear in $n$.

The structure of Sidon set systems

Maximilian Wötzel — Mon, 28 Aug 2023 00:00:00 +0200

A family $\mathcal{F}\subset 2^G$ of subsets of an abelian group $G$ is a Sidon system if the sumsets $A+B$ with $A,B\in \mathcal{F}$ are pairwise distinct. Cilleruelo, Serra and the author previously proved that the maximum size $F_k(n)$ of a Sidon system consisting of $k$-subsets of the first $n$ positive integers satisfies $C_k n^{k-1}\leq F_k(n) \leq \binom{n-1}{k-1}+n-k$ for some constant $C_k$ only depending on $k$. We close the gap by proving an essentially tight structural result that in particular implies $F_k(n)\geq (1-o(1))\binom{n}{k-1}$. We also use this to establish a result about the size of the largest Sidon system in the binomial random family $\binom{[n]}{k}_p$. Extensions to $h$-fold sumsets for any fixed $h\geq 3$ are also obtained.

Minimum non-chromatic-λ-choosable graphs

Jialu Zhu, Xuding Zhu — Mon, 28 Aug 2023 00:00:00 +0200

For a multi-set $\lambda=\{k_1,k_2, \ldots, k_q\}$ of positive integers, let $k_{\lambda} = \sum_{i=1}^q k_i$. A $\lambda$-list assignment of $G$ is a list assignment $L$ of $G$ such that the colour set $\bigcup_{v \in V(G)}L(v)$ can be partitioned into the disjoint union $C_1 \cup C_2 \cup \ldots \cup C_q$ of $q$ sets so that for each $i$ and each vertex $v$ of $G$, $|L(v) \cap C_i| \ge k_i$. We say $G$ is $\lambda$-choosable if $G$ is $L$-colourable for any $\lambda$-list assignment $L$ of $G$. The concept of $\lambda$-choosability puts $ k$-colourability and $k$-choosability in the same framework: If $\lambda = \{k\}$, then $\lambda$-choosability is equivalent to $k$-choosability; if $\lambda$ consists of $k $ copies of $1$, then $\lambda$-choosability is equivalent to $k $-colourability. If $G$ is $\lambda$-choosable, then $G$ is $k_{\lambda}$-colourable. On the other hand, there are $k_{\lambda}$-colourable graphs that are not $\lambda$-choosable, provided that $\lambda$ contains an integer larger than $1$. Let $\phi(\lambda)$ be the minimum number of vertices in a $k_{\lambda}$-colourable non-$\lambda$-choosable graph. This paper determines the value of $\phi(\lambda)$ for all $\lambda$.

European Conference on Combinatorics, Graph Theory and Applications

Foreword

On the number of tangencies among 1-intersecting curves

Partition Universality for Hypergraphs of Bounded Degeneracy and Degree

Expander graphs, strong blocking sets and minimal codes

Moderate deviations of triangle counts – the lower tail

Constructing Hamilton cycles and perfect matchings efficiently

Algorithms for subgraph complementation to some classes of graphs

A lower bound for set-colouring Ramsey numbers

Type-respecting amalgamation and big Ramsey degrees

Cycles of every length and orientation in randomly perturbed digraphs

Tiling problems in edge-ordered graphs

Graphs without a rainbow path of length 3

Directed graphs without rainbow triangles

On ordered Ramsey numbers of matchings versus triangles

On the sizes of t-intersecting k-chain-free families

Isoperimetric stability in lattices

Nonrepetitive colorings of Rd

Exact antichain saturation numbers via a generalisation of a result of Lehman-Ron

Chromatic number of intersection graphs of segments with two slopes

Big Ramsey degrees in the metric setting

On a recolouring version of Hadwiger’s conjecture

The Localization game on locally finite trees

Twin-width and permutations

Independent dominating sets in planar triangulations

Biclique immersions in graphs with independence number 2

A resolution of the Kohayakawa--Kreuter conjecture for the majority of cases

Tight path, what is it (Ramsey-)good for? Absolutely (almost) nothing!

Effective bounds for induced size-Ramsey numbers of cycles

Single-conflict colorings of degenerate graphs

Monadic NIP in monotone classes of relational structures

Decomposition horizons: from graph sparsity to model-theoretic dividing lines

Countable ultrahomogeneous 2-colored graphs consisting of disjoint unions of cliques

Raising the roof on the threshold for Szemerédi‘s theorem with random differences

Random restrictions of high-rank tensors and polynomial maps

Strict Erdős-Ko-Rado for simplicial complexes

Exact enumeration of graphs and bipartite graphs with degree constraints

A precise condition for independent transversals in bipartite covers

Chordal graphs with bounded tree-width

A compactification of the set of sequences of positive real numbers with applications to limits of graphs

A direct bijection between two-stack sortable permutations and fighting fish

Counting tournament score sequences

The k-XORSAT threshold revisited

Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P4

Higher degree Erdős distinct evaluations problem

Monochromatic configurations on a circle

Beyond the Erdős–Sós conjecture

Dispersion on the Complete Graph

The root cluster after percolation on preferential attachment trees

Cycles through two edges in signed graphs

Powers of planar graphs, product structure, and blocking partitions

When is Cartesian product a Cayley graph?

A generalization of Bondy’s pancyclicity theorem

Chvátal-Erdős condition for pancyclicity

Tower gaps in multicolour Ramsey numbers

On the minimum number of inversions to make a digraph k-(arc-)strong

Precoloring extension in planar near-Eulerian-triangulations

Maximum genus orientable embeddings from circuit decompositions of dense eulerian graphs and digraphs

Tangled Paths: A Random Graph Model from Mallows Permutations

Cop number of random k-uniform hypergraphs

The structure of quasi-transitive graphs avoiding a minor with applications to the domino problem

Sharp threshold for embedding balanced spanning trees in random geometric graphs

Odd-Sunflowers

Upper bounds on Ramsey numbers for vector spaces over finite fields

A general bound for the induced poset saturation problem

Extremal number of graphs from geometric shapes

The dimension of the feasible region of pattern densities

On the structure and values of betweenness centrality in dense betweenness-uniform graphs

The Minimum Degree Removal Lemma Thresholds

Hamilton cycles in pseudorandom graphs

Random perfect matchings in regular graphs

Forcing Generalized Quasirandom Graphs Efficiently

Refined list version of Hadwiger’s Conjecture

A general approach to transversal versions of Dirac-type theorems

The maximum number of copies of an even cycle in a planar graph

3-uniform linear hypergraphs without a long Berge path

Rooting algebraic vertices of convergent sequences

Colouring complete multipartite and Kneser-type digraphs

The hitting time of clique factors

Roudneff‘s Conjecture in Dimension 4

Nonrepetitive colorings of R^d

Proving a directed analogue of the Gyárfás-Sumner conjecture for orientations of P₄

Finding pairwise disjoint vector pairs in F₂ⁿ with a prescribed sequence of differences