Maximizing Subgraph Counts in Regular Graphs
Gabor Lippner and Arturo Ortiz San Miguel · 2026
Read Maximizing Subgraph Counts in Regular Graphs by Gabor Lippner and Arturo Ortiz San Miguel (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-20988.txt.
Introduction
Gabor Lippner and Arturo Ortiz San Miguel ask which regular graphs hold the most copies of a given pattern. Their 2026 paper studies subgraph counts in regular graphs. A regular graph gives every vertex the same number of edges. For a fixed pattern graph H, some regular graphs pack in more H-shaped copies than others. The authors seek the graphs with the highest H-density.
They reframe the hunt as a continuous optimization problem. The new frame runs through the eigenvalues of the graph. Counts of injective homomorphisms link to counts from quotient graphs of H. That link turns a discrete search into smooth math. The result gives extremal graph theory a fresh handle. It may help design networks with chosen pattern densities.
Catalog record
| CREATOR | Gabor Lippner and Arturo Ortiz San Miguel |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-20988
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Maximizing Subgraph Counts in Regular Graphs Thanks: Department of Mathematics, Northeastern University Thanks: email: [email protected], [email protected] Gabor Lippner and Arturo Ortiz San Miguel Abstract . Given a graph H H , we investigate the d d -regular graphs G G with the highest H H -density. We reframe the problem as a continuous optimization problem on the eigenvalues of G G by relating injective homomorphism numbers from H H and homomorphism numbers from quotient graphs of H H . For almost all H H , this relation has non-spectral terms , which require bounding by spectral terms in a way that is sharp at the optimal graph. For bipartite H H and d d large enough, we show G G consists of disjoint copies of K d , d K_{d,d} . For non-bipartite H H and d d sufficiently large, G G is a collection of disjoint K d + 1 K_{d+1} graphs. For H = C 5 H=C_{5} and d = 3 d=3 , disjoint Petersen graphs emerge. MSC Classification (2020): 05C35 (Primary); 05C60, 05C50 (Secondary). Keywords: Extremal graph theory, regular graphs, homomorphism numbers, spectral graph theory. 1. Introduction Understanding the extremal behavior of subgraph counts in regular graphs, such as maximizing the number of triangles, cliques, or cycles is a fundamental question in extremal combinatorics. These problems are closely tied to the structure theory of graphs, pseudo-randomness, and spectral graph theory. They also serve as a lens through which we can better understand how local graph properties constrain global patterns. Consider the case of triangles: in an n -vertex, d -regular graph, any node can be contained in at most \tbinom{d}{2} triangles. So the whole graph cannot have more than n/3\cdot\tbinom{t}{2} and clearly equality is only achievable when each component of the graph is isomorphic to K_{d+1} . A similar argument shows that the same is true for K_{r} subgraphs for any r\leq d . On the other hand, for 4-cycles the answer is different: it is easy to see that an edge can be contained in at most (d-1)^{2} 4-cycles, and this can only happen when the edge is in a component isomorphic to K_{d,d} . So in order for a graph to have the largest number of 4 -cycles on average, it has to consist of disjoint copies of K_{d,d} . In this paper we study the general question: given a fixed graph H , which d -regular graphs have the “most” copies of H ? Of course, the subgraph count needs to be suitably normalized. Following [ 4 ] , we denote \inj(H,G)=\mbox{ the number of injective homomorphisms from $H\to G$} and refer to t_{\inj}(H,G)=\frac{\inj(H,G)}{|V(G)|} as the H -density of G . This is the normalization that is best adapted to the case of bounded-degree graphs. Let \mathcal{G}_{d} denote the set of all d -regular graphs. Our main goal can now be phrased as follows: for a fixed H and d>0 , determine t_{\inj}^{\sup}(H):=\sup\{t_{\inj}(H,G):G\in\mathcal{G}_{d}\} and classify all graphs where the supremum is achieved. Based on the cases explained above, one might be led to believe that the answer is always the same: the optimal graphs must consist of disjoint copies of K_{d+1} or of K_{d,d} . The simplicity and intuitiveness of this answer perhaps explains why such a basic question received so little attention in the literature. However, it turns out that the situation is more complicated. Already for the case of the 5-cycle the answer depends on d . For d\geq 7 the above guess is indeed the right answer, but for d=3 the optimal graphs consist of disjoint copies of the Petersen graph. And while for d=4,5,6 we haven’t been able determine the answer, we do know that copies of K_{d+1} are not optimal for d=4,5 , and for d=6 there are other graphs that achieve the same density as K_{7} . A somewhat similar question was studied in an unpublished note by Rivin [ 5 ] , where a bound for the number of closed walks in a graph is given as a function of the number of its edges, and it is shown that the extremum is achieved when the edges form a clique. Zhao [ 8 ] studies the number of independent sets in d -regular graphs, and shows that this is maximized for unions of complete d -regular bipartite graphs, whereas Galvin [ 2 ] shows that the number of q -colorings among d -regular graphs cannot asymptotically exceed that of a union of K_{d,d} s. The rest of this paper is structured as follows: the rest of Section 1 presents our main results, gives a proof overview, and discusses recent and relevant research developments. The main ingredients and the overall structure of the proof are explained in Section 2 . The actual proof is broken into a part about homomorphism inequalities in Section 3 and some rather technical results about polynomial optimization in Section 4 . Finally, Appendix A focuses on the special case of H=C_{5} . 1.1. Results Throughout this paper, unless stated otherwise, all graphs G=(V,E) are finite and simple. If all components of a graph G are isomorphic to a (connected) graph H then we will often refer to G as consisting of (disjoint) copies of H . Our main theorem confirms the intuition stated above when d is large enough. The answer is different depending on whether H is a tree, a non-tree bipartite graph, or a non-bipartite graph. Theorem 1.1 . Let H be a tree. Then for any d\geq\Delta(H) we have t_{\inj}(H,G)=t_{\inj}^{\sup}(H)\Longleftrightarrow\mbox{ the girth of $G$ is greater than the diameter of $H$}. Theorem 1.2 . Let H be a connected bipartite graph that is not a tree. Then there is a d_{0}=d_{0}(H) such that for all d\geq d_{0} and all G\in\mathcal{G}_{d} we have t_{\inj}(H,G)=t_{\inj}^{\sup}(H)\Longleftrightarrow\mbox{$G$ consists of copies of $K_{d,d}$ }. Theorem 1.3 . Let H be a connected non-bipartite graph. Then there is a d_{0}=d_{0}(H) such that for all d\geq d_{0} and all G\in\mathcal{G}_{d} we have t_{\inj}(H,G)=t_{\inj}^{\sup}(H)\Longleftrightarrow\mbox{$G$ consists of copies of $K_{d+1}$ }. Remark 1.4 . It is worth noting that unless H is a tree, graphs that exactly maximize the H -density only exist for certain values of n . Specifically, the optimal density can only be achieved for n=2kd for bipartite H and n=k(d+1) for non-bipartite H . For large n that does not have the required number of vertices, we will see that the optimal graphs still have the same clique structure that covers all but a vanishingly small portion of their nodes. Along the way we also study the (much simpler) problem of determining the maximum density of closed walks in d -regular graphs. This is trivial for walks of even length (where the optimizers consist of copies of K_{d,d} for all d ), but we can obtain a similarly general result for walks of odd length. We even show a version where only walks starting at a specific vertex are counted. Proposition 1.5 . For any d\geq 2 , the d -regular graph with the most closed (2k+1) -walks containing a given vertex is K_{d+1} . Corollary 1.6 . For k\in\mathbb{N} and d\geq 2 : (1) The d -regular graphs with the highest density of closed