Michael–Traves conjecture: the Roller Coaster Conjecture

About 22 years old · traced to

Let qq be a positive integer, let π\pi be a permutation of {⌈q/2⌉,⌈q/2⌉+1,…,q}\{\lceil q/2\rceil,\lceil q/2\rceil+1,\ldots,q\}, and let ik(G)i_k(G) denote the number of independent sets of cardinality kk in a graph GG. A graph is well-covered if all its maximal independent sets have the same size, and α(G)\alpha(G) denotes its independence number. Roller Coaster Conjecture. There is a well-covered graph GG with α(G)=q\alpha(G)=q such that

iπ(⌈q/2⌉)(G)<iπ(⌈q/2⌉+1)(G)<⋯<iπ(q)(G).i_{\pi(\lceil q/2\rceil)}(G)<i_{\pi(\lceil q/2\rceil+1)}(G)<\cdots<i_{\pi(q)}(G).

The paper proves this conjecture by constructing suitable well-covered graphs, so the asserted ordering is no longer open.

References

Primary source

Jonathan Cutler and Luke Pebody, “Maximal-clique partitions and the Roller Coaster Conjecture”, arXiv:1412.4595 (2014).

Additional references

2 papers in this index state this conjecture (2004–2014). The statement above is taken from the most recent of them; the others are arXiv:math/0406623.

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.