On a Conjecture of Nagy on Extremal Densities
Pages 294 - 306
Abstract
We disprove a conjecture of Nagy on the maximum number of copies $N$($G$, $H$) of a fixed graph $G$ in a large graph $H$ with prescribed edge density. Nagy conjectured that for all $G$, the quantity $N$($G$, $H$) is asymptotically maximized by either a quasi-star or a quasi-clique. We show this is false for infinitely many graphs, the smallest of which has six vertices and six edges. We also propose some new conjectures for the behavior of $N$($G$, $H$) and present some evidence for them.
References
[1]
R. Ahlswede and G. Katona, Graphs with maximal number of adjacent pairs of edges, Acta Math. Hungar., 32 (1978), pp. 97--120, https://doi.org/10.1007/BF01902206.
[2]
N. Alon, On the number of subgraphs of prescribed type of graphs with a given number of edges, Israel J. Math., 38 (1981), pp. 116--130, https://doi.org/10.1007/BF02761855.
[3]
F. Chung, R. Graham, P. Frankl, and J. Shearer, Some intersection theorems for ordered sets and graphs, J. Combin. Theory Ser. A, 43 (1986), pp. 23--37, https://doi.org/10.1016/0097-3165(86)90019-1.
[4]
J. Cutler and J. Radcliffe, Extremal problems for independent set enumeration, Electron. J. Combin., 18 (2011), P169, https://doi.org/10.37236/656.
[5]
A. Dudek, J. Polcyn, and A. Ruciński, Subhypergraph counts in extremal and random hypergraphs and the fractional $q$-independence, J. Comb. Optim., 19 (2010), pp. 184--199, https://doi.org/10.1007/s10878-008-9174-9.
[6]
E. Friedgut and J. Kahn, On the number of copies of one hypergraph in another, Israel J. Math., 105 (1998), pp. 251--256, https://doi.org/10.1007/BF02780332.
[7]
D. Gerbner, D. Nagy, B. Patkós, and M. Vizer, On the maximum number of copies of $H$ in graphs with given size and order, J. Graph Theory, 96 (2020), pp. 34--43, https://doi.org/10.1002/jgt.22563.
[8]
S. Janson, K. Oleszkiewicz, and A. Ruciński, Upper tails for subgraph counts in random graphs, Israel J. Math., 142 (2004), pp. 61--92, https://doi.org/10.1007/BF02771528.
[9]
R. Kenyon, C. Radin, K. Ren, and L. Sadun, Multipodal structure and phase transitions in large constrained graphs, J. Stat. Phys., 168 (2017), pp. 233--258, https://doi.org/10.1007/s10955-017-1804-0.
[10]
L. Lovász, Large Networks and Graph Limits, Amer. Math. Soc. Colloq. Publ. 60, AMS, Providence, RI, 2012, https://doi.org/10.1090/coll/060.
[11]
D. Nagy, On the number of 4-edge paths in graphs with given edge density, Combin. Probab. Comput., 26 (2017), pp. 431--447, https://doi.org/10.1017/S0963548316000389.
[12]
G. Nemhauser and L. Trotter, Properties of vertex packing and independence system polyhedra, Math. Program., 6 (1974), pp. 48--61, https://doi.org/10.1007/BF01580222.
[13]
C. Reiher, The clique density theorem, Ann. of Math., 184 (2016), pp. 683--707, https://doi.org/10.4007/annals.2016.184.3.1.
[14]
C. Reiher and S. Wagner, Maximum star densities, Studia Sci. Math. Hungar., 55 (2018), pp. 238--259, https://doi.org/10.1556/012.2018.55.2.1395.
[15]
A. Sidorenko, A correlation inequality for bipartite graphs, Graphs Combin., 9 (1993), pp. 201--204, https://doi.org/10.1007/BF02988307.
Recommendations
Books versus Triangles at the Extremal Density
A celebrated result of Mantel shows that every graph on n vertices with $\lfloor n^2/4 \rfloor + 1$ edges must contain a triangle. A robust version of this result, due to Rademacher, says that there must, in fact, be at least $\lfloor n/2 \rfloor$ ...
The Generalized Rainbow Turán Problem for Cycles
Given an edge-colored graph, we say that a subgraph is rainbow if all of its edges have different colors. Let ${\operatorname{ex}}(n,H, {rainbow-}F)$ denote the maximal number of copies of $H$ that a properly edge-colored graph on $n$ vertices can ...
Extremal Threshold Graphs for Matchings and Independent Sets
Many extremal problems for graphs have threshold graphs as their extremal examples. For instance the current authors proved that for fixed $$k\ge 1$$k?1, among all graphs on n vertices with e edges, some threshold graph has the fewest matchings of size ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
DOI:10.1137/sjdmec.35.1
Issue’s Table of Contents© 2021, Society for Industrial and Applied Mathematics.
Publisher
Society for Industrial and Applied Mathematics
United States
Publication History
Published: 04 March 2021
Author Tags
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Nov 2024
Other Metrics
Citations
View Options
View options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in