Linial–Morgenstern conjecture on minimizing 4-cycles in tournaments

Let TT be a tournament on nn vertices, and let c3c_3 and c4c_4 denote its normalized numbers of cyclic triples and cyclic 44-cycles, respectively. For a transitive tournament TmT_m and weights w1,,wmw_1,\ldots,w_m, form the random blow-up by replacing vertex ii with a class of asymptotic relative size wiw_i, orienting edges between classes according to TmT_m, and choosing each class internally at random. Linial–Morgenstern conjecture. For fixed c3c_3, the minimum of c4c_4 is attained by a random blow-up of a transitive tournament TmT_m. Among such blow-ups with the prescribed c3c_3, the minimum is attained by taking mm as small as possible and w1=w2==wm1wmw_1=w_2=\cdots=w_{m-1}\geq w_m. This conjecture proposes an extremal description of tournaments minimizing cyclic 44-cycles subject to a prescribed density of cyclic triples; the cited passage does not state whether it has been resolved.

Sources & referencesView supporting material

Primary source

Nati Linial and Avraham Morgenstern, “On the number of 4-cycles in a tournament”, arXiv:1405.1576 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.