Independence in 5-uniform hypergraphs

详细信息    查看全文

• 作者：Alex Eustis^a ; ^{akeustis@gmail.com" class="auth_mail" title="E-mail the corresponding author} ; Michael A. Henning^b ; ^{mahenning@uj.ac.za" class="auth_mail" title="E-mail the corresponding author} ; Anders Yeo^b ; ^c ; ^{andersyeo@gmail.com" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Independence ; Transversal ; Hypergraph ; Dual hypergraph
• 刊名：Discrete Mathematics
• 出版年：2016
• 出版时间：6 February 2016
• 年：2016
• 卷：339
• 期：2
• 页码：1004-1027
• 全文大小：515 K

文摘

In this paper we improve the best known lower bounds on independent sets in 5-uniform hypergraphs. Our proof techniques introduce two completely new methods in order to obtain our improvements on existing bounds. A subset of vertices in a hypergraph 4e183" title="Click to view the MathML source">H$H$ is an independent set if it contains no edge of 4e183" title="Click to view the MathML source">H$H$. The independence number, α(H)$\alpha \left(H\right)$, of 4e183" title="Click to view the MathML source">H$H$ is the maximum cardinality of an independent set in 4e183" title="Click to view the MathML source">H$H$. Let 4e183" title="Click to view the MathML source">H$H$ be a connected 5-uniform hypergraph with maximum degree Δ(H)$\Delta \left(H\right)$. For e1723fd4084e9326b5dbccc" title="Click to view the MathML source">i=1,…,Δ(H)$i=1,\dots ,\Delta \left(H\right)$, let n_i$n_i$ denote the number of vertices of degree i$i$ in 4e183" title="Click to view the MathML source">H$H$. We prove the following results. If Δ(H)≤3$\Delta \left(H\right)\le 3$ and 4e183" title="Click to view the MathML source">H$H$ is not one of two forbidden hypergraphs, then α(H)≥0.8n₁+0.75n₂+0.7n₃+(n₁−n₃)/130$\alpha \left(H\right)\ge 0.8n_1+0.75n_2+0.7n_3+(n_1-n_3)/130$. If Δ(H)≤4$\Delta \left(H\right)\le 4$ and 4e183" title="Click to view the MathML source">H$H$ is not a given forbidden hypergraph, then α(H)≥0.8n₁+0.75n₂+0.7n₃+0.65n₄+n₄/300−(n₂+2n₃)/260$\alpha \left(H\right)\ge 0.8n_1+0.75n_2+0.7n_3+0.65n_4+n_4/300-(n_2+2n_3)/260$. For 54501a19eb29995356171cb0e2a3c6" title="Click to view the MathML source">Δ(H)≥5$\Delta \left(H\right)\ge 5$, we define f(1)=0.8$f\left(1\right)=0.8$, f(2)=5.2/7$f\left(2\right)=5.2/7$, f(3)=0.7−1/130$f\left(3\right)=0.7-1/130$, f(4)=0.65+1/300$f\left(4\right)=0.65+1/300$ and for d≥5$d\ge 5$, we define f(d)=f(d−1)−(2f(d−1)−f(d−2))/(4d)$f\left(d\right)=f(d-1)-(2f(d-1)-f(d-2))/\left(4d\right)$ and prove that α(H)≥∑_v∈V(H)f(d(v))$\alpha \left(H\right)\ge {\sum }_{v\in V\left(H\right)}f\left(d\left(v\right)\right)$. Furthermore, we prove that we can find an independent set I$I$ in 4e183" title="Click to view the MathML source">H$H$ in polynomial time, such that |I|≥∑_v∈V(H)f(d(v))$\left|I\right|\ge {\sum }_{v\in V\left(H\right)}f\left(d\left(v\right)\right)$. Our results give support for existing conjectures and we pose several new conjectures which are of independent interest.