We propose a strengthening of the conclusion in Turán’s (3,4)-conjecture in terms of algebraic shifting, and show that its analogue for graphs does hold. In another direction, we generalize the Mantel–Turán theorem by weakening its assumption: for any graph on vertices and any involution on its vertex set, if for any 3-set of the vertices, the number of edges in spanned by , plus the number of edges in spanned by the image of under the involution, is at least 2, then the number of edges in is at least the Mantel–Turán bound, namely the number achieved by two disjoint cliques of sizes rounded up and down.
Accepted: 2018-06-25
Published online: 2019-06-06
DOI: https://doi.org/10.5802/alco.30
Keywords: Turán’s -conjecture, shifting, threshold graphs
@article{ALCO_2019__2_3_367_0, author = {Kalai, Gil and Nevo, Eran}, title = {Tur\'an, involution and shifting}, journal = {Algebraic Combinatorics}, pages = {367--378}, publisher = {MathOA foundation}, volume = {2}, number = {3}, year = {2019}, doi = {10.5802/alco.30}, zbl = {07066880}, language = {en}, url = {alco.centre-mersenne.org/item/ALCO_2019__2_3_367_0/} }
Kalai, Gil; Nevo, Eran. Turán, involution and shifting. Algebraic Combinatorics, Volume 2 (2019) no. 3, pp. 367-378. doi : 10.5802/alco.30. https://alco.centre-mersenne.org/item/ALCO_2019__2_3_367_0/
[1] Shifting operations and graded Betti numbers, J. Algebr. Comb., Volume 12 (2000) no. 3, pp. 207-222 | Article | MR 1803232 | Zbl 0980.13013
[2] Reverse lexicographic and lexicographic shifting, J. Algebr. Comb., Volume 23 (2006) no. 2, pp. 107-123 | Article | MR 2223682 | Zbl 1097.13029
[3] An extended Euler-Poincaré theorem, Acta Math., Volume 161 (1988) no. 3-4, pp. 279-303 | Article | MR MR971798 | Zbl 0667.52008
[4] On an open problem of Paul Turán concerning -graphs, Studies in pure mathematics, Birkhäuser, 1983, pp. 91-93 | Article | MR 820213 | Zbl 0599.05033
[5] An upper bound for the Turán number , J. Comb. Theory, Ser. A, Volume 87 (1999) no. 2, pp. 381-389 | Article | MR 1704268 | Zbl 0946.05063
[6] The current status of Turán’s problem on hypergraphs, Extremal problems for finite sets (Visegrád, 1991) (Bolyai Society Mathematical Studies) Volume 3, János Bolyai Mathematical Society, 1994, pp. 187-197 | MR 1319162 | Zbl 0820.05042
[7] Intersection theorems for systems of finite sets, Q. J. Math., Oxf. II. Ser., Volume 12 (1961), pp. 313-320 | Article | MR 0140419 | Zbl 0100.01902
[8] A method for constructing -graphs, Mat. Zametki, Volume 44 (1988) no. 4, pp. 546-550 | Article | MR 975195 | Zbl 0727.05042
[9] The shifting technique in extremal set theory, Surveys in combinatorics 1987 (New Cross, 1987) (London Mathematical Society Lecture Note Series) Volume 123, Cambridge University Press, 1987, pp. 81-110 | MR 905277 | Zbl 0633.05038
[10] More constructions for Turán’s -conjecture, Electron. J. Comb., Volume 15 (2008) no. 1, 23 pages | MR 2465761 | Zbl 1178.05066
[11] Characterization of -vectors of families of convex sets in . I. Necessity of Eckhoff’s conditions, Isr. J. Math., Volume 48 (1984) no. 2-3, pp. 175-195 | Article | MR MR770700 | Zbl 0572.52006
[12] A new approach to Turán’s conjecture, Graphs Comb., Volume 1 (1985), pp. 107-109 | Article | Zbl 0579.05003
[13] Symmetric matroids, J. Comb. Theory, Ser. B, Volume 50 (1990) no. 1, pp. 54-64 | Article | MR 1070465
[14] Algebraic shifting, Computational commutative algebra and combinatorics (Osaka, 1999) (Advanced Studies in Pure Mathematics) Volume 33, Mathematical Society of Japan, 2002, pp. 121-163 | Article | MR 1890098 | Zbl 1034.57021
[15] Hypergraph Turán problems, Surveys in combinatorics 2011 (London Mathematical Society Lecture Note Series) Volume 392, Cambridge University Press, 2011, pp. 83-139 | Article | MR 2866732 | Zbl 1244.05159
[16] Maximal number of subsets of a finite set no of which are pairwise disjoint, J. Comb. Theory, Volume 5 (1968), pp. 157-163 | Article | MR 0228350 | Zbl 0245.05003
[17] A class of constructions for Turán’s -problem, Combinatorica, Volume 2 (1982) no. 2, pp. 187-192 | Article | MR 685045 | Zbl 0502.05046
[18] Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff), Wiskundige Opgaven, Volume 10 (1907), p. 60-61 | Zbl 38.0270.01
[19] Generic initial ideals and exterior algebraic shifting of the join of simplicial complexes, Ark. Mat., Volume 45 (2007) no. 2, pp. 327-336 | Article | MR 2342617 | Zbl 1143.13024
[20] Algebraic shifting and graded Betti numbers, Trans. Am. Math. Soc., Volume 361 (2009) no. 4, pp. 1853-1865 | Article | MR 2465820 | Zbl 1163.13006
[21] Algebraic shifting and basic constructions on simplicial complexes, J. Algebr. Comb., Volume 22 (2005) no. 4, pp. 411-433 | Article | MR 2191645 | Zbl 1092.52008
[22] The minimum size of 3-graphs without a 4-set spanning no or exactly three edges, Eur. J. Comb., Volume 32 (2011) no. 7, pp. 1142-1155 | Article | MR 2825540 | Zbl 1229.05154
[23] On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Discrete Math., Volume 24 (2010) no. 3, pp. 946-963 | Article | MR 2680226 | Zbl 1223.05204
[24] Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, Volume 48 (1941), pp. 436-452 | MR 0018405 | Zbl 67.0732.03
[25] Research problems, Magyar Tud. Akad. Mat. Kutató Int. Közl., Volume 6 (1961), pp. 417-423 | MR 0177847