ALGEBRAIC COMBINATORICS

Turán, involution and shifting
Algebraic Combinatorics, Volume 2 (2019) no. 3, p. 367-378

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 G on n vertices and any involution on its vertex set, if for any 3-set S of the vertices, the number of edges in G spanned by S, plus the number of edges in G spanned by the image of S under the involution, is at least 2, then the number of edges in G is at least the Mantel–Turán bound, namely the number achieved by two disjoint cliques of sizes n 2 rounded up and down.

Received : 2018-03-05
Accepted : 2018-06-26
Published online : 2019-06-06
DOI : https://doi.org/10.5802/alco.30
Keywords: Turán’s (3,4)-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},
     publisher = {MathOA foundation},
     volume = {2},
     number = {3},
     year = {2019},
     pages = {367-378},
     doi = {10.5802/alco.30},
     zbl = {07066880},
     language = {en},
     url = {https://alco.centre-mersenne.org/item/ALCO_2019__2_3_367_0}
}

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] Aramova, Annetta; Herzog, Jürgen; Hibi, Takayuki Shifting operations and graded Betti numbers, J. Algebr. Comb., Volume 12 (2000) no. 3, pp. 207-222 | Article | MR 1803232 | Zbl 0980.13013

[2] Babson, Eric; Novik, Isabella; Thomas, Rekha Reverse lexicographic and lexicographic shifting, J. Algebr. Comb., Volume 23 (2006) no. 2, pp. 107-123 | Article | MR 2223682 | Zbl 1097.13029

[3] Björner, Anders; Kalai, Gil An extended Euler-Poincaré theorem, Acta Math., Volume 161 (1988) no. 3-4, pp. 279-303 | Article | MR MR971798 | Zbl 0667.52008

[4] Brown, William G. On an open problem of Paul Turán concerning 3-graphs, Studies in pure mathematics, Birkhäuser (1983), pp. 91-93 | Article | MR 820213 | Zbl 0599.05033

[5] Chung, Fan; Lu, Linyuan An upper bound for the Turán number t 3 (n,4), J. Comb. Theory, Ser. A, Volume 87 (1999) no. 2, pp. 381-389 | Article | MR 1704268 | Zbl 0946.05063

[6] De Caen, D. The current status of Turán’s problem on hypergraphs, Extremal problems for finite sets (Visegrád, 1991), János Bolyai Mathematical Society (Bolyai Society Mathematical Studies) Volume 3 (1994), pp. 187-197 | MR 1319162 | Zbl 0820.05042

[7] Erdős, Pál; Ko, Chao; Rado, Richard 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] Fon-Der-Flaass, Dmitriĭ G. A method for constructing (3,4)-graphs, Mat. Zametki, Volume 44 (1988) no. 4, pp. 546-550 | Article | MR 975195 | Zbl 0727.05042

[9] Frankl, Peter The shifting technique in extremal set theory, Surveys in combinatorics 1987 (New Cross, 1987), Cambridge University Press (London Mathematical Society Lecture Note Series) Volume 123 (1987), pp. 81-110 | MR 905277 | Zbl 0633.05038

[10] Frohmader, Andrew More constructions for Turán’s (3,4)-conjecture, Electron. J. Comb., Volume 15 (2008) no. 1, R137, 23 pages | MR 2465761 | Zbl 1178.05066

[11] Kalai, Gil Characterization of f-vectors of families of convex sets in R d . 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] Kalai, Gil A new approach to Turán’s conjecture, Graphs Comb., Volume 1 (1985), pp. 107-109 | Article | Zbl 0579.05003

[13] Kalai, Gil Symmetric matroids, J. Comb. Theory, Ser. B, Volume 50 (1990) no. 1, pp. 54-64 | Article | MR 1070465

[14] Kalai, Gil Algebraic shifting, Computational commutative algebra and combinatorics (Osaka, 1999), Mathematical Society of Japan (Advanced Studies in Pure Mathematics) Volume 33 (2002), pp. 121-163 | Article | MR 1890098 | Zbl 1034.57021

[15] Keevash, Peter Hypergraph Turán problems, Surveys in combinatorics 2011, Cambridge University Press (London Mathematical Society Lecture Note Series) Volume 392 (2011), pp. 83-139 | Article | MR 2866732 | Zbl 1244.05159

[16] Kleitman, Daniel J. Maximal number of subsets of a finite set no k of which are pairwise disjoint, J. Comb. Theory, Volume 5 (1968), pp. 157-163 | Article | MR 0228350 | Zbl 0245.05003

[17] Kostochka, Aleksandr V. A class of constructions for Turán’s (3,4)-problem, Combinatorica, Volume 2 (1982) no. 2, pp. 187-192 | Article | MR 685045 | Zbl 0502.05046

[18] Mantel, W. 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] Murai, Satoshi 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] Murai, Satoshi; Hibi, Takayuki 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] Nevo, Eran 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] Pikhurko, Oleg 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] Razborov, Alexander A. 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] Turán, Paul Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, Volume 48 (1941), pp. 436-452 | MR 0018405 | Zbl 67.0732.03

[25] Turán, Paul Research problems, Magyar Tud. Akad. Mat. Kutató Int. Közl., Volume 6 (1961), pp. 417-423 | Article | MR 0177847