×

Edge-statistics on large graphs. (English) Zbl 1466.05101

Summary: The inducibility of a graph \(H\) measures the maximum number of induced copies of \(H\) a large graph \(G\) can have. Generalizing this notion, we study how many induced subgraphs of fixed order \(k\) and size \(\ell\) a large graph \(G\) on \(n\) vertices can have. Clearly, this number is \(\binom{n}{k}\) for every \(n,k\) and \(\ell\in\{0,\binom{k}{2}\}\). We conjecture that for every \(n\), \(k\) and \(0<\ell<\binom{k}{2}\) this number is at most \((1/e+o_k(1))\binom{n}{k}\). If true, this would be tight for \(\ell\in\{1,k-1\}\).
In support of our ‘Edge-statistics Conjecture’, we prove that the corresponding density is bounded away from 1 by an absolute constant. Furthermore, for various ranges of the values of \(\ell\) we establish stronger bounds. In particular, we prove that for ‘almost all’ pairs \((k,\ell)\) only a polynomially small fraction of the \(k\)-subsets of \(V(G)\) have exactly \(\ell\) edges, and prove an upper bound of \((1/2+o_k(1))\binom{n}{k}\) for \(\ell=1\).
Our proof methods involve probabilistic tools, such as anti-concentration results relying on fourth moment estimates and Brun’s sieve, as well as graph-theoretic and combinatorial arguments such as Zykov’s symmetrization, Sperner’s theorem and various counting techniques.

MSC:

05C35 Extremal problems in graph theory
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
05C12 Distance in graphs
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Ahlswede, R. and Katona, G. O. H. (1978) Graphs with maximal number of adjacent pairs of edges. Acta Math. Acad. Sci. Hungar.3297-120. · Zbl 0386.05036
[2] Alon, N., Gutin, G. and Krivelevich, M. (2004) Algorithms with large domination ratio. J. Algorithms50118-131. · Zbl 1068.68175
[3] Alon, N. and Spencer, J. H. (2016) The Probabilistic Method, fourth edition, Wiley-Interscience Series in Discrete Mathematics and Optimization, Wiley. · Zbl 1333.05001
[4] Balogh, J., Hu, P., Lidický, B. and Pfender, F. (2016) Maximum density of induced 5-cycle is achieved by an iterated blow-up of 5-cycle. Eur. J. Combin.5247-58. · Zbl 1327.05171
[5] Bollobás, B. (1998) Modern Graph Theory, Springer. · Zbl 0902.05016
[6] Brown, J. I. and Sidorenko, A. (1994) The inducibility of complete bipartite graphs. J. Graph Theory18629-645. · Zbl 0810.05037
[7] Erdős, P. (1945) On a lemma of Littlewood and Offord. Bull. Amer. Math. Soc.51898-902. · Zbl 0063.01270
[8] Feige, U. (2004) On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. In Proceedings of the Thirty-Sixth Annual ACM Symposium on the Theory of Computing, ACM, pp. 594-603. · Zbl 1192.60021
[9] Fox, J. and Sauermann, L. (2018) A completion of the proof of the Edge-statistics Conjecture. arXiv:1809.01352 · Zbl 1450.05094
[10] Hefetz, D. and Tyomkyn, M. (2018) On the inducibility of cycles. J. Combin. Theory Ser. B133243-258. · Zbl 1397.05087
[11] Král, D., Norin, S. and Volec, J. (2018) A bound on the inducibility of cycles. arXiv:1801.01556 · Zbl 1400.05074
[12] Janson, S., Łuczak, T. and Ruciński, A. (2000) Random Graphs, Wiley. · Zbl 0968.05003
[13] Kahn, J., Saks, M. and Smyth, C. (2011) The dual BKR inequality and Rudich’s conjecture. Combin. Probab. Comput20257-266. · Zbl 1237.05190
[14] Kwan, M., Sudakov, B. and Tran, T. (2019) Anticoncentration for subgraph statistics. J. Lond. Math. Soc.99757-777. · Zbl 1415.05089
[15] Martinsson, A., Mousset, F., Noever, A. and Trujić, M. (2018) The edge-statistics conjecture for ℓ ≪ k^6/5. arXiv:1809.02576 · Zbl 1429.05106
[16] Pippenger, N. and Golumbic, M. C. (1975) Inducibility of graphs. J. Combin. Theory Ser. B19189-203. · Zbl 0332.05119
[17] Yuster, R. (2018) On the exact maximum induced density of almost all graphs and their inducibility. arXiv:1801.01047 · Zbl 1414.05173
[18] Zykov, A. A. (1949) On some properties of linear complexes. Mat. Sbornik N.S.24163-188.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.