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

Abstract

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.