×

Refuting conjectures in extremal combinatorics via linear programming. (English) Zbl 1428.05308

Summary: We apply simple linear programming methods and an LP solver to refute a number of open conjectures in extremal combinatorics.

MSC:

05D99 Extremal combinatorics
90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aharoni, R.; Howard, D., A rainbow \(r\)-partite version of the Erdős-Ko-Rado theorem, Combin. Probab. Comput., 26, 3, 321-337 (2017) · Zbl 1371.05195
[2] Anstee, R., A survey of forbidden configuration results, Electron. J. Combin., 1000, 20-29 (2013) · Zbl 1267.05278
[3] Chvátal, V.; Chvátal, V., Linear Programming (1983), Macmillan · Zbl 0318.05002
[4] Colbourn, C. J., CRC Handbook of Combinatorial Designs (2010), CRC Press
[5] Colbourn, C. J.; Hamm, R. C.; Lindner, C. C.; Rodger, C. A., Embedding partial graph designs, block designs, and triple systems with \(\lambda > 1\), Canad. Math. Bull., 29, 4, 385-391 (1986) · Zbl 0556.05008
[6] De Silva, J.; Heysse, K.; Kapilow, A.; Schenfisch, A.; Young, M., Turán numbers of vertex-disjoint cliques in r-partite graphs, Discrete Math., 341, 2, 492-496 (2018) · Zbl 1376.05072
[7] Erdős, P., Intersection theorems for systems op finite sets, Quart. J. Math. Oxford Ser. (2), 12, 313-320 (1961) · Zbl 0100.01902
[8] Frankl, P., An Erdős-Ko-Rado theorem for direct products, European J. Combin., 17, 8, 727-730 (1996) · Zbl 0860.05068
[9] Frankl, P., Antichains of fixed diameter, Mosc. J. Comb. Number Theory, 7, N3 (2017) · Zbl 1456.05166
[10] Frankl, P.; Han, J.; Huang, H.; Zhao, Y., A degree version of the Hilton-Milner theorem, J. Combin. Theory Ser. A, 155, 493-502 (2018) · Zbl 1377.05189
[11] Frankl, P.; Kupavskii, A., Families with no \(s\) pairwise disjoint sets, J. Lond. Math. Soc., 95, 3, 875-894 (2017) · Zbl 1370.05214
[12] Frankl, P.; Kupavskii, A., Families of sets with no matchings of sizes 3 and 4, European J. Combin., 75, 123-135 (2019) · Zbl 1400.05252
[13] Frankl, P.; Tokushige, N., Extremal Problems for Finite Sets, Student Mathematical Library (2018), American Mathematical Society · Zbl 1416.05001
[14] Hillier, F. S.; Lieberman, G. J., Introduction to Operations Research (1995), McGraw-Hill Science, Engineering & Mathematics · Zbl 0155.28202
[15] Hilton, A. J.W.; Milner, E. C., Some intersection theorems for systems of finite sets, Q. J. Math., 18, 1, 369-384 (1967) · Zbl 0168.26205
[16] Ihringer, F.; Kupavskii, A., Regular intersecting families (2017), arXiv preprint
[17] Katona, Gy O. H., A general 2-part Erdős-Ko-Rado theorem, Opuscula Math., 37, 4, 577-588 (2017) · Zbl 1402.05207
[18] Kirkman, T. P., On a problem in combinations, Cambridge Dublin Math. J., 2, 191-204 (1847)
[19] Kleitman, D. J., On a combinatorial conjecture of Erdős, J. Combin. Theory, 1, 2, 209-214 (1966) · Zbl 0148.01105
[20] Kleitman, D. J., Maximal number of subsets of a finite set no \(k\) of which are pairwise disjoint, J. Combin. Theory, 5, 2, 157-163 (1968) · Zbl 0245.05003
[21] Quinn, F. (1986), PhD thesis
[22] Suda, S.; Tanaka, H., A cross-intersection theorem for vector spaces based on semidefinite programming, Bull. Lond. Math. Soc., 46, 2, 342-348 (2014) · Zbl 1285.05181
[23] Suda, S.; Tanaka, H.; Tokushige, N., A semidefinite programming approach to a cross-intersection problem with measures, Math. Program., 166, 1-2, 113-130 (2017) · Zbl 1375.05261
[24] Wagner, A. Z., Refuting conjectures in extremal combinatorics via linear programming (2019), arXiv preprint
[25] Wilson, R. M., An existence theory for pairwise balanced designs, iii: proof of the existence conjectures, J. Combin. Theory Ser. A, 18, 1, 71-79 (1975) · Zbl 0295.05002
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.