Minimum number of \(k\)-cliques in graphs with bounded independence number. (English) Zbl 1282.05183
Summary: P. Erdős asked in [Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 459–464 (1962; Zbl 0174.04104)] about the value of \(f(n,k,l)\), the minimum number of \(k\)-cliques in a graph with order \(n\) and independence number less than \(l\). The case \((k,l)=(3,3)\) was solved by G. Lorden [Am. Math. Mon. 69, 114–120 (1962; Zbl 0108.18303)]. Here we solve the problem (for all large \(n\)) for \((3,l)\) with \(4\leq l\leq 7\) and \((k,3)\) with \(4\leq k\leq 7\). Independently, S. Das et al. [J. Comb. Theory, Ser. B 103, No. 3, 344–373 (2013; doi:10.1016/j.jctb.2013.02.003)] resolved the cases \((k,l)=(3,4)\) and \((4,3)\).
MSC:
| 05C69 | Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) |
| 05C35 | Extremal problems in graph theory |
| 90C35 | Programming involving graphs or networks |
Keywords:
extremal Ramsey graphReferences:
| [1] | Proc. London Math. Soc. 30 pp 264– (1930) |
| [2] | DOI: 10.2178/jsl/1203350785 · Zbl 1146.03013 · doi:10.2178/jsl/1203350785 |
| [3] | Combin. Probab. Comput. 10 pp 361– (2001) |
| [4] | DOI: 10.1017/S0963548312000508 · Zbl 1257.05077 · doi:10.1017/S0963548312000508 |
| [5] | DOI: 10.2307/2312538 · Zbl 0108.18303 · doi:10.2307/2312538 |
| [6] | Electron. J. Combin. 19 pp P40– (2012) |
| [7] | DOI: 10.1016/S0021-9800(68)80024-9 · Zbl 0164.24702 · doi:10.1016/S0021-9800(68)80024-9 |
| [8] | Magyar Tud. Akad. Mat. Kutató Int. Kozl. 7 pp 459– (1962) |
| [9] | DOI: 10.1016/j.jcta.2012.12.008 · Zbl 1259.05087 · doi:10.1016/j.jcta.2012.12.008 |
| [10] | DOI: 10.1016/j.jctb.2013.02.003 · Zbl 1301.05185 · doi:10.1016/j.jctb.2013.02.003 |
| [11] | DOI: 10.2307/2310464 · Zbl 0092.01305 · doi:10.2307/2310464 |
| [12] | DOI: 10.1016/j.jctb.2013.05.002 · Zbl 1301.05121 · doi:10.1016/j.jctb.2013.05.002 |
| [13] | Extremal Graph Theory (1978) · Zbl 0419.05031 |
| [14] | DOI: 10.1017/S0963548310000222 · Zbl 1213.05184 · doi:10.1017/S0963548310000222 |
| [15] | DOI: 10.1007/s004930070001 · Zbl 1052.68096 · doi:10.1007/s004930070001 |
| [16] | Paul Erdos and his Mathematics pp 667– (2002) |
| [17] | DOI: 10.1137/090747476 · Zbl 1223.05204 · doi:10.1137/090747476 |
| [18] | Europ. J. Combin. 23 pp 1142– (2011) |
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.
