The extremal alternating-sign conjecture for transitive tournaments

Let TTnTT_n be a transitive tournament on nn vertices. For α=(α1,α2,,αs)Ks\alpha=(\alpha_1,\alpha_2,\dots,\alpha_s)\in\mathbb{K}_s satisfying

i=1sαi=n1,\sum_{i=1}^s\alpha_i=n-1,

Extremal alternating-sign conjecture. If nn is even, then

fTTn(1,1,1,,1,1)fTTn(α1,α2,,αs),f_{TT_n}(1,-1,1,\dots,-1,1)\geq f_{TT_n}(\alpha_1,\alpha_2,\dots,\alpha_s),

where (1,1,1,,1,1)(1,-1,1,\dots,-1,1) has n1n-1 components. If nn is odd, then

fTTn(1,2,1,1,1,,1,1)fTTn(α1,α2,,αs),f_{TT_n}(1,-2,1,-1,1,\dots,-1,1)\geq f_{TT_n}(\alpha_1,\alpha_2,\dots,\alpha_s),

where (1,2,1,,1)(1,-2,1,\dots,1) has n2n-2 components. The conjecture proposes that these alternating-sign tuples maximize the number of Hamiltonian paths counted by fTTnf_{TT_n} among all admissible tuples. The preceding computations verify the analogous extremal behavior for the tested values of nn, while the general assertion remains open.

Sources & referencesView supporting material

Primary source

Zeina Ghazo Hanna and Amine El Sahili, “Counting Hamiltonian Paths in Transitive Tournaments”, arXiv:2207.11510 (2022).

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.