The extremal alternating-sign conjecture for transitive tournaments

About 4 years old · traced to

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=n−1,\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 n−1n-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 n−2n-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.

References

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.