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

color energydifference setsforbidden configurationslocal propertiesRamsey theory

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

• 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
• 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?)
• 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 edge colorings with at least \(q\) colors in every subset of \(p\) vertices
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• The Erdős-Gyárfás problem on generalized Ramsey numbers
• The probabilistic method

Cited in

(13)

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

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)