We extend the seminal van den Berg-Kesten Inequality 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 u
pper tail probabilities for event counts in a product probability space.
Write $mathcal{C}(G)$ for the cycle space of a graph $G$, $mathcal{C}_kappa(G)$ for the subspace of $mathcal{C}(G)$ spanned by the copies of the $kappa$-cycle $C_kappa$ in $G$, $mathcal{T}_kappa$ for the class of graphs satisfying $mathcal{C}_kappa(G
)=mathcal{C}(G)$, and $mathcal{Q}_kappa$ for the class of graphs each of whose edges lies in a $C_kappa$. We prove that for every odd $kappa geq 3$ and $G=G_{n,p}$, [max_p , Pr(G in mathcal{Q}_kappa setminus mathcal{T}_kappa) rightarrow 0;] so the $C_kappa$s of a random graph span its cycle space as soon as they cover its edges. For $kappa=3$ this was shown by DeMarco, Hamm and Kahn (2013).
An old conjecture of Zs. Tuza says that for any graph $G$, the ratio of the minimum size, $tau_3(G)$, of a set of edges meeting all triangles to the maximum size, $ u_3(G)$, of an edge-disjoint triangle packing is at most 2. Here, disproving a conjec
ture of R. Yuster, we show that for any fixed, positive $alpha$ there are arbitrarily large graphs $G$ of positive density satisfying $tau_3(G)>(1-o(1))|G|/2$ and $ u_3(G)<(1+alpha)|G|/4$.
