zbMATH — the first resource for mathematics

On the 3-local profiles of graphs. (English) Zbl 1305.05120
Authors’ abstract: For a graph \(G\), let \(p_i(G)\), \(i=0,\ldots,3\) be the probability that three distinct random vertices span exactly \(i\) edges. We call \((p_0(G), \ldots,p_3(G))\) the 3-local profile of \(G\). We investigate the set \(\mathcal{S}_3 \subset \mathbb{R}^4\) of all vectors \((p_0,\ldots,p_3)\) that are arbitrarily close to the 3-local profiles of arbitrarily large graphs. We give a full description of the projection of \(\mathcal{S}_3\) to the \((p_0,p_3)\) plane. The upper envelope of this planar domain is obtained from cliques on a fraction of the vertex set and complements of such graphs. The lower envelope is Goodman’s inequality \(p_0+p_3 \geq \frac{1}{4}\). We also give a full description of the triangle-free case, i.e. the intersection of \(\mathcal{S}_3\) with the hyperplane \(p_3=0\). This planar domain is characterized by an SDP constraint that is derived from Razborov’s flag algebra theory.

05C42 Density (toughness, etc.)
05C75 Structural characterization of families of graphs
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI arXiv
[1] Bollobás, The maximal number of induced complete bipartite graphs, Discrete Math 62 pp 271– (1986) · Zbl 0613.05028 · doi:10.1016/0012-365X(86)90214-1
[2] Brown, The inducibility of complete bipartite graphs, J Graph Theory 18 pp 629– (1994) · Zbl 0810.05037 · doi:10.1002/jgt.3190180610
[3] Das, A problem of Erdos on the minimum of k-cliques, J Combin Theory Ser B 103 pp 34– (2013)
[4] P. Erdos D. J. Kleitman B. L. Rothschild Asymptotic enumeration of K n -free graphs, Theorie Combinatorie Proceedings of the Conference, Vol. II, Rome, 1973, Roma, Acad Nazionale dei Lincei 1976 19 27
[5] Erdos, On the number of complete subgraphs contained in certain graphs, Magyar Tud Akad Mat Kutató Int Közl 7 pp 459– (1962)
[6] Erdös, On the structure of linear graphs, Bull Am Math Soc 52 pp 1087– (1946) · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7
[7] Exoo, Dense packings of induced subgraphs, Ars Combin 22 pp 5– (1986) · Zbl 0651.05041
[8] Franek, 2-colorings of complete graphs with small number of monochromatic K4 subgraphs, Discrete Math 114 pp 199– (1993) · Zbl 0782.05059 · doi:10.1016/0012-365X(93)90366-2
[9] Giraud, Sur le problème de Goodman pour les quadrangles et la majoration des nombres de Ramsey, J Combin Theory, Series B 27 pp 237– (1979) · Zbl 0427.05052 · doi:10.1016/0095-8956(79)90016-9
[10] Goodman, On sets of acquaintances and strangers at any party, Am Math Monthly pp 778– (1959) · Zbl 0092.01305 · doi:10.2307/2310464
[11] H. Hatami J. Hirst S. Norine The inducibility of blow-up graphs 2011 · Zbl 1301.05234
[12] Hatami, Undecidability of linear inequalities in graph homomorphism densities, J Am Math Soc 24 pp 547– (2011) · Zbl 1259.05088 · doi:10.1090/S0894-0347-2010-00687-X
[13] J. Hirst The inducibility of graphs on four vertices 2011
[14] H. Huang N. Linial H. Naves Y. Peled B. Sudakov On the densities of cliques and independent sets in graphs
[15] Katona, A Theorem of Finite Sets pp 187– (1968)
[16] Kruskal, The Number of Simplices in a Complex, Mathematical Optimization Techniques pp 251– (1963) · Zbl 0116.35102
[17] Nikiforov, The number of cliques in graphs of given order and size, Trans Am Math Soc 363 pp 1599– (2011) · Zbl 1231.05129 · doi:10.1090/S0002-9947-2010-05189-X
[18] O. Pikhurko Minimum number of k -cliques in graphs with bounded independence number
[19] Pippenger, The inducibility of graphs, J Combin Theory, Series B 19 pp 189– (1975) · Zbl 0332.05119 · doi:10.1016/0095-8956(75)90084-2
[20] Razborov, Flag algebras, J Symbolic Logic 72 pp 1239– (2007) · Zbl 1146.03013 · doi:10.2178/jsl/1203350785
[21] Razborov, On the minimal density of triangles in graphs, Combin Prob Comput 17 pp 603– (2008) · Zbl 1170.05036 · doi:10.1017/S0963548308009085
[22] Razborov, On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J Discrete Math 24 pp 946– (2010) · Zbl 1223.05204 · doi:10.1137/090747476
[23] C. Reiher Minimizing the number of cliques in graphs of given order and edge density
[24] K. Sperfeld On the minimal monochromatic K 4 -density 2011
[25] Thomason, A disproof of a conjecture of Erdos in Ramsey theory, J London Math Soc 2 pp 246– (1989) · Zbl 0638.05037 · doi:10.1112/jlms/s2-39.2.246
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.