More Like this

1. On Ramsey numbers of hedgehogs

   https://doi.org/10.1017/s0963548319000312  

   Fox, Jacob ; Li, Ray ( January 2020 , Combinatorics, Probability and Computing)

   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
2. A note on the Erdős-Hajnal hypergraph Ramsey problem

   https://doi.org/10.1090/proc/15839  

   Mubayi, Dhruv ; Suk, Andrew ; Zhu, Emily ( September 2022 , Proceedings of the American Mathematical Society)

   We show that there is an absolute constant c > 0 c>0 such that the following holds. For every n > 1 n > 1 , there is a 5-uniform hypergraph on at least 2 2 c n 1 / 4 2^{2^{cn^{1/4}}} vertices with independence number at most n n , where every set of 6 vertices induces at most 3 edges. The double exponential growth rate for the number of vertices is sharp. By applying a stepping-up lemma established by the first two authors, analogous sharp results are proved for k k -uniform hypergraphs. This answers the penultimate open case of a conjecture in Ramsey theory posed by Erdős and Hajnal in 1972. 

   more » « less
3. THE ERDŐS–SZEKERES PROBLEM AND AN INDUCED RAMSEY QUESTION

   https://doi.org/10.1112/S0025579319000135  

   Mubayi, Dhruv ; Suk, Andrew ( January 2019 , Mathematika)

   Motivated by the Erdős–Szekeres convex polytope conjecture in $\mathbb{R}^{d}$ , we initiate the study of the following induced Ramsey problem for hypergraphs. Given integers $n>k\geqslant 5$ , what is the minimum integer $g_{k}(n)$ such that any $k$ -uniform hypergraph on $g_{k}(n)$ vertices with the property that any set of $k+1$ vertices induces 0, 2, or 4 edges, contains an independent set of size $n$ . Our main result shows that $g_{k}(n)>2^{cn^{k-4}}$ , where $c=c(k)$ . 

   more » « less
4. Multicolor list Ramsey numbers grow exponentially

   https://doi.org/10.1002/jgt.22832  

   Fox, Jacob ; He, Xiaoyu ; Luo, Sammy ; Xu, Max Wenqiang ( April 2022 , Journal of Graph Theory)

   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
5. Improved Bounds on a Generalization of Tuza's Conjecture

   https://doi.org/10.37236/10829  

   Basit, Abdul ; McGinnis, Daniel ; Simmons, Henry ; Sinnwell, Matt ; Zerbib, Shira ( October 2022 , The Electronic Journal of Combinatorics)

   For an $r$-uniform hypergraph $H$, let $\nu^{(m)}(H)$ denote the maximum size of a set $M$ of edges in $H$ such that every two edges in $M$ intersect in less than $m$ vertices, and let $\tau^{(m)}(H)$ denote the minimum size of a collection $C$ of $m$-sets of vertices such that every edge in $H$ contains an element of $C$. The fractional analogues of these parameters are denoted by $\nu^{*(m)}(H)$ and $\tau^{*(m)}(H)$, respectively. Generalizing a famous conjecture of Tuza on covering triangles in a graph, Aharoni and Zerbib conjectured that for every $r$-uniform hypergraph $H$, $\tau^{(r-1)}(H)/\nu^{(r-1)}(H) \leq \lceil{\frac{r+1}{2}}\rceil$. In this paper we prove bounds on the ratio between the parameters $\tau^{(m)}$ and $\nu^{(m)}$, and their fractional analogues. Our main result is that, for every $r$-uniform hypergraph~$H$,\[ \tau^{*(r-1)}(H)/\nu^{(r-1)}(H) \le \begin{cases} \frac{3}{4}r - \frac{r}{4(r+1)} &\text{for }r\text{ even,}\\\frac{3}{4}r - \frac{r}{4(r+2)} &\text{for }r\text{ odd.} \\\end{cases} \]This improves the known bound of $r-1$.We also prove that, for every $r$-uniform hypergraph $H$, $\tau^{(m)}(H)/\nu^{*(m)}(H) \le \operatorname{ex}_m(r, m+1)$, where the Turán number $\operatorname{ex}_r(n, k)$ is the maximum number of edges in an $r$-uniform hypergraph on $n$ vertices that does not contain a copy of the complete $r$-uniform hypergraph on $k$ vertices. Finally, we prove further bounds in the special cases $(r,m)=(4,2)$ and $(r,m)=(4,3)$. 

   more » « less