Independence in uniform linear triangle-free hypergraphs

DOI10.1016/J.DISC.2016.01.006zbMATH Open1334.05091DBLPjournals/dm/BorowieckiGLR16arXiv1507.04323OpenAlexW1918183363WikidataQ62043605 ScholiaQ62043605MaRDI QIDQ279201FDOQ279201

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

Publication date: 27 April 2016

Published in: Discrete Mathematics (Search for Journal in Brave)

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*}

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

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

zbMATH Keywords

independencetriangle-freehypergraphdouble linearlinearuniform

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (2)

• A note on the caro-tuza bound on the independence number of uniform hypergraphs
• New lower bounds for the independence number of sparse graphs and hypergraphs

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)