The paper is about counting special subsets of vertices in a type of network called a regular graph, where every vertex (node) has exactly the same number of connections. A classical result, proved by Kahn and later extended by Zhao, says that among all such graphs, the one that contains the most "independent sets" (collections of vertices with no connections between them) is a specific highly symmetric graph made of identical complete bipartite pieces. The new paper asks: what happens if you relax the rule slightly and allow the chosen subsets to have a small number of internal edges, rather than requiring zero? These are called "almost independent sets."
The authors prove a precise upper bound on how many such almost-independent subsets can exist in any regular graph. The bound has two correction terms beyond the baseline count for true independent sets. One term grows with the density of allowed edges and captures how much the count can increase when you permit a few internal connections. The other term reflects how far the graph is from the idealized symmetric structure, and it matches what was already known just for strict independent sets. Crucially, the authors show both correction terms are essentially the best possible, meaning no tighter bound of the same form could work in general.
The result resolves an open question posed by a researcher named Seth and fits into a broader mathematical program of understanding how combinatorial extremes, like maximizing the count of certain subsets, behave when the defining conditions are slightly loosened. Beyond just answering this specific question, the techniques developed here may be useful for related problems in combinatorics and statistical physics, where counting configurations in graphs with local constraints is a central challenge.