Michael–Traves conjecture: the Roller Coaster Conjecture

From papers

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.

Progress summary

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

Sources & referencesView supporting material

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.

Solutions 0

No solutions have been posted yet.