%~Mouliné par MaN_auto v.0.21.2 2019-02-21 09:02:05
\documentclass[ALCO, ThmDefs, Unicode]{cedram}
\OneNumberAllTheorems
\DeclareMathOperator{\sh}{Shift}
\DeclareMathOperator{\rank}{rank}
\renewcommand{\tilde}{\widetilde}
\graphicspath{{./figures/}}
\newcommand*{\mk}{\mkern -1mu}
\newcommand*{\Mk}{\mkern -2mu}
\newcommand*{\mK}{\mkern 1mu}
\newcommand*{\MK}{\mkern 2mu}
\hypersetup{urlcolor=purple, linkcolor=blue, citecolor=red}
\newcommand*{\romanenumi}{\renewcommand*{\theenumi}{\roman{enumi}}}
\newcommand*{\Romanenumi}{\renewcommand*{\theenumi}{\Roman{enumi}}}
\newcommand*{\alphenumi}{\renewcommand*{\theenumi}{\alph{enumi}}}
\newcommand*{\Alphenumi}{\renewcommand*{\theenumi}{\Alph{enumi}}}
\title{Tur\'{a}n, involution and shifting}
\author{\firstname{Gil} \lastname{Kalai}}
\address{Einstein Institute of Mathematics\\
The Hebrew University of Jerusalem\\
Jerusalem (Israel)}
\email{kalai@math.huji.ac.il}
\author{\firstname{Eran} \lastname{Nevo}}
\address{Einstein Institute of Mathematics\\
The Hebrew University of Jerusalem\\
Jerusalem (Israel)}
\email{nevo@math.huji.ac.il}
\thanks{Research of Kalai is partially supported by ERC advanced grant 320924, BSF grant 2006066, and NSF grant DMS-1300120, and of Nevo by Israel Science Foundation grant ISF-1695/15, by grant 2528/16 of the ISF-NRF Singapore joint research program, and by ISF-BSF joint grant 2016288.}
\keywords{Tur\'{a}n's $(3,4)$-conjecture, shifting, threshold graphs}
%\subjclass{missing MSC}
\begin{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.
\end{abstract}
\begin{document}
\maketitle
\section{Introduction}
Let $T(n)$ be a graph on the vertex set $[n]=\{1,2,\ldots,n\}$ which is the disjoint union of two cliques of sizes $\lfloor\frac{n}{2}\rfloor$ and $\lceil\frac{n}{2}\rceil$. Our starting point is the following influential Mantel--Tur\'{a}n theorem~\cite{Mantel, Turan}.
\begin{theo}[Mantel, Tur\'{a}n]\label{thm:Turan}
Let $G$ be a graph on $[n]$ where every $3$-subset of $[n]$ contains an edge of $G$. Then the edge sets satisfy
\[
|E(G)|\geq |E(T(n))|.
\]
\end{theo}
Let $B(n)$ be the set of edges on $[n]$
\[
B(n)=\{ab: 1\leq a**=\mathbb{Z}_2$ acts trivially on $[n]$, then the conditions in both theorems coincide.
Second, if $\tau$ acts on $[n]$ with at most one fixed point, then by applying a suitable permutation of the vertices we can assume $\tau(i)=n+1-i$ for any $i\in [n]$. For this $\tau$, $(B(n),\tau)$ satisfies the assumptions of Theorem~\ref{thm:pairs}.
We now turn to an algebraic statement that implies Theorem~\ref{thm:Turan}. First we define the notion of domination.
Let $X=(x_{i,j})$ be an $n\times n$ matrix of variables, and $C_k(X)=(c_{S,T})$ its $k$-th \emph{compound} matrix, namely the $\binom{n}{k}\times \binom{n}{k}$ matrix, where for $k$-subsets $S,T$ of $[n]$, $c_{S,T}$ equals the determinant of the $(S,T)$-minor of $X$, computed in the field extension $\mathbb{Q}(x_{i,j})$ over the rationales say. Let $F_1$ and $F_2$ be two families of $k$-subsets of $[n]$. Then $F_1$ \emph{dominates} $F_2$ if the submatrix of $C_k(X)$ with rows indexed by $F_2$ and columns indexed by $F_1$ has rank $|F_2|$. This implies, of course, that $|F_2| \le |F_1|$.
\begin{theo}[Tur\'{a}n with domination]\label{thm:domination_Turan}
Let $G$ be a graph on $[n]$ where every $3$-subset of $[n]$ contains an edge of $G$. Then $E(G)$ dominates $B(n)$.
\end{theo}
We prove this statement via exterior algebraic shifting, introduced by Kalai~\cite{Kalai_ext_shift}, and via relations between algebraic and combinatorial shifting established by Hibi and Murai~\cite{Murai-Join, Murai-Hibi}. (We can apply algebraic shifting w.r.t. any fixed term order $<_t$ that satisfies $ab<_t a'b'$ whenever $a+b2$.
\begin{proof}[First Step]
Assume there exists $i\in [n]$ such that the edge $\{i,\tau(i)\}\notin E(G)$. For any triple $T=\{i,\tau(i),j\}$, $T$ and $\tau(T)=\{i,\tau(i),\tau(j)\}$ support at least two edges of $G$, thus there are at least $n-2$ edges between $V\setminus \{i,\tau(i)\}$ and $\{i,\tau(i)\}$. By induction,
\[
|E(G)|\geq n-2+|E(G[V\setminus \{i,\tau(i)\}])|\geq n-2+|E(T(n-2))|=|E(T(n))|.
\]
Thus, assume $\{i,\tau(i)\}\in E(G)$ for every $i\in [n]$.
\let\qed\relax
\end{proof}
\begin{proof}[Second Step]
Consider the case where $G$ contains an \emph{induced} matching with two edges $M=(V_M, E_M)$, $E_M=\{i\tau(i), j\tau(j)\}$. For any vertex $k\notin V_M$ the two triples $ijk$ and $\tau(i)\tau(j)\tau(k)$ support at least 2 edges, and the two triples $ij\tau(k), \tau(i)\tau(j)k$ support at least 2 edges, so there are at least 4 edges between $V_M$ and $\{k,\tau(k)\}$. All together, there are at least $2(n-4)$ edges in the cut $(V_M,V\setminus V_M)$. By induction, and as the edges $i\tau(i)$ and $j\tau(j)$ exist,
\begin{align*}
|E(G)|&\geq 2+2(n-4)+|E(G[V\setminus V_M])|\\
&\geq (n-2)+(n-4)+|E(T(n-4))|=|E(T(n))|.
\end{align*}
Thus, assume further that
\begin{enumerate}[($\ast$)]
\item \label{ast2} for any $j\neq i,\tau(i)$, there is a crossing edge from $\{i,\tau(i)\} \text{ to }\{j,\tau(j)\}$.
\end{enumerate}
\let\qed\relax
\end{proof}
\begin{proof}[Third Step]
We define 3 auxiliary graphs, $W=([m],E_W)$, $Z=([m],E_Z)$ and $R=([m],E_R)$ as follows: $ij\in E_W / E_Z / E_R$ iff there exists, resp., exactly one/ exactly two/ at least $3$ edges in $G$ crossing from $\{i,\tau(i)\}$ to $\{j,\tau(j)\}$. Let $N_X(x)$ denote the set of neighbors of vertex $x$ in a graph $X$.
\begin{lemm}\label{lem:W}
If $j,k\in N_W(i)$, $j\neq k$, then there exist at least 3 edges in $G$ crossing from $\{k,\tau(k)\}$ to $\{j,\tau(j)\}$. In particular, $W$ is triangle free.
\end{lemm}
\begin{proof}[Proof of Lemma~\ref{lem:W}]
By interchanging the labeling of $v$ and $\tau(v)$ if needed, we can assume that either
\begin{enumerate}[(a)]
\item \label{p4.1.1} $ij,\tau(i)\tau(k)\in E(G)$, or
\item \label{p4.1.2} $ij,ik\in E(G)$.
\end{enumerate}
In case~\ref{p4.1.1}: the two triples $i\tau(j)\tau(k)$ and $\tau(i)jk$ support at least 2 edges, so $jk,\tau(j)\tau(k)\in E(G)$. Likewise, the two triples $ij\tau(k)$ and $\tau(i)\tau(j)k$ support at least 2 edges, one of them is $ij$, so at least one of $j\tau(k),\tau(j)k$ is in $G$; in total we found $3$ crossing edges from $\{k,\tau(k)\}$ to $\{j,\tau(j)\}$.
In case~\ref{p4.1.2}: similarly, considering the two triples $i\tau(j)\tau(k), \tau(i)jk$ implies $jk,\tau(j)\tau(k)\in E(G)$, and considering the two triples $ij\tau(k), \tau(i)\tau(j)k$ implies that at least one of $j\tau(k),\tau(j)k$ is in $E(G)$; in total we found $3$ crossing edges from $\{k,\tau(k)\}$ to $\{j,\tau(j)\}$ in this case as well.
\end{proof}
By definition, clearly the edge sets $E_W, E_R, E_Z$ are pairwise disjoint, so $|E(G)|\geq m+|E(W)|+3|E(R)|+2|E(Z)|$. By Lemma~\ref{lem:W}, the graph $R$ contains the union of cliques $\cup_{v\in [m]}K_{N_W(v)}$. Thus, the following claim, of independent interest, finishes the proof of the even case $n=2m$ (details follow):
\begin{enonce}{Claim}\label{claim:T-free}
Let $X$ be a triangle free graph on $m$ vertices, and define the graph $Y=Y(X)=\cup_{v\in X}K_{N_X(v)}$. Then
\[
|E(Y)|+\left\lfloor\frac{m}{2}\right\rfloor \geq |E(X)|.
\]
\end{enonce}
\begin{rema}
The Mantel--Tur\'{a}n theorem (phrased for the complementary graph w.r.t. Theorem~\ref{thm:Turan}) easily follows from this claim, combined with the trivial inequality $|E(X)|+|E(Y)|\leq \binom{m}{2}$. Indeed, we get $2|E(X)|-\lfloor\frac{m}{2} \rfloor \leq \binom{m}{2}$, equivalently $|E(X)|\leq \lfloor \frac{m^2}{4}\rfloor$.
While in the Mantel--Tur\'{a}n theorem equality holds only for the complete bipartite graph $K_{\lfloor \frac{m}{2}\rfloor,\lceil \frac{m}{2}\rceil}$, in Claim~\ref{claim:T-free} equality holds for more graphs, e.g. for perfect matchings.
\end{rema}
\begin{proof}[Proof of Claim~\ref{claim:T-free}]
We give an easy proof by induction on $m$. The assertion is clear for $E(X)=\emptyset$, and for the case $m\leq 2$; assume $m\geq 3$ and $uw\in E(X)$. As $X$ is triangle free, $N_X(u)\cap N_X(w)=\emptyset$. By the definition of $Y$, for any $u \neq w'\in N_X(w)$, and for any $w \neq u'\in N_X(u)$, we have $uw',u'w\in E(Y)$. Thus,
\begin{align*}
|E(Y)|&\geq |E(Y(X-\{u,w\}))|+|N_{X-u}(w)|+|N_{X-w}(u)|\\
&\geq |E(X-\{u,w\})|-\left\lfloor\frac{m-2}{2}\right\rfloor + |E_X(\{u,w\},V_X-\{u,w\})|\\
&= |E(X)|-1 -\left(\left\lfloor\frac{m}{2}\right\rfloor -1\right),
\end{align*}
as desired, where the second inequality is by the induction hypothesis, and the first ``$-1$'' stands for the edge $uw$. $E_X(A,V-A)$ stands for edges of $X$ in the cut from $A$ to its complement.
\end{proof}
Back to the proof of the free action case of Theorem~\ref{thm:pairs}, we get
\[
|E(G)|\geq m+|E(W)|+3|E(R)|+2|E(Z)|\geq m+2\binom{m}{2}-\left\lfloor\frac{m}{2}\right\rfloor > |E(T(2m))|,
\]
as desired, where we used Claim~\ref{claim:T-free} for the second inequality.
\let\qed\relax
\end{proof}
\let\qed\relax
\end{proof}
\begin{proof}[General case]
The proof is similar to the free action case; we indicate the differences, and keep the notations from the proof of the previous case. W.l.o.g. $n=2m+l$, $\tau(i)=2m+1-i$ for $i\in [2m]$, and $\tau(z)=z$ for $2m+1\leq z\leq n$.
\begin{proof}[First Step]
Note that for any $i\in [2m]$, $z\in [2m+1,n]$ and $T=\{i,\tau(i),z\}$, $\tau(T)=T$, so $T$ must support an edge of $G$, and as in the free action case we conclude there are at least $n-2$ edges crossing from $\{i,\tau(i)\}$ to $V(G)-\{i,\tau(i)\}$. So assume all edges $i\tau(i)$ exist in $G$. By the same reasoning, also assume that any two fixed points form an edge in $G$.
\let\qed\relax
\end{proof}
\begin{proof}[Second Step]
The triples $T=ijz$ and $\tau(T)=\tau(i)\tau(j)z$, for $z$ a fixed point, support at least 2 edges of $G$, both contain the vertex $z$, and again we conclude there are at least $2(n-4)$ edges in $G$ crossing from $\{i,j,\tau(i),\tau(j)\}$ to the complementary set of vertices. So assume there is at least one crossing edge from $\{i,\tau(i)\}$ to $\{j,\tau(j)\}$. By similar reasoning, we can assume there is at least one edge crossing from $\{i,\tau(i)\}$ to any pair of fixed points $\{z,z'\}$.
\let\qed\relax
\end{proof}
\begin{proof}[Third Step]
Define the graphs $W, R, Z$ on the vertex set $[m]$ as before, and define bipartite graphs $W'',Z'', R''$ with edges crossing from $[m]$ to $[2m+1,n]$ as follows: for $z\in [2m+1,n]$ and $i\in [m]$ $iz\in E(W'') / E(Z'') / E(R'')$ iff, resp., in $G$ there are exactly $0/1/2$ crossing edges from $z$ to $\{i,\tau(i)\}$. Let $W'=W\cup W''$, and similarly define the graphs $Z'$ and $R'$. For a graph $H$ denote $e(H):=|E(H)|$. Thus,
\[
e(W')+e(R')+e(Z')+\binom{l}{2}=\binom{m+l}{2}.
\]
In order to lower bound the number of edges in $G$, we need the following analog of Lemma~\ref{lem:W}: for any $z\in [2m+1,n]$ and $i,j\in [m]$, $i\neq j$, we have
\begin{enumerate}[(a)]
\item \label{a} if $i,j\in N_{W'}(z)$ then there exist all $4$ crossing edges from $\{i,\tau(i)\}$ to $\{j,\tau(j)\}$ in $G$, and
\item \label{b} if $i,z\in N_{W'}(j)$ then there exist all $2$ crossing edges from $\{i,\tau(i)\}$ to $z$ in $G$.
\end{enumerate}
The verification of~\ref{a} and~\ref{b} is similar to the proof of Lemma~\ref{lem:W}.
We estimate $|E(G)|$:
\begin{align*}
e(G)&\geq \left(m+\binom{l}{2}\right) + (3e(R)+2e(Z)+e(W)) + (2e(R'')+e(Z''))\\
&\geq m+\binom{l}{2} + \left(e(W')-\left\lfloor\frac{m+l}{2}\right\rfloor\right) + 2e(R)+2e(Z)+e(W) + e(R'')+ e(Z'')\\
&= m+\binom{m+l}{2}-\left\lfloor\frac{m+l}{2}\right\rfloor+e(R)+e(Z)+e(W)\\
&= m-\left\lfloor\frac{m+l}{2}\right\rfloor+\binom{m+l}{2}+\binom{m}{2},
\end{align*}
where in the first inequality the first summand accounts for edges from the first step and the other summands are by definition of $W',R',Z'$; the second inequality follows from combining the second and third steps with Claim~\ref{claim:T-free}, yielding $e(R)+e(R'')\geq e(W')-\lfloor\frac{m+l}{2}\rfloor$; and the equalities are by the definition of $W',R',Z'$ (and of $W,R,Z$).
Now, one verifies by a direct computation that the RHS is indeed $>e(T(2m+l))$. This completes the proof of Theorem~\ref{thm:pairs}.
\end{proof}
\let\qed\relax
\end{proof}
\let\qed\relax
\end{proof}
\begin{rema}
Unlike Theorem~\ref{thm:Turan}, where the extremal example is unique, in Theorem~\ref{thm:pairs}, for $\tau(i)=n+1-i$ say, there are multiple extremal examples. In fact, following the first and second steps in the proof gives a recursive way to construct all of them, as labeled graphs. It may be of interest to characterize / count these extremal examples up to graph isomorphism.
\end{rema}
\begin{rema}\label{rem:1.2+1.3}
In support of Problem~\ref{prob:1.2+1.3} we note that if $G$ is a shifted graph on $[n]$ satisfying~\eqref{e:inv} w.r.t. the involution $\tau(i)=n+1-i$, then $E(G)\supseteq B(n)$, so $E(G)$ dominates $B(n)$. Indeed, assume by contradiction that $ab \in B(n)\setminus E(G)$, $a**