Linial–Morgenstern conjecture on minimizing 4-cycles in tournaments
Linial–Morgenstern conjecture on minimizing 4-cycles in tournaments
Let be a tournament on vertices, and let and denote its normalized numbers of cyclic triples and cyclic -cycles, respectively. For a transitive tournament and weights , form the random blow-up by replacing vertex with a class of asymptotic relative size , orienting edges between classes according to , and choosing each class internally at random. Linial–Morgenstern conjecture. For fixed , the minimum of is attained by a random blow-up of a transitive tournament . Among such blow-ups with the prescribed , the minimum is attained by taking as small as possible and . This conjecture proposes an extremal description of tournaments minimizing cyclic -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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.