Extremal and Ramsey results on graph blowups

DOI10.4310/JOC.2021.V12.N1.A1MaRDI QIDQ2226518zbMATH OpenOpenAlexFDO

Authors Jacob Fox, Sammy Luo, Yuval Wigderson

Publication date 8 February 2021

Published in Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.08328

zbMATH Keywords

graph blowupsRamsey theory

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: Recently, Souza introduced blowup Ramsey numbers as a generalization of bipartite Ramsey numbers. For graphs $G$ and $H$, say $GoversetrlongrightarrowH$ if every $r$-edge-coloring of $G$ contains a monochromatic copy of $H$. Let $H[t]$ denote the $t$-blowup of $H$. Then the blowup Ramsey number of $G,H,r,$ and $t$ is defined as the minimum $n$ such that $G[n]oversetrlongrightarrowH[t]$. Souza proved upper and lower bounds on $n$ that are exponential in $t$, and conjectured that the exponential constant does not depend on $G$. We prove that the dependence on $G$ in the exponential constant is indeed unnecessary, but conjecture that some dependence on $G$ is unavoidable. An important step in both Souza's proof and ours is a theorem of Nikiforov, which says that if a graph contains a constant fraction of the possible copies of $H$, then it contains a blowup of $H$ of logarithmic size. We also provide a new proof of this theorem with a better quantitative dependence.

Recommendations

• Blowup Ramsey numbers
• Extremal graphs for edge blow-up of graphs
• Extremal graphs for blow-ups of cycles and trees
• Degree Ramsey numbers for cycles and blowups of trees
• On the Turán number of the blow-up of the hexagon

Cited in

(7)

• Extremal graphs for blow-ups of keyrings
• scientific article; zbMATH DE number 3520446 (Why is no real title available?)
• Ramsey precompact expansions of homogeneous directed graphs
• Extremal Problems for Hypergraph Blowups of Trees
• Common graphs with arbitrary connectivity and chromatic number
• Two Ramsey problems in blowups of graphs
• Unavoidable patterns in locally balanced colourings

This page was built for publication: Extremal and Ramsey results on graph blowups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2226518)