K₄^--free triple systems without large stars in the complement

2025/04/08 by Dhruv Mubayi, Mubayi, Dhruv, Nicholas Spanier +1 · 1 citation
Computer Science · Engineering · Mathematics · #05C55 #05C65 #05D10 #05D40 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Limits and Structures in Graph Theory #graph theory and CDMA systems

paper · pdf · doi:10.48550/arxiv.2504.06076

openalex publication_date 2025/04/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The n-star S_n is the n-vertex triple system with n-1 \choose 2 edges all of which contain a fixed vertex, and K₄^- is the unique triple system with four vertices and three edges. We prove that the Ramsey number r(K₄^-, S_n) has order of magnitude n² /log n. This confirms a conjecture of Conlon, Fox, He, Suk, Verstraëte and the first author. It also generalizes the well-known bound of Kim for the graph Ramsey number r(3,n), as the link of any vertex in a K₄^--free triple system is a triangle-free graph. Our method builds on the approach of Guo and Warnke who adapted Kim's lower bound for r(3,n) to the pseudorandom setting.

Cited by

• Improving R(3,k) in just two bites

Related

• Paley-like graphs for the Ramsey number r(C₄,K_t)
• On generalized Ramsey numbers for 3-uniform hypergraphs
• Multicolor Ramsey numbers for triple systems
• Computation of the Ramsey Numbers R(C₄,K₉) and R(C₄,K₁₀)
• Off-diagonal Ramsey numbers