Independence number of hypergraphs under degree conditions

DOI10.1002/RSA.21151zbMATH Open1522.05216arXiv2205.02877MaRDI QIDQ6076735FDOQ6076735

Authors:

Publication date: 17 October 2023

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

Abstract: A well-known result of Ajtai et al. from 1982 states that every $k$-graph $H$ on $n$ vertices, with girth at least five, and average degree $t^{k-1}$ contains an independent set of size $cn(logt{)}^{1/(k-1)}/t$ for some $c>0$. In this paper we show that an independent set of the same size can be found under weaker conditions allowing certain cycles of length 2, 3 and 4. Our work is motivated by a problem of Lo and Zhao, who asked for $kge4$, how large of an independent set a $k$-graph $H$ on $n$ vertices necessarily has when its maximum $(k-2)$-degree $Delt{a}_{k-2}(H)ledn$. (The corresponding problem with respect to $(k-1)$-degrees was solved by Kostochka, Mubayi, and Varstra"ete [Random Structures & Algorithms 44, 224--239, 2014].) In this paper we show that every $k$-graph $H$ on $n$ vertices with $Delt{a}_{k-2}(H)ledn$ contains an independent set of size $c(fracndloglogfracnd{)}^{1/(k-1)}$, and under additional conditions, an independent set of size $c(fracndlogfracnd{)}^{1/(k-1)}$. The former assertion gives a new upper bound for the $(k-2)$-degree Tur'an density of complete $k$-graphs.

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

Recommendations

• New results on \(k\)-independence of hypergraphs
• On the independence number of non-uniform uncrowded hypergraphs
• On uncrowded hypergraphs
• Independence in 5-uniform hypergraphs
• New results on \(k\)-independence of graphs

zbMATH Keywords

hypergraphindependent setsemi-random methoddegree Turán density

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Hypergraphs (05C65)

Cites Work

• Title not available (Why is that?)
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Title not available (Why is that?)
• Extremal uncrowded hypergraphs
• On independent sets in hypergraphs
• A note on the random greedy independent set algorithm
• Coloring sparse hypergraphs
• Turan's theorem for \(k\)-graphs
• A dense infinite Sidon sequence
• Co-degree density of hypergraphs
• On the codegree density of complete 3-graphs and related problems
• \({\ell}\)-degree Turán density
• On the independence number of non-uniform uncrowded hypergraphs
• Codegree Turán density of complete \(r\)-uniform hypergraphs
• Bounding the independence number in some \((n,k,\ell,\lambda)\)-hypergraphs
• Note on independent sets in steiner systems
• Independent sets in hypergraphs omitting an intersection

Cited In (6)

• Positive independence densities of finite rank countable hypergraphs are achieved by finite hypergraphs
• New results on \(k\)-independence of hypergraphs
• The critical independence number and an independence decomposition
• On the independence number of non-uniform uncrowded hypergraphs
• Independence and Matchings in $\sigma$-hypergraphs
• A degree sum condition concerning the connectivity and the independence number of a graph

This page was built for publication: Independence number of hypergraphs under degree conditions

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