Convex hull of face vectors of colored complexes (Q2441631): Difference between revisions

A simplicial complex \(\varDelta\) on \(n\) vertices is \(r\)-colourable if its underlying graph is \(r\)-colourable. The clique vector \(c(G)\) of a graph \(G\) counts the numbers \(c_k(G)\) of \(k\)-cliques of \(G\) for each \(k\); its \(k\)-truncation replaces \(c_j(G)\) by \(0\) whenever \(j > k\). The Turán graph \(T(n,r)\) on \(n\) vertices has cliques of size at most \(r\), whose maximal independent sets have sizes as nearly equal as possible; the number of its \(k\)-cliques is denoted \(t_k(n,r)\). In [Discrete Comput. Geom. 18, No. 4, 421--431 (1997; Zbl 0899.52010)], \textit{D. N. Kozlov} made the following conjecture, which is established here: the convex hull of the \(f\)-vectors of \(r\)-colourable complexes on \(n\) vertices is generated by the truncations of the clique vector of \(T(n,r)\). The author further proves a generalization of a result of Zykov, showing that an \(r\)-colourable graph \(G\) on \(n\) vertices satisfies \[ \frac{c_r(G)}{t_r(n,r)} \leq \cdots \leq \frac{c_k(G)}{t_k(n,r)} \leq \frac{c_{k-1}(G)}{t_{k-1}(n,r)} \leq \cdots \leq \frac{c_r(G)}{t_r(n,r)} \leq 1. \]