Solution to a problem of Katona on counting cliques of weighted graphs
share
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.
READ FULL TEXT