Local properties via color energy graphs and forbidden configurations

DOI10.1137/18M1225987zbMATH Open1431.05144arXiv1810.09019OpenAlexW2998803016WikidataQ126384929 ScholiaQ126384929MaRDI QIDQ5208745FDOQ5208745

Authors: Sara Fish, Cosmin Pohoata, Adam Sheffer 

Publication date: 10 January 2020

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

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$.

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

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

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)

Cites Work

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

Cited In (9)

• The Erdős–Gyárfás function with respect to Gallai‐colorings
• Progress on local properties problems of 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
• Color Isomorphic Even Cycles and a Related Ramsey Problem
• 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)