More Like this

1. Hyperbolic families and coloring graphs on surfaces

   https://doi.org/https://doi.org/10.1090/btran/26  

   Postle, Luke; Thomas, Robin (December 2018, Transactions of the American Mathematical Society. Series B)

   We develop a theory of linear isoperimetric inequalities for graphs on surfaces and apply it to coloring problems, as follows. Let $ G$ be a graph embedded in a fixed surface $$ \Sigma $$ of genus $ g$ and let $$ L=(L(v):v\in V(G))$$ be a collection of lists such that either each list has size at least five, or each list has size at least four and $ G$ is triangle-free, or each list has size at least three and $ G$ has no cycle of length four or less. An $ L$-coloring of $ G$ is a mapping $$ \phi $$ with domain $ V(G)$ such that $$ \phi (v)\in L(v)$$ for every $$ v\in V(G)$$ and $$ \phi (v)\ne \phi (u)$$ for every pair of adjacent vertices $$ u,v\in V(G)$$. We prove if every non-null-homotopic cycle in $ G$ has length $$ \Omega (\log g)$$, then $ G$ has an $ L$-coloring, if $ G$ does not have an $ L$-coloring, but every proper subgraph does (``$ L$-critical graph''), then $$ \vert V(G)\vert=O(g)$$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and a set $$ X\subseteq V(G)$$ of vertices that are pairwise at distance $$ \Omega (1)$$ is precolored from the corresponding lists, then the precoloring extends to an $ L$-coloring of $ G$, if every non-null-homotopic cycle in $ G$ has length $$ \Omega (g)$$, and the graph $ G$ is allowed to have crossings, but every two crossings are at distance $$ \Omega (1)$$, then $ G$ has an $ L$-coloring, if $ G$ has at least one $ L$-coloring, then it has at least $$ 2^{\Omega (\vert V(G)\vert)}$$ distinct $ L$-colorings. We show that the above assertions are consequences of certain isoperimetric inequalities satisfied by $ L$-critical graphs, and we study the structure of families of embedded graphs that satisfy those inequalities. It follows that the above assertions hold for other coloring problems, as long as the corresponding critical graphs satisfy the same inequalities. 

   more » « less
2. Forbidding $$K_{2,t}$$ Traces in Triple Systems

   https://doi.org/10.37236/9760  

   Luo, Ruth; Spiro, Sam (April 2021, The Electronic Journal of Combinatorics)

   Let $$H$$ and $$F$$ be hypergraphs. We say $$H$$ {\em contains $$F$$ as a trace} if there exists some set $$S \subseteq V(H)$$ such that $$H|_S:=\{E\cap S: E \in E(H)\}$$ contains a subhypergraph isomorphic to $$F$$. In this paper we give an upper bound on the number of edges in a $$3$$-uniform hypergraph that does not contain $$K_{2,t}$$ as a trace when $$t$$ is large. In particular, we show that $$\lim_{t\to \infty}\lim_{n\to \infty} \frac{\mathrm{ex}(n, \mathrm{Tr}_3(K_{2,t}))}{t^{3/2}n^{3/2}} = \frac{1}{6}.$$ Moreover, we show $$\frac{1}{2} n^{3/2} + o(n^{3/2}) \leqslant \mathrm{ex}(n, \mathrm{Tr}_3(C_4)) \leqslant \frac{5}{6} n^{3/2} + o(n^{3/2})$$. 

   more » « less
3. Extremal Numbers and Sidorenko’s Conjecture

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

   Conlon, David; Lee, Joonkyung; Sidorenko, Alexander (April 2024, International Mathematics Research Notices)

   Abstract Sidorenko’s conjecture states that, for all bipartite graphs $$H$$, quasirandom graphs contain asymptotically the minimum number of copies of $$H$$ taken over all graphs with the same order and edge density. While still open for graphs, the analogous statement is known to be false for hypergraphs. We show that there is some advantage in this, in that if Sidorenko’s conjecture does not hold for a particular $$r$$-partite $$r$$-uniform hypergraph $$H$$, then it is possible to improve the standard lower bound, coming from the probabilistic deletion method, for its extremal number $$\textrm{ex}(n,H)$$, the maximum number of edges in an $$n$$-vertex $$H$$-free $$r$$-uniform hypergraph. With this application in mind, we find a range of new counterexamples to the conjecture for hypergraphs, including all linear hypergraphs containing a loose triangle and all $$3$$-partite $$3$$-uniform tight cycles. 

   more » « less
4. A Hypergraph Analog of Dirac's Theorem for Long Cycles in 2-Connected Graphs, II: Large Uniformities

   https://doi.org/10.37236/12486  

   Kostochka, Alexandr; Luo, Ruth; McCourt, Grace (January 2025, The Electronic Journal of Combinatorics)

   Dirac proved that each $$n$$-vertex $$2$$-connected graph with minimum degree $$k$$ contains a cycle of length at least $$\min\{2k, n\}$$. We obtain analogous results for Berge cycles in hypergraphs. Recently, the authors proved an exact lower bound on the minimum degree ensuring a Berge cycle of length at least $$\min\{2k, n\}$$ in $$n$$-vertex $$r$$-uniform $$2$$-connected hypergraphs when $$k \geq r+2$$. In this paper we address the case $$k \leq r+1$$ in which the bounds have a different behavior. We prove that each $$n$$-vertex $$r$$-uniform $$2$$-connected hypergraph $$H$$ with minimum degree $$k$$ contains a Berge cycle of length at least $$\min\{2k,n,|E(H)|\}$$. If $$|E(H)|\geq n$$, this bound coincides with the bound of the Dirac's Theorem for 2-connected graphs. 

   more » « less
5. 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