2019/03/19 by Lauren Keough, Keough, Lauren, A. J. Radcliffe +1
Computer Science · Engineering · #05C35 #05C65 #05C69 #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1903.08232
openalex publication_date 2019/03/19 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
There has been interest recently in maximizing the number of independent sets in graphs. For example, the Kahn-Zhao theorem gives an upper bound on the number of independent sets in a d-regular graph. Similarly, it is a corollary of the Kruskal-Katona theorem that the lex graph has the maximum number of independent sets in a graph of fixed size and order. In this paper we solve two equivalent problems. The first is: what 3-uniform hypergraph on a ground set of size n, having at least t edges, has the most 2-independent sets? Here a 2--independent set is a subset of vertices containing fewer than 2 vertices from each edge. This is equivalent to the problem of determining which graph on n vertices having at least t triangles has the most independent sets. The (hypergraph) answer is that, ignoring some transient and some persistent exceptions, a (2,3,1)-lex style 3-graph is optimal. We also discuss the problem of maximizing the number of s-independent sets in r-uniform hypergraphs of fixed size and order, proving some simple results, and conjecture an asymptotically correct general solution to the problem.