zbMATH — the first resource for mathematics

On the densities of cliques and independent sets in graphs. (English) Zbl 1399.05125
Summary: Let \(r\), \(s\geq 2\) be integers. Suppose that the number of blue \(r\)-cliques in a red/blue coloring of the edges of the complete graph \(K_n\) is known and fixed. What is the largest possible number of red \(s\)-cliques under this assumption? The well known Kruskal-Katona theorem answers this question for \(r = 2\) or \(s = 2\). Using the shifting technique from extremal set theory together with some analytical arguments, we resolve this problem in general and prove that in the extremal coloring either the blue edges or the red edges form a clique.

05C35 Extremal problems in graph theory
05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05D05 Extremal set theory
Full Text: DOI
[1] M.H. Albert, M.D. Atkinson, C.C. Handley, D.A. Holton and W. Stromquist: On packing densities of permutations, Electron. J. Combin. 9 (2002), #R5. · Zbl 0982.05005
[2] V. Chvátal and P. Hammer: Aggregation of inequalities in integer programming, Ann. Discrete Math. 1 (1977), 145–162. · doi:10.1016/S0167-5060(08)70731-3
[3] S. Das, H. Huang, J. Ma, H. Naves and B. Sudakov: A problem of Erdos on the minimum of k-cliques, J. Combinatorial Theory Ser. B 103 (2013), 344–373. · Zbl 1301.05185 · doi:10.1016/j.jctb.2013.02.003
[4] P. Erdos: On the number of complete subgraphs contained in certain graphs, Magyar Tud. Akad. Mat. Kutató Int. Közl. 7 (1962), 459–464.
[5] P. Erdos and A. Stone: On the structure of linear graphs, Bull. Am. Math. Soc. 52 (1946), 1087–1091. · Zbl 0063.01277 · doi:10.1090/S0002-9904-1946-08715-7
[6] P. Frankl: The shifting techniques in extremal set theory, in: Surveys in Combinatorics, Lond. Math. Soc. Lect. Note Ser. 123 (1987), 81–110.
[7] P. Frankl, M. Kato, G. Katona and N. Tokushige: Two-colorings with many monochromatic cliques in both colors, J. Comb. Theory Ser. B 103 (2013), 415–427. · Zbl 1301.05123 · doi:10.1016/j.jctb.2013.04.002
[8] A. Goodman: On sets of acquaintances and strangers at any party, Amer. Math. Monthly 66 (1959), 778–783. · Zbl 0092.01305 · doi:10.2307/2310464
[9] G. Katona: A theorem of finite sets, in: Theory of Graphs Akadémia Kiadó, Budapest (1968), 187–207.
[10] P. Keevash: Shadows and intersections: stability and new proofs, Adv. Math. 218 (2008), 1685–1703. · Zbl 1160.05055 · doi:10.1016/j.aim.2008.03.023
[11] J. Kruskal: The number of simplicies in a complex, Mathematical Optimization Techniques, Univ. of California Press (1963), 251–278.
[12] V. Nikiforov: The number of cliques in graphs of given order and size, Trans. Amer. Math. Soc. 363 (2011), 1599–1618. · Zbl 1231.05129 · doi:10.1090/S0002-9947-2010-05189-X
[13] O. Pikhurko and E.R. Vaughan: Minimum number of k-cliques in graphs with bounded independence number, Combin. Probab. Computing 22 (2013), 910–934. · Zbl 1282.05183 · doi:10.1017/S0963548313000357
[14] A. Razborov: On the minimal density of triangles in graphs, Combin. Probab. Computing 17 (2008), 603–618. · Zbl 1170.05036 · doi:10.1017/S0963548308009085
[15] C. Reiher: Minimizing the number of cliques in graphs of given order and edge density, manuscript.
[16] A. Thomason: A disproof of a conjecture of Erdos in Ramsey theory, J. London Math. Soc. (2) 39(2) (1989), 246–255. · Zbl 0638.05037 · doi:10.1112/jlms/s2-39.2.246
[17] P. Turán: On an extremal problem in graph theory, Matematikai ás Fizikai Lapok 48 (1941), 436–452.
[18] A. Zykov: On some properties of linear complexes, Mat. Sbornik N.S. 24 (1949), 163–188.
[19] F. Franek and V. Rödl: 2-colorings of complete graphs with small number of monochromatic K 4 subgraphs, Discrete Mathematics 114 (1993), 199–203. · Zbl 0782.05059 · doi:10.1016/0012-365X(93)90366-2
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.