Turán, involution and shifting

Kalai, Gil; Nevo, Eran

Algebraic Combinatorics, Tome 2 (2019) no. 3, pp. 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 $\frac{n}{2}$ rounded up and down.

Mots-clés : Turán’s $(3,4)$-conjecture, shifting, threshold graphs

[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 | DOI | MR | Zbl

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

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

[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 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[6] de Caen, D. 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] 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 | DOI | MR | Zbl

[8] Fon-Der-Flaass, Dmitriĭ G. A method for constructing $(3,4)$-graphs, Mat. Zametki, Volume 44 (1988) no. 4, pp. 546-550 | DOI | MR | Zbl

[9] Frankl, Peter 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] Frohmader, Andrew More constructions for Turán’s $(3,4)$-conjecture, Electron. J. Comb., Volume 15 (2008) no. 1, R137, 23 pages | MR | Zbl

[11] Kalai, Gil Characterization of $f$-vectors of families of convex sets in ${\mathbf{R}}^d$. I. Necessity of Eckhoff’s conditions, Isr. J. Math., Volume 48 (1984) no. 2-3, pp. 175-195 | DOI | MR | Zbl

[12] Kalai, Gil A new approach to Turán’s conjecture, Graphs Comb., Volume 1 (1985), pp. 107-109 | DOI | Zbl

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

[14] Kalai, Gil 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] Keevash, Peter 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] 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 | DOI | MR | Zbl

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

[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), pp. 60-61 | Zbl

[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 | DOI | MR | Zbl

[20] Murai, Satoshi; Hibi, Takayuki Algebraic shifting and graded Betti numbers, Trans. Am. Math. Soc., Volume 361 (2009) no. 4, pp. 1853-1865 | DOI | MR | Zbl

[21] Nevo, Eran Algebraic shifting and basic constructions on simplicial complexes, J. Algebr. Comb., Volume 22 (2005) no. 4, pp. 411-433 | DOI | MR | Zbl

[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 | DOI | MR | Zbl

[23] Razborov, Alexander A. On 3-hypergraphs with forbidden 4-vertex configurations, SIAM J. Discrete Math., Volume 24 (2010) no. 3, pp. 946-963 | DOI | MR | Zbl

[24] Turán, Paul Eine Extremalaufgabe aus der Graphentheorie, Mat. Fiz. Lapok, Volume 48 (1941), pp. 436-452 | MR | Zbl

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