Sharp asymptotics for triangle independence and covering numbers
For a graph $G$, let $α_1(G)$ be the maximum size of an edge set containing at most one edge from every triangle, and let $τ_1(G)$ be the minimum size of an edge set meeting every triangle. Erdős, Gallai, and Tuza proved that $α_1(G)+τ_1(G)=Ω(m^{2/3})$ for every $m$-edge graph and asked for the optimal asymptotic constant. We prove $$\lim_{m\to\infty} \min_{G,\,|E(G)|=m} \frac{α_1(G) + τ_1(G)}{m^{2/3}} = \frac{3}{2},$$ thereby establishing that the sharp constant is $3/2$ and solving the problem.
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.15561
curl -X POST /api/v1/records/arxiv/2608.15561/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.15561/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'