More Like this

1. A Unified Proof of Conjectures on Cycle Lengths in Graphs

   https://doi.org/10.1093/imrn/rnaa324  

   Gao, Jun; Huo, Qingyi; Liu, Chun-Hung; Ma, Jie (January 2021, International Mathematics Research Notices)

   null (Ed.)

   Abstract In this paper, we prove a tight minimum degree condition in general graphs for the existence of paths between two given endpoints whose lengths form a long arithmetic progression with common difference one or two. This allows us to obtain a number of exact and optimal results on cycle lengths in graphs of given minimum degree, connectivity or chromatic number. More precisely, we prove the following statements by a unified approach: 1. Every graph $$G$$ with minimum degree at least $k+1$ contains cycles of all even lengths modulo $$k$$; in addition, if $$G$$ is $$2$$-connected and non-bipartite, then it contains cycles of all lengths modulo $$k$$. 2. For all $$k\geq 3$$, every $$k$$-connected graph contains a cycle of length zero modulo $$k$$. 3. Every $$3$$-connected non-bipartite graph with minimum degree at least $k+1$ contains $$k$$ cycles of consecutive lengths. 4. Every graph with chromatic number at least $k+2$ contains $$k$$ cycles of consecutive lengths. The 1st statement is a conjecture of Thomassen, the 2nd is a conjecture of Dean, the 3rd is a tight answer to a question of Bondy and Vince, and the 4th is a conjecture of Sudakov and Verstraëte. All of the above results are best possible. 

   more » « less
2. The Implicit Graph Conjecture is False

   https://doi.org/10.1109/FOCS54457.2022.00109  

   Hatami, Hamed; Hatami, Pooya (October 2022, Annual Symposium on Foundations of Computer Science)

   An efficient implicit representation of an n-vertex graph G in a family F of graphs assigns to each vertex of G a binary code of length O(log n) so that the adjacency between every pair of vertices can be determined only as a function of their codes. This function can depend on the family but not on the individual graph. Every family of graphs admitting such a representation contains at most 2^O(n log(n)) graphs on n vertices, and thus has at most factorial speed of growth. The Implicit Graph Conjecture states that, conversely, every hereditary graph family with at most factorial speed of growth admits an efficient implicit representation. We refute this conjecture by establishing the existence of hereditary graph families with factorial speed of growth that require codes of length n^Ω(1). 

   more » « less
3. Induced subgraphs and tree decompositions III. Three-path-configurations and logarithmic treewidth

   https://doi.org/10.19086/aic.2022.6  

   Chudnovsky, Maria; Abrishami, Tara; Hajebi, Sepehr; Spirkl, Sophie (September 2022, Advances in Combinatorics)

   A _theta_ is a graph consisting of two non-adjacent vertices and three internally disjoint paths between them, each of length at least two. For a family $$\mathcal{H}$$ of graphs, we say a graph $$G$$ is $$\mathcal{H}$$-_free_ if no induced subgraph of $$G$$ is isomorphic to a member of $$\mathcal{H}$$. We prove a conjecture of Sintiari and Trotignon, that there exists an absolute constant $$c$$ for which every (theta, triangle)-free graph $$G$$ has treewidth at most $$c\log (|V(G)|)$$. A construction by Sintiari and Trotignon shows that this bound is asymptotically best possible, and (theta, triangle)-free graphs comprise the first known hereditary class of graphs with arbitrarily large yet logarithmic treewidth.Our main result is in fact a generalization of the above conjecture, that treewidth is at most logarithmic in $|V(G)|$ for every graph $$G$$ excluding the so-called _three-path-configurations_ as well as a fixed complete graph. It follows that several NP-hard problems such as Stable Set, Vertex Cover, Dominating Set and $$k$$-Coloring (for fixed $$k$$) admit polynomial time algorithms in graphs excluding the three-path-configurations and a fixed complete graph. 

   more » « less
4. A completion of the proof of the Edge-statistics Conjecture

   https://doi.org/10.19086/aic.12047  

   Fox, Jacob; Sauermann, Lisa (February 2020, Advances in Combinatorics)

   Extremal combinatorics often deals with problems of maximizing a specific quantity related to substructures in large discrete structures. The first question of this kind that comes to one's mind is perhaps determining the maximum possible number of induced subgraphs isomorphic to a fixed graph $$H$$ in an $$n$$-vertex graph. The asymptotic behavior of this number is captured by the limit of the ratio of the maximum number of induced subgraphs isomorphic to $$H$$ and the number of all subgraphs with the same number vertices as $$H$$; this quantity is known as the _inducibility_ of $$H$$. More generally, one can define the inducibility of a family of graphs in the analogous way.Among all graphs with $$k$$ vertices, the only two graphs with inducibility equal to one are the empty graph and the complete graph. However, how large can the inducibility of other graphs with $$k$$ vertices be? Fix $$k$$, consider a graph with $$n$$ vertices join each pair of vertices independently by an edge with probability $$\binom{k}{2}^{-1}$$. The expected number of $$k$$-vertex induced subgraphs with exactly one edge is $$e^{-1}+o(1)$$. So, the inducibility of large graphs with a single edge is at least $$e^{-1}+o(1)$$. This article establishes that this bound is the best possible in the following stronger form, which proves a conjecture of Alon, Hefetz, Krivelevich and Tyomkyn: the inducibility of the family of $$k$$-vertex graphs with exactly $$l$$ edges where $$0<\binom{k}{2}$$ is at most $$e^{-1}+o(1)$$. The example above shows that this is tight for $l=1$ and it can be also shown to be tight for $l=k-1$. The conjecture was known to be true in the regime where $$l$$ is superlinearly bounded away from $$0$$ and $$\binom{k}{2}$$, for which the sum of the inducibilities goes to zero, and also in the regime where $$l$$ is bounded away from $$0$$ and $$\binom{k}{2}$$ by a sufficiently large linear function. The article resolves the hardest cases where $$l$$ is linearly close to $$0$$ or close to $$\binom{k}{2}$$, and provides generalizations to hypergraphs. 

   more » « less
5. Equitable colourings of Borel graphs

   https://doi.org/10.1017/fmp.2021.12  

   Bernshteyn, Anton; Conley, Clinton T. (January 2021, Forum of Mathematics, Pi)

   Abstract Hajnal and Szemerédi proved that if G is a finite graph with maximum degree $$\Delta $$ , then for every integer $$k \geq \Delta +1$$ , G has a proper colouring with k colours in which every two colour classes differ in size at most by $$1$$ ; such colourings are called equitable. We obtain an analogue of this result for infinite graphs in the Borel setting. Specifically, we show that if G is an aperiodic Borel graph of finite maximum degree $$\Delta $$ , then for each $$k \geq \Delta + 1$$ , G has a Borel proper k -colouring in which every two colour classes are related by an element of the Borel full semigroup of G . In particular, such colourings are equitable with respect to every G -invariant probability measure. We also establish a measurable version of a result of Kostochka and Nakprasit on equitable $$\Delta $$ -colourings of graphs with small average degree. Namely, we prove that if $$\Delta \geq 3$$ , G does not contain a clique on $$\Delta + 1$$ vertices and $$\mu $$ is an atomless G -invariant probability measure such that the average degree of G with respect to $$\mu $$ is at most $$\Delta /5$$ , then G has a $$\mu $$ -equitable $$\Delta $$ -colouring. As steps toward the proof of this result, we establish measurable and list-colouring extensions of a strengthening of Brooks’ theorem due to Kostochka and Nakprasit. 

   more » « less