TY - JOUR TI - Two problems on cycles in random graphs DO - https://doi.org/doi:10.7282/T39C70QR PY - 2016 AB - We prove three results. First, an old conjecture of Zs. Tuza says that for any graph G, the ratio of the minimum size, τ3(G), of a set of edges meeting all triangles to the maximum size, ν3(G), of an edge-disjoint triangle packing is at most 2. Disproving a conjecture of R. Yuster [40], we show that for any fixed, positive α there are arbitrarily large graphs G of positive density satisfying τ3(G) > (1 − o(1))|G|/2 and ν3(G) < (1 + α)|G|/4. Second, write C(G) for the cycle space of a graph G, Cκ(G) for the subspace of C(G) spanned by the copies of Cκ in G, Tκ for the class of graphs satisfying Cκ(G) = C(G), and Qκ for the class of graphs each of whose edges lies in a Cκ. We prove that for every odd κ ≥ 3 and G = Gn,p, max p Pr(G ∈ Qκ Tκ) → 0; so the Cκ’s of a random graph span its cycle space as soon as they cover its edges. For κ = 3 this was shown in [12]. Third, we extend the seminal van den Berg–Kesten Inequality [9] on disjoint occurrence of two events to a setting with arbitrarily many events, where the quantity of interest is the maximum number that occur disjointly. This provides a handy tool for bounding upper tail probabilities for event counts in a product probability space. KW - Mathematics KW - Random graphs LA - eng ER -