Independence in uniform linear triangle-free hypergraphs

详细信息    查看全文

• 作者：Piotr Borowiecki^a ; ^{pborowie@eti.pg.gda.pl" class="auth_mail" title="E-mail the corresponding author} ; Michael Gentner^b ; ^{michael.gentner@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author} ; Christian Lö ; wenstein^b ; ^{christian.loewenstein@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author} ; Dieter Rautenbach^b ; ^{dieter.rautenbach@uni-ulm.de" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Independence ; Hypergraph ; Linear ; Uniform ; Double linear ; Triangle-free
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 July 2016
• 年：2016
• 卷：339
• 期：7
• 页码：1878-1883
• 全文大小：378 K

文摘

The independence number class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16000169&_mathId=si8.gif&_user=111111111&_pii=S0012365X16000169&_rdoc=1&_issn=0012365X&md5=76029c550208082f2da4f5b0196b4022" title="Click to view the MathML source">α(H)class="mathContainer hidden">class="mathCode">$\alpha \left(H\right)$ of a hypergraph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16000169&_mathId=si9.gif&_user=111111111&_pii=S0012365X16000169&_rdoc=1&_issn=0012365X&md5=c48b10e2069f5c76ed2216b1aac08a09" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$H$ is the maximum cardinality of a set of vertices of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16000169&_mathId=si9.gif&_user=111111111&_pii=S0012365X16000169&_rdoc=1&_issn=0012365X&md5=c48b10e2069f5c76ed2216b1aac08a09" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$H$ that does not contain an edge of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16000169&_mathId=si9.gif&_user=111111111&_pii=S0012365X16000169&_rdoc=1&_issn=0012365X&md5=c48b10e2069f5c76ed2216b1aac08a09" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$H$. Generalizing Shearer’s classical lower bound on the independence number of triangle-free graphs Shearer (1991), and considerably improving recent results of Li and Zang (2006) and Chishti et al. (2014), we show that for an class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16000169&_mathId=si13.gif&_user=111111111&_pii=S0012365X16000169&_rdoc=1&_issn=0012365X&md5=11e876266c0c3a0d7c71e5bc60a22ee2" title="Click to view the MathML source">rclass="mathContainer hidden">class="mathCode">$r$-uniform linear triangle-free hypergraph class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16000169&_mathId=si9.gif&_user=111111111&_pii=S0012365X16000169&_rdoc=1&_issn=0012365X&md5=c48b10e2069f5c76ed2216b1aac08a09" title="Click to view the MathML source">Hclass="mathContainer hidden">class="mathCode">$H$ with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0012365X16000169&_mathId=si15.gif&_user=111111111&_pii=S0012365X16000169&_rdoc=1&_issn=0012365X&md5=c39e4b09d9e49c635e37d26710e6404b" title="Click to view the MathML source">r≥2class="mathContainer hidden">class="mathCode">$r\ge 2$, where