Independent sets in hypergraphs omitting an intersection

DOI10.1002/RSA.21071MaRDI QIDQ6052482zbMATH OpenOpenAlexFDO

Authors Tom Bohman, Xizhi Liu, Dhruv Mubayi

Publication date 17 October 2023

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

independent setsL-intersecting familiespseudorandom hypergraphsrandom greedy processes

Mathematics Subject Classification ID

Hypergraphs (05C65) Random graphs (graph-theoretic aspects) (05C80) Extremal set theory (05D05)

Abstract: A $k$-uniform hypergraph with $n$ vertices is an $(n,k,ell)$-omitting system if it does not contain two edges whose intersection has size exactly $ell$. If in addition it does not contain two edges whose intersection has size greater than $ell$, then it is an $(n,k,ell)$-system. R"{o}dl and v{S}iv{n}ajov'{a} proved a lower bound for the independence number of $(n,k,ell)$-systems that is sharp in order of magnitude for fixed $2leelllek-1$. We consider the same question for the larger class of $(n,k,ell)$-omitting systems. For $kle2ell+1$, we believe that the behavior is similar to the case of $(n,k,ell)$-systems and prove a nontrivial lower bound for the first open case $ell=k-2$. For $k>2ell+1$ we give new lower and upper bounds which show that the minimum independence number of $(n,k,ell)$-omitting systems has a very different behavior than for $(n,k,ell)$-systems. Our lower bound for $ell=k-2$ uses some adaptations of the random greedy independent set algorithm, and our upper bounds (constructions) for $k>2ell+1$ are obtained from some pseudorandom graphs. We also prove some related results where we forbid more than two edges with a prescribed common intersection size and this leads to some applications in Ramsey theory. For example, we obtain good bounds for the Ramsey number $r_k(F^k,t)$, where $F^k$ is the $k$-uniform Fan. Here the behavior is quite different than the case $k=2$ which reduces to the classical graph Ramsey number $r(3,t)$.

Recommendations

• Independent sets in hypergraphs with a forbidden link
• On independent sets in hypergraphs
• On the independence number of non-uniform uncrowded hypergraphs
• Bounding the independence number in some \((n,k,\ell,\lambda)\)-hypergraphs
• The independent neighborhoods process

Cites work

• A new generalization of Mantel's theorem to \(k\)-graphs
• A note on embedding hypertrees
• A note on Ramsey numbers
• A note on the random greedy independent set algorithm
• Bounding the independence number in some \((n,k,\ell,\lambda)\)-hypergraphs
• Extremal uncrowded hypergraphs
• Forbidding just one intersection
• scientific article; zbMATH DE number 3026527 (Why is no real title available?)
• Hypergraph Ramsey numbers: triangles versus cliques
• Intersection Properties of Systems of Finite Sets
• Introduction to Random Graphs
• Mathematics of Ramsey theory. Collected papers of the Prague symposium on graph theory held in Prague, Czechoslovakia
• Note on independent sets in steiner systems
• On independent sets in hypergraphs
• On the independence number of sparse graphs
• On the independence number of Steiner systems
• On Turan's theorem for sparse graphs
• Sparse hypergraphs with low independence number
• The de Bruijn-Erdős theorem for hypergraphs
• The Ramsey number R(3, t) has order of magnitude t²/log t
• Turan's theorem for k-graphs
• Using Lovász local lemma in the space of random injections

Cited in

(2)

• Independence number of hypergraphs under degree conditions
• Random Turán and counting results for general position sets over finite fields

This page was built for publication: Independent sets in hypergraphs omitting an intersection

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