An official website of the United States government
ABSTRACT For ak‐uniform hypergraph and a positive integer , the Ramsey number denotes the minimum such that every ‐vertex ‐free ‐uniform hypergraph contains an independent set of vertices. A hypergraph isslowly growingif there is an ordering of its edges such that for each . We prove that if is fixed and is any non‐k‐partite slowly growing ‐uniform hypergraph, then for ,In particular, we deduce that the off‐diagonal Ramsey number is of order , where is the triple system . This is the only 3‐uniform Berge triangle for which the polynomial power of its off‐diagonal Ramsey number was not previously known. Our constructions use pseudorandom graphs and hypergraph containers.
more »
« less
Off-diagonal book Ramsey numbers
Abstract The book graph $$B_n ^{(k)}$$ consists of $$n$$ copies of $$K_{k+1}$$ joined along a common $$K_k$$ . In the prequel to this paper, we studied the diagonal Ramsey number $$r(B_n ^{(k)}, B_n ^{(k)})$$ . Here we consider the natural off-diagonal variant $$r(B_{cn} ^{(k)}, B_n^{(k)})$$ for fixed $$c \in (0,1]$$ . In this more general setting, we show that an interesting dichotomy emerges: for very small $$c$$ , a simple $$k$$ -partite construction dictates the Ramsey function and all nearly-extremal colourings are close to being $$k$$ -partite, while, for $$c$$ bounded away from $$0$$ , random colourings of an appropriate density are asymptotically optimal and all nearly-extremal colourings are quasirandom. Our investigations also open up a range of questions about what happens for intermediate values of $$c$$ .
more »
« less
- Award ID(s):
- 2154129
- PAR ID:
- 10429250
- Date Published:
- Journal Name:
- Combinatorics, Probability and Computing
- Volume:
- 32
- Issue:
- 3
- ISSN:
- 0963-5483
- Page Range / eLocation ID:
- 516 to 545
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
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
-
Abstract Recently, Dvořák, Norin, and Postle introduced flexibility as an extension of list coloring on graphs (J Graph Theory 92(3):191–206, 2019, https://doi.org/10.1002/jgt.22447 ). In this new setting, each vertex v in some subset of V ( G ) has a request for a certain color r ( v ) in its list of colors L ( v ). The goal is to find an L coloring satisfying many, but not necessarily all, of the requests. The main studied question is whether there exists a universal constant $$\varepsilon >0$$ ε > 0 such that any graph G in some graph class $$\mathscr {C}$$ C satisfies at least $$\varepsilon$$ ε proportion of the requests. More formally, for $$k > 0$$ k > 0 the goal is to prove that for any graph $$G \in \mathscr {C}$$ G ∈ C on vertex set V , with any list assignment L of size k for each vertex, and for every $$R \subseteq V$$ R ⊆ V and a request vector $$(r(v): v\in R, ~r(v) \in L(v))$$ ( r ( v ) : v ∈ R , r ( v ) ∈ L ( v ) ) , there exists an L -coloring of G satisfying at least $$\varepsilon |R|$$ ε | R | requests. If this is true, then $$\mathscr {C}$$ C is called $$\varepsilon$$ ε - flexible for lists of size k . Choi, Clemen, Ferrara, Horn, Ma, and Masařík (Discrete Appl Math 306:20–132, 2022, https://doi.org/10.1016/j.dam.2021.09.021 ) introduced the notion of weak flexibility , where $$R = V$$ R = V . We further develop this direction by introducing a tool to handle weak flexibility. We demonstrate this new tool by showing that for every positive integer b there exists $$\varepsilon (b)>0$$ ε ( b ) > 0 so that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_b$$ K 4 , C 5 , C 6 , C 7 , B b is weakly $$\varepsilon (b)$$ ε ( b ) -flexible for lists of size 4 (here $$K_n$$ K n , $$C_n$$ C n and $$B_n$$ B n are the complete graph, a cycle, and a book on n vertices, respectively). We also show that the class of planar graphs without $$K_4, C_5 , C_6 , C_7, B_5$$ K 4 , C 5 , C 6 , C 7 , B 5 is $$\varepsilon$$ ε -flexible for lists of size 4. The results are tight as these graph classes are not even 3-colorable.more » « less
-
Abstract The hedgehog H t is a 3-uniform hypergraph on vertices $$1, \ldots ,t + \left({\matrix{t \cr 2}}\right)$$ such that, for any pair ( i , j ) with 1 ≤ i < j ≤ t , there exists a unique vertex k > t such that { i , j , k } is an edge. Conlon, Fox and Rödl proved that the two-colour Ramsey number of the hedgehog grows polynomially in the number of its vertices, while the four-colour Ramsey number grows exponentially in the square root of the number of vertices. They asked whether the two-colour Ramsey number of the hedgehog H t is nearly linear in the number of its vertices. We answer this question affirmatively, proving that r ( H t ) = O ( t 2 ln t ).more » « less
-
Abstract The list Ramsey number , recently introduced by Alon, Bucić, Kalvari, Kuperwasser, and Szabó, is a list‐coloring variant of the classical Ramsey number. They showed that if is a fixed ‐uniform hypergraph that is not ‐partite and the number of colors goes to infinity, . We prove that if and only if is not ‐partite.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/s0963548322000360
