Local properties via color energy graphs and forbidden configurations

DOI10.1137/18M1225987MaRDI QIDQ5208745zbMATH OpenOpenAlexWikidataFDO

Authors Sara Fish, Cosmin Pohoata, Adam Sheffer

Publication date 10 January 2020

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

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

zbMATH Keywords

Ramsey theorydifference setsforbidden configurationscolor energylocal properties

Mathematics Subject Classification ID

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

Abstract: The local properties problem of ErdH{o}s and Shelah generalizes many Ramsey problems and some distinct distances problems. In this work, we derive a variety of new bounds for the local properties problem and its variants. We do this by continuing to develop the color energy technique --- a variant of the concept of additive energy from Additive Combinatorics. In particular, we generalize the concept of color energy to higher color energies, and combine these with Extremal Graph Theory results about graphs with no cycles or subdivisions of size $k$.

Recommendations

• Local properties in colored graphs, distinct distances, and difference sets
• Lower bounds on the Erdős–Gyárfás problem via color energy graphs
• Generalized local colorings of graphs
• Ramsey numbers for local colorings
• A variant of the classical Ramsey problem

Cites work

• scientific article; zbMATH DE number 3540832 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• scientific article; zbMATH DE number 3258067 (Why is no real title available?)
• scientific article; zbMATH DE number 5663738 (Why is no real title available?)
• A Note on Bipartite Graphs Without 2 k -Cycles
• A quantitative improvement for Roth's theorem on arithmetic progressions: Table 1.
• A variant of the classical Ramsey problem
• Additive combinatorics
• Improved bounds for the extremal number of subdivisions
• Local properties in colored graphs, distinct distances, and difference sets
• More distinct distances under local conditions
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• On edge colorings with at least \(q\) colors in every subset of \(p\) vertices
• The Erdős-Gyárfás problem on generalized Ramsey numbers
• The probabilistic method

Cited in

(11)

• The Erdős–Gyárfás function with respect to Gallai‐colorings
• Progress on local properties problems of difference sets
• Color isomorphic even cycles and a related Ramsey problem
• Local rainbow colorings for various graphs
• Local properties in colored graphs, distinct distances, and difference sets
• Lower bounds on the Erdős–Gyárfás problem via color energy graphs
• The Erdős-Gyárfás function \(f(n, 4, 5) = \frac{5}{6} n + o(n)\) -- so Gyárfás was right
• Rainbow Turán number of even cycles, repeated patterns and blow-ups of cycles
• Growth rates of the bipartite Erdős-Gyárfás function
• Rainbow subgraphs in edge-colored planar and outerplanar graphs
• New bounds on the generalized Ramsey number \(f(n, 5, 8)\)

This page was built for publication: Local properties via color energy graphs and forbidden configurations

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