Solution to a problem of Katona on counting cliques of weighted graphs

A subset I of the vertex set V ( G ) of a graph G is called a k-clique independent set of G if no k vertices in I form a k-clique of G. An independent set is a 2-clique independent set. Let π k ( G ) denote the number of k-cliques of G. For a function w : V ( G ) → { 0, 1, 2, … }, let G ( w ) be the graph obtained from G by replacing each vertex v by a w ( v )-clique K v and making each vertex of K u adjacent to each vertex of K v for each edge { u, v } of G. For an integer m ≥ 1, consider any w with ∑ v ∈ V ( G ) w ( v ) = m. For U ⊆ V ( G ), we say that w is uniform on U if w ( v ) = 0 for each v ∈ V ( G ) ∖ U and, for each u ∈ U, w ( u ) = m / | U | or w ( u ) = m / | U |. Katona asked if π k ( G ( w ) ) is smallest when w is uniform on a largest k-clique independent set of G. He placed particular emphasis on the Sperner graph B n, given by V ( B n ) = { X : X ⊆ { 1, …, n } } and E ( B n ) = { { X, Y } : X ⊊ Y ∈ V ( B n ) }. He provided an affirmative answer for k = 2 (and any G). We determine graphs for which the answer is negative for every k ≥ 3. These include B n for n ≥ 2. Generalizing Sperner’s Theorem and a recent result of Qian, Engel and Xu, we show that π k ( B n ( w ) ) is smallest when w is uniform on a largest independent set of B n. We also show that the same holds for complete multipartite graphs and chordal graphs. We show that this is not true of every graph, using a deep result of Bohman on triangle-free graphs.