Independence in uniform linear triangle-free hypergraphs

DOI10.1016/J.DISC.2016.01.006MaRDI QIDQ279201zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Piotr Borowiecki, Michael Gentner, Dieter Rautenbach, Christian Löwenstein

Publication date 27 April 2016

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

independencetriangle-freehypergraphdouble linearlinearuniform

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Hypergraphs (05C65)

Abstract: The independence number $alpha(H)$ of a hypergraph $H$ is the maximum cardinality of a set of vertices of $H$ that does not contain an edge of $H$. Generalizing Shearer's classical lower bound on the independence number of triangle-free graphs (J. Comb. Theory, Ser. B 53 (1991) 300-307), and considerably improving recent results of Li and Zang (SIAM J. Discrete Math. 20 (2006) 96-104) and Chishti et al. (Acta Univ. Sapientiae, Informatica 6 (2014) 132-158), we show that ${\displaystyle }$alpha(H)geq sum_{uin V(H)}f_r(d_H(u))${\displaystyle }$ for an $r$-uniform linear triangle-free hypergraph $H$ with $rgeq2$, where �egin{eqnarray*} f_r(0)&=&1mbox{, and }\ f_r(d)&=&frac{1+Big((r-1)d^2-dBig)f_r(d-1)}{1+(r-1)d^2}mbox{ for $dgeq1$.} end{eqnarray*}

Recommendations

• On vertex independence number of uniform hypergraphs
• Counting Independent Sets in Hypergraphs
• On independent sets in hypergraphs
• Independence numbers of hypergraphs with sparse neighborhoods.
• New lower bounds for the independence number of sparse graphs and hypergraphs

Cites work

• A lower bound on the independence number of arbitrary hypergraphs
• A note on Ramsey numbers
• A note on the independence number of triangle-free graphs
• A note on the independence number of triangle-free graphs. II
• Differential Methods for Finding Independent Sets in Hypergraphs
• Extremal uncrowded hypergraphs
• Improved lower bounds on k‐independence
• New lower bounds for the independence number of sparse graphs and hypergraphs
• On independent sets in hypergraphs
• On uncrowded hypergraphs
• On vertex independence number of uniform hypergraphs
• The potential of greed for independence

Cited in

(5)

• On vertex independence number of uniform hypergraphs
• New lower bounds for the independence number of sparse graphs and hypergraphs
• A note on the caro-tuza bound on the independence number of uniform hypergraphs
• The independent neighborhoods process
• A new lower bound on the independence number of a graph and applications

This page was built for publication: Independence in uniform linear triangle-free hypergraphs

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