Turán, involution and shifting

Kalai, Gil; Nevo, Eran

doi:10.5802/alco.30

Kalai, Gil ¹; Nevo, Eran ¹

¹ Einstein Institute of Mathematics The Hebrew University of Jerusalem Jerusalem (Israel)

Algebraic Combinatorics, Volume 2 (2019) no. 3, pp. 367-378.

Abstract

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.

Received: 2018-03-05
Accepted: 2018-06-26
Published online: 2019-06-06

Zbl

DOI: 10.5802/alco.30

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

Author's affiliations:

Kalai, Gil ¹; Nevo, Eran ¹

¹ Einstein Institute of Mathematics The Hebrew University of Jerusalem Jerusalem (Israel)

License:

CC-BY 4.0

Copyrights: The authors retain unrestricted copyrights and publishing rights

@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 = {https://alco.centre-mersenne.org/articles/10.5802/alco.30/}
}

TY  - JOUR
AU  - Kalai, Gil
AU  - Nevo, Eran
TI  - Turán, involution and shifting
JO  - Algebraic Combinatorics
PY  - 2019
SP  - 367
EP  - 378
VL  - 2
IS  - 3
PB  - MathOA foundation
UR  - https://alco.centre-mersenne.org/articles/10.5802/alco.30/
DO  - 10.5802/alco.30
LA  - en
ID  - ALCO_2019__2_3_367_0
ER  -

%0 Journal Article
%A Kalai, Gil
%A Nevo, Eran
%T Turán, involution and shifting
%J Algebraic Combinatorics
%D 2019
%P 367-378
%V 2
%N 3
%I MathOA foundation
%U https://alco.centre-mersenne.org/articles/10.5802/alco.30/
%R 10.5802/alco.30
%G en
%F 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/articles/10.5802/alco.30/

References
Cited by

[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, Paper no. R137, 23 pages | MR | Zbl

[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 | 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

Cited by Sources: