Odd Ramsey numbers of multipartite graphs and hypergraphs
Nicholas Crawford, Emily Heath, Owen Henderschedt, Coy Schwieder, Shira Zerbib · 2025
Read Odd Ramsey numbers of multipartite graphs and hypergraphs by Nicholas Crawford, Emily Heath, Owen Henderschedt, Coy Schwieder, Shira Zerbib (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2507-19456.txt.
Introduction
Nicholas Crawford, Emily Heath, Owen Henderschedt, Coy Schwieder, and Shira Zerbib settle two cases of a coloring problem, in a 2025 paper. The odd Ramsey number asks for the fewest colors needed to paint one graph's edges under a parity rule. Every copy of a smaller graph inside must use some color an odd number of times. It is a parity twist on a classic Ramsey question.
For complete two-sided graphs, the team prove the answer grows as n over t, up to small error. They also solve the matching case for hypergraphs, where edges can join many vertices at once. That case is the first such result for hypergraphs. Both answers say the parity demand costs about as little as it possibly could.
Catalog record
| CREATOR | Nicholas Crawford, Emily Heath, Owen Henderschedt, Coy Schwieder, Shira Zerbib |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 83 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2507-19456
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Odd Ramsey numbers of multipartite graphs and hypergraphs Nicholas Crawford, Emily Heath, Owen Henderschedt, Coy Schwieder, Shira Zerbib Abstract Given a hypergraph G G and a subhypergraph H H of G G , the odd Ramsey number r o d d ( G , H ) r_{odd}(G,H) is the minimum number of colors needed to edge-color G G so that every copy of H H intersects some color class in an odd number of edges. Generalizing a result of [ 9 ] in two different ways, in this paper we prove r o d d ( K n , n , K 2 , t ) = n t + o ( n ) r_{odd}\left(K_{n,n},K_{2,t}\right)=\frac{n}{t}+o(n) for all t ≥ 2 t\geq 2 , and r o d d ( 𝒦 n , … , n ( k ) , 𝒦 1 , … , 1 , 2 , 2 ) = n 2 + o ( n ) r_{odd}\left({\mathcal{K}}^{(k)}_{n,\dots,n},{\mathcal{K}}_{1,\dots,1,2,2}\right)=\frac{n}{2}+o(n) for all k ≥ 2 k\geq 2 . The latter is the first result studying odd Ramsey numbers for hypergraphs. 1 Introduction The generalized Ramsey number f(K_{n},K_{p},q) , introduced by Erdős and Shelah [ 15 ] , is the minimum number of colors needed to edge-color the complete graph on n vertices so that every copy of K_{p} receives at least q colors. In the special case where q=2 , determining the generalized Ramsey numbers is equivalent to finding the diagonal Ramsey numbers R(p,p) . The problem can be further extended by replacing K_{n} and K_{p} by a hypergraph G and a subhypergraph H , respectively. Generalized Ramsey numbers have been studied extensively, see e.g., [ 2 , 5 , 6 , 8 , 11 , 12 , 13 , 16 , 23 , 24 ] . Recently, a variant of this problem has been introduced (see [ 1 , 7 , 9 , 25 ] ), asking for edge-colorings of G in which every copy C of H intersects some color class in an odd number of edges. In this case, we say that C has an odd color class . The minimum number of colors needed to produce such a coloring is called the odd Ramsey number , r_{odd}(G,H) . The study of r_{odd}(K_{n},H) was initially motivated by a work of Alon [ 1 ] on bounding the size of graph-codes . Given a family \mathcal{H} of graphs on vertex set [n] , an \mathcal{H} -(graph)-code is a collection of graphs \mathcal{F} on vertex set [n] such that the symmetric difference of any two members in {\mathcal{F}} is not a graph in \mathcal{H} . We denote the maximum possible cardinality of an \mathcal{H} -code by D_{\mathcal{H}}(n) , and the maximum possible density of an \mathcal{H} -code by d_{\mathcal{H}}(n)=\displaystyle\frac{D_{\mathcal{H}}(n)}{2^{\binom{n}{2}}}. In [ 25 ] , Versteegen showed that d_{H}(n)\geq r_{odd}(K_{n},H)^{-(e(H)/2+1)} . Thus, an upper bound on r_{odd}(K_{n},H) implies a lower bound for d_{H}(n) . In this context, Versteegen [ 25 ] obtained lower bounds on r_{odd}(K_{n},H) , when H is a K_{4} -free graph with an even number of edges. To this end, he used a modification of the explicit coloring in [ 11 ] . In [ 10 ] , Boyadzhiyska, Das, Lesgourgues, and Petrova established a connection between odd Ramsey numbers and results from coding theory. They showed r_{odd}(K_{n},K_{t,n-t})\in\{n-1,n\} , and (1+o(1))\left(\frac{n}{t}\right)^{1/\lceil s/2\rceil}\leq r_{odd}\left(K_{n},K_{s,t}\right)\leq O\left(n^{\frac{2s+2t-4}{st}}\right), where the upper bound is a direct corollary of the bound on f\left(K_{n},K_{s,t},\frac{st}{2}+1\right) from [ 2 ] . In [ 1 ] it was observed that a coloring in [ 11 ] modifying constructions in [ 13 , 23 ] implies r_{odd}(K_{n},K_{4})\leq n^{o(1)} . Bennett, Heath, and Zerbib [ 9 ] , and independently Ge, Xu, and Zhang [ 17 ] , then proved r_{odd}(K_{n},K_{5})\leq n^{o(1)} . The next non-trivial case, r_{odd}(K_{n},K_{8})\leq n^{o(1)} , was proven recently by Yip [ 26 ] . All these results were obtained by providing an explicit (deterministic) edge-coloring of K_{n} . For host graphs other than K_{n} , not much is known yet. In [ 9 ] it was shown that r_{odd}(K_{n,n},K_{2,2})=\frac{1}{2}n+o(n) . The proof used a probabilistic coloring technique that utilized the conflict-free hypergraph matching method (see below). Joos and Mubayi [ 20 ] used this technique to obtain an upper bound on the generalized Ramsey number f(K_{n},C_{4},3) . A similar approach has been used by various authors to obtain upper bounds on other generalized Ramsey numbers, see e.g., [ 4 , 9 , 22 , 19 ] . In this paper, we generalize the result r_{odd}(K_{n,n},K_{2,2})=\frac{1}{2}n+o(n) from [ 9 ] in two different ways. Theorem 1 . For any integer t\geq 2 , we have r_{odd}\left(K_{n,n},K_{2,t}\right)=\frac{n}{t}+o(n). Theorem 2 . For any integer k\geq 2 , we have r_{odd}\left({\mathcal{K}}^{(k)}_{n,\dots,n},{\mathcal{K}}_{1,\dots,1,2,2}\right)=\frac{n}{2}+o(n). The proofs of the upper bounds in both theorems use the Tripartite Matching Theorem , a new version of the conflict-free hypergraph matching method recently introduced by Joos, Mubayi, and Smith [ 21 ] . Theorem 2 is the first result studying odd Ramsey numbers for hypergraphs. The organization of the paper is as follows. In Section 2 , we outline the Tripartite Matching Theorem [ 21 ] . The proof of Theorem 1 is then given in Section 3 , and the proof of Theorem 2 is given in Section 4 . 2 The Tripartite Matching Theorem The conflict-free hypergraph matching method is a powerful probabilistic tool that, given some conditions, guarantees the existence of a matching avoiding certain negative constraints (conflicts) in a hypergraph. The method was introduced by Glock, Joos, Kim, Kühn, and Lichev [ 18 ] and independently by Delcourt and Postle [ 14 ] , and it has already seen many applications, including bounds for odd Ramsey and generalized Ramsey numbers (see e.g., [ 4 , 7 , 9 , 19 , 20 , 21 , 22 ] ). In this paper, we use a new version of the method, the Tripartite Matching Theorem, which was proven recently by Joos, Mubayi, and Smith [ 21 ] (Theorem 3 below). Very recently Bal and Bennett improved the upper bound on f(K_{n},C_{4},3) using the Tripartite Matching Theorem [ 3 ] . The key difference between the original method and the new version involves properties of the matching obtained by the theorem. In the original method, there is a hypergraph {\mathcal{H}} and a conflict system {\mathcal{C}} for {\mathcal{H}} , where V({\mathcal{C}})=E({\mathcal{H}}) . The edges of {\mathcal{C}} correspond to conflicts , namely sets of edges in {\mathcal{H}} that should not be included together in the resulting matching. As long as some conditions on the degrees in {\mathcal{H}} and {\mathcal{C}} hold, the method guarantees the existence of an almost perfect matching of {\mathcal{H}} that does not contain any of the conflicts in {\mathcal{C}} . Applying this method to edge-coloring, one defines a hypergraph {\mathcal{H}} in which an almost perfect matching corresponds to an edge-coloring of a dense subgraph of G with k colors. The conflicts in {\mathcal{C}} are defined to correspond to such colorings that would not satisfy the odd- or generalized- Ramsey requirements. Thus, if the conditions of the theorem hold, one obtains a matching corresponding to a coloring of most of the edges in G