On Ramsey Size-Linear Graphs and Related Questions

DOI10.1137/22M1481713MaRDI QIDQ6141859zbMATH OpenFDO

Authors Domagoj Bradač, Lior Gishboliner, Benny Sudakov

Publication date 23 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

dependent random choicegraph Ramsey theoryRamsey size-linear graph

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Ramsey theory (05D10)

Abstract: In this paper we prove several results on Ramsey numbers $R(H,F)$ for a fixed graph $H$ and a large graph $F$, in particular for $F=K_n$. These results extend earlier work of ErdH{o}s, Faudree, Rousseau and Schelp and of Balister, Schelp and Simonovits on so-called Ramsey size-linear graphs. Among others, we show that if $H$ is a subdivision of $K_4$ with at least $6$ vertices, then $R(H,F)=O(v(F)+e(F))$ for every graph $F$. We also conjecture that if $H$ is a connected graph with $$, then $R(H,K_n)=O(n^k)$. The case $k=2$ was proved by ErdH{o}s, Faudree, Rousseau and Schelp. We prove the case $k=3$.

Recommendations

• Subdivided graphs have linear ramsey numbers
• Ramsey Size Linear Graphs
• Ramsey linear families and generalized subdivided graphs
• A note on the Size-Ramsey number of long subdivisions of graphs
• The size‐Ramsey number of short subdivisions

Cites work

• A note on Ramsey numbers
• A note on Ramsey size-linear graphs
• A partial k-arboretum of graphs with bounded treewidth
• Asymptotic lower bounds for Ramsey functions
• Dependent random choice
• Disproof of a Conjecture of Erdős and Simonovits on the Turán Number of Graphs with Minimum Degree 3
• scientific article; zbMATH DE number 3545699 (Why is no real title available?)
• Parameters tied to treewidth
• Ramsey Size Linear Graphs
• Random graphs.
• The early evolution of the \(H\)-free process
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Turán Numbers of Bipartite Graphs and Related Ramsey-Type Questions

This page was built for publication: On Ramsey Size-Linear Graphs and Related Questions

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