Independent sets in hypergraphs with a forbidden link

DOI10.1112/PLMS.12400MaRDI QIDQ5012711zbMATH OpenOpenAlexFDO

Authors Jacob Fox, Xiaoyu He

Publication date 25 November 2021

Published in Proceedings of the London Mathematical Society (Search for Journal in Brave)

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

zbMATH Keywords

3-uniform hypergraphhypergraph Ramsey numbers

Mathematics Subject Classification ID

Generalized Ramsey theory (05C55) Hypergraphs (05C65) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Ramsey theory (05D10) Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.) (05D40)

Abstract: We give a probabilistic construction of a $3$-uniform hypergraph on $N$ vertices with independence number $O(logN/loglogN)$ in which there are at most two edges among any four vertices. This bound is tight and solves a longstanding open problem of ErdH{o}s and Hajnal in Ramsey theory. We further extend this result to prove tight bounds on various other hypergraph Ramsey numbers.

Recommendations

• On independent sets in hypergraphs
• A note on the Erdős-Hajnal hypergraph Ramsey problem
• Sparse hypergraphs with low independence number
• On 3-hypergraphs with forbidden 4-vertex configurations
• On the independence number of non-uniform uncrowded hypergraphs

Cited in

(19)

• Coloring the normalized Laplacian for oriented hypergraphs
• On 3-hypergraphs with forbidden 4-vertex configurations
• Independent sets in hypergraphs and Ramsey properties of graphs and the integers
• Polynomial to exponential transition in Ramsey theory
• On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs
• Independent sets in hypergraphs
• On independent sets in hypergraphs
• Independent sets in hypergraphs omitting an intersection
• Hypergraph Ramsey numbers of cliques versus stars
• Large independent sets from local considerations
• Erdős-Hajnal problem for \(H\)-free hypergraphs
• Large cliques or cocliques in hypergraphs with forbidden order-size pairs
• Is it easy to regularize a hypergraph with easy links?
• Maximizing the maximum degree in ordered nearest neighbor graphs
• When are off-diagonal hypergraph Ramsey numbers polynomial?
• On off-diagonal hypergraph Ramsey numbers
• Maximizing the maximum degree in ordered nearest neighbor graphs
• Off-diagonal Ramsey numbers for slowly growing hypergraphs
• Generalized Erdős-Rogers problems for hypergraphs

This page was built for publication: Independent sets in hypergraphs with a forbidden link

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