Bonferroni inequalities and negative cycles in large complete signed graphs (Q1922875)

A signed graph \(G\) based on \(F\) is an ordinary graph \(F\) with each edge marked as positive or negative. The authors only consider the case in which \(F\) is the complete graph \(K_n\). A cycle of \(K_n\) is said to be negative if it contains an odd number of negative edges; otherwise, it is positive. The authors solve the problem of characterizing extremal graphs \(K_n\) relative to the number of negative \(p\)-cycles, when the number of negative edges is fixed, and when \(n\) is large. They also show that the number of negative \(p\)-cycles can be expressed as an alternating sum for which the Bonferroni inequalities hold. Furthermore, the asymptotic value of the probability that a \(p\)-cycle of \(K_n\) is negative is found as \(n\to\infty\), if the negative edges induce a subgraph whose components are paths or cycles.