Graphs with asymmetric Ramsey properties

2025/11/04 by Mendonça, Walner, Miralaei, Meysam, Mota, Guilherme O.
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2511.02963

Abstract

Given positive integers k and ℓ we write G → (K_k,K_ℓ) if every 2-colouring of the edges of G yields a red copy of K_k or a blue copy of K_ℓ and we denote by R(k) the minimum n such that K_n→ (K_k,K_k). By using probabilistic methods and hypergraph containers we prove that for every integer k ≥ 3, there exists a graph G such that G \nrightarrow (K_k,K_k) and G → (K_R(k)-1,K_k-1). This result can be viewed as a variation of a classical theorem of Nešetřil and Rödl [The Ramsey property for graphs with forbidden complete subgraphs, Journal of Combinatorial Theory, Series B, 20 (1976), 243-249], who proved that for every integer k≥ 2 there exists a graph G with no copies of K_k such that G→(K_k-1, K_k-1).

Citations

• The asymptotics of r(4,t)
• An exponential improvement for diagonal Ramsey
• Diagonal Ramsey via effective quasirandomness
• Ramsey equivalence of K_n and K_n+K_n-1
• Recent developments in graph Ramsey theory
• What is Ramsey-equivalent to a clique?
• Independent sets in hypergraphs
• A New Upper Bound for Diagonal Ramsey Numbers
• On a Problem of Formal Logic

Related

• Asymmetric Ramsey Properties of Random Graphs for Cliques and Cycles
• Towards the 0-statement of the Kohayakawa-Kreuter conjecture
• Asymmetric Ramsey properties of randomly perturbed graphs
• Symmetric and asymmetric Ramsey properties in random hypergraphs
• Recent developments in graph Ramsey theory