Sparse hypergraphs with low independence number

DOI10.1007/S00493-014-3219-8MaRDI QIDQ1705800zbMATH OpenOpenAlexFDO

Authors Jeff Cooper, Dhruv Mubayi

Publication date 16 March 2018

Published in Combinatorica (Search for Journal in Brave)

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

zbMATH Keywords

hypergraphsindependence number

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65) Extremal set theory (05D05) Ramsey theory (05D10)

Abstract: Let K_4 denote the complete 3-uniform hypergraph on 4 vertices. Ajtai, ErdH{o}s, Koml'os, and Szemer'edi (1981) asked if there is a function omega(d) tending to infinity such that every 3-uniform, K_4-free hypergraph N vertices and average degree d has independence number at least omega(d) N/d^{1/2}. We answer this question by constructing a 3-uniform, K_4-free hypergraph with independence number at most 2N/d^{1/2}. We also provide counterexamples to several related conjectures and improve the lower bound of some hypergraph Ramsey numbers.

Recommendations

• On the independence number of sparse graphs
• New lower bounds for the independence number of sparse graphs and hypergraphs
• Independence numbers of random sparse hypergraphs
• Independence numbers of hypergraphs with sparse neighborhoods.
• Sparse hypergraphs: new bounds and constructions
• Lower bounds for independence numbers of some locally sparse graphs
• On Counting Independent Sets in Sparse Graphs
• Approximating independent sets in sparse graphs
• Sparse graphs of high gonality

Cites work

• scientific article; zbMATH DE number 4014740 (Why is no real title available?)
• A Lower Bound for Heilbronn'S Problem
• A dense infinite Sidon sequence
• An intersection theorem for four sets
• Coloring \(H\)-free hypergraphs
• Extremal uncrowded hypergraphs
• List coloring triangle-free hypergraphs
• On Turan's theorem for sparse graphs
• On the independence number of sparse graphs
• Properly colored subgraphs and rainbow subgraphs in edge‐colorings with local constraints
• Sparse Parity-Check Matrices over ${GF(q)}$
• Turan's theorem for \(k\)-graphs

Cited in

(8)

• Defective coloring of hypergraphs
• Independent sets in hypergraphs with a forbidden link
• Graph and hypergraph colouring via nibble methods: a survey
• Coloring the normalized Laplacian for oriented hypergraphs
• Embedding Graphs into Larger Graphs: Results, Methods, and Problems
• Sparse 0−1 Matrices and Forbidden Hypergraphs
• Independent sets in hypergraphs omitting an intersection
• List coloring triangle-free hypergraphs

This page was built for publication: Sparse hypergraphs with low independence number

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