论文标题
Tuza的广义猜想是随机超图
Generalized Tuza's conjecture for random hypergraphs
论文作者
论文摘要
Tuza的一个著名猜想指出，在任何有限的图中，边缘的三角形盖的最小尺寸最多是一组边缘 - 迪斯三角形三角形的最大尺寸。对于$ r $ - 均匀的超图（$ r $ -graph）$ g $，让$τ（g）$是边缘封面的最小尺寸，$（r-1）$ - $（r-1）$的顶点，让$ν（g）$是一组边的最大尺寸，一组相交的相互作用少于$ r-1 $ $ r-1 $ Vertices。 Aharoni和Zerbib提出了Tuza猜想的以下概括：$$ \ text {对于任何$ r $ -graph $ g $，$τ（g）/ν（g）/ν（g）\ leq \ lceil（r+1）/2 \ rceil $。 令$ h_r（n，p）$为$ n $顶点上的均匀随机$ r $ graph。我们表明，对于$ r \ in \ {3、4、5 \} $，任何$ p = p（n）$，$ h_r（n，p）$都以很高的可能性满足了aharoni-Zerbib的猜想（即，概率接近1 $ n \ rightarrow \ rightarrow \ infty \ infty $）。我们还表明，有一个$ c <1 $，因此，对于任何$ r \ geq 6 $和任何$ p = p（n）$，$τ（h_r（n，p））/ν（h_r（n，p））\ leq c r $具有很高的可能性。此外，对于任何$ \ varepsilon> 0 $，我们可能会服用$ c <1/2 + \ varepsilon $，通过限制到足够大的$ r $（取决于$ \ varepsilon $）。
A celebrated conjecture of Tuza states that in any finite graph the minimum size of a cover of triangles by edges is at most twice the maximum size of a set of edge-disjoint triangles. For an $r$-uniform hypergraph ($r$-graph) $G$, let $τ(G)$ be the minimum size of a cover of edges by $(r-1)$-sets of vertices, and let $ν(G)$ be the maximum size of a set of edges pairwise intersecting in fewer than $r-1$ vertices. Aharoni and Zerbib proposed the following generalization of Tuza's conjecture: $$ \text{For any $r$-graph $G$, $τ(G)/ν(G) \leq \lceil(r+1)/2\rceil$.} $$ Let $H_r(n,p)$ be the uniformly random $r$-graph on $n$ vertices. We show that, for $r \in \{3, 4, 5\}$ and any $p = p(n)$, $H_r(n,p)$ satisfies the Aharoni-Zerbib conjecture with high probability (i.e., with probability approaching 1 as $n \rightarrow \infty$). We also show that there is a $C < 1$ such that, for any $r \geq 6$ and any $p = p(n)$, $τ(H_r(n, p))/ν(H_r(n, p)) \leq C r$ with high probability. Furthermore, we may take $C < 1/2 + \varepsilon$, for any $\varepsilon > 0$, by restricting to sufficiently large $r$ (depending on $\varepsilon$).
