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:
Published online:
DOI: 10.5802/alco.30
@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 = {http://www.numdam.org/articles/10.5802/alco.30/} }
Kalai, Gil; Nevo, Eran. Turán, involution and shifting. Algebraic Combinatorics, Volume 2 (2019) no. 3, pp. 367-378. doi : 10.5802/alco.30. http://www.numdam.org/articles/10.5802/alco.30/
[1] Shifting operations and graded Betti numbers, J. Algebr. Comb., Volume 12 (2000) no. 3, pp. 207-222 | DOI | MR | Zbl
[2] Reverse lexicographic and lexicographic shifting, J. Algebr. Comb., Volume 23 (2006) no. 2, pp. 107-123 | DOI | MR | Zbl
[3] An extended Euler-Poincaré theorem, Acta Math., Volume 161 (1988) no. 3-4, pp. 279-303 | DOI | MR | Zbl
[4] On an open problem of Paul Turán concerning -graphs, Studies in pure mathematics, Birkhäuser, 1983, pp. 91-93 | DOI | MR | Zbl
[5] An upper bound for the Turán number , J. Comb. Theory, Ser. A, Volume 87 (1999) no. 2, pp. 381-389 | DOI | MR | Zbl
[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 | Zbl
[7] Intersection theorems for systems of finite sets, Q. J. Math., Oxf. II. Ser., Volume 12 (1961), pp. 313-320 | DOI | MR | Zbl
[8] A method for constructing -graphs, Mat. Zametki, Volume 44 (1988) no. 4, pp. 546-550 | DOI | MR | Zbl
[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 | Zbl
[10] More constructions for Turán’s -conjecture, Electron. J. Comb., Volume 15 (2008) no. 1, R137, 23 pages | MR | Zbl
[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 | DOI | MR | Zbl
[12] A new approach to Turán’s conjecture, Graphs Comb., Volume 1 (1985), pp. 107-109 | DOI | Zbl
[13] Symmetric matroids, J. Comb. Theory, Ser. B, Volume 50 (1990) no. 1, pp. 54-64 | DOI | MR
[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 | DOI | MR | Zbl
[15] Hypergraph Turán problems, Surveys in combinatorics 2011 (London Mathematical Society Lecture Note Series), Volume 392, Cambridge University Press, 2011, pp. 83-139 | DOI | MR | Zbl
[16] Maximal number of subsets of a finite set no of which are pairwise disjoint, J. Comb. Theory, Volume 5 (1968), pp. 157-163 | DOI | MR | Zbl
[17] A class of constructions for Turán’s -problem, Combinatorica, Volume 2 (1982) no. 2, pp. 187-192 | DOI | MR | Zbl
[18] Problem 28 (Solution by H. Gouwentak, W. Mantel, J. Teixeira de Mattes, F. Schuh and W. A. Wythoff), Wiskundige Opgaven, Volume 10 (1907), pp. 60-61 | Zbl
[19] Generic initial ideals and exterior algebraic shifting of the join of simplicial complexes, Ark. Mat., Volume 45 (2007) no. 2, pp. 327-336 | DOI | MR | Zbl
[20] Algebraic shifting and graded Betti numbers, Trans. Am. Math. Soc., Volume 361 (2009) no. 4, pp. 1853-1865 | DOI | MR | Zbl
[21] Algebraic shifting and basic constructions on simplicial complexes, J. Algebr. Comb., Volume 22 (2005) no. 4, pp. 411-433 | DOI | MR | Zbl
[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 | DOI | MR | Zbl
[23] On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Discrete Math., Volume 24 (2010) no. 3, pp. 946-963 | DOI | MR | Zbl
[24] Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, Volume 48 (1941), pp. 436-452 | MR | Zbl
[25] Research problems, Magyar Tud. Akad. Mat. Kutató Int. Közl., Volume 6 (1961), pp. 417-423 | DOI | MR
Cited by Sources: