论文标题
通过在线三角包装过程中缩小图扎猜想中的随机图形差距
Closing the Random Graph Gap in Tuza's Conjecture Through the Online Triangle Packing Process
论文作者
论文摘要
Zsolt Tuza的一个长期猜想断言，覆盖数量$τ（g）$的三角形最多是三角形包装数字$ν（g）$，其中三角形包装数量$ $ν（g）$是一组$ g $的边缘triangles的最大尺寸，$ g $和triangle covel $ coved $ g $ copt $ g）是一定的，分为$ gal（g）所有三角形。在本文中，我们证明了Tuza的猜想在所有$ m $范围内的Erdős-rényi随机图$ g（n，m）$中，缩小了以前已知的差距。 （最近，Jeff Kahn和Jinyoung Park也独立证明了这一结果。）我们采用了一个随机的贪婪过程，称为在线三角包装过程，以$ G（N，M）$中的三角形包装生产三角形包装，并使用微分方程方法分析了此过程。
A long-standing conjecture of Zsolt Tuza asserts that the triangle covering number $τ(G)$ is at most twice the triangle packing number $ν(G)$, where the triangle packing number $ν(G)$ is the maximum size of a set of edge-disjoint triangles in $G$ and the triangle covering number $τ(G)$ is the minimal size of a set of edges intersecting all triangles. In this paper, we prove that Tuza's conjecture holds in the Erdős-Rényi random graph $G(n,m)$ for all range of $m$, closing the gap in what was previously known. (Recently, this result was also independently proved by Jeff Kahn and Jinyoung Park.) We employ a random greedy process called the online triangle packing process to produce a triangle packing in $G(n,m)$ and analyze this process by using the differential equations method.
