text:
\section{Introduction and main results} \cntrs
\label{s:intro}

Let $M^{2n}$ be a closed symplectic $2n$-dimensional manifold. Assume
further that $M$ is monotone with minimal Chern number $C_M$
(see~\S\ref{sb:monotone} below for the definitions). Denote by $QH(M)$
the quantum homology of $M$ with coefficients in the ring
$\mathbb{\mathbb{Z}}[q]$, where the degree of the variable $q$ is
$|q|=-2$. Denote by $*$ the quantum product on $QH(M)$ and for a class
$a \in QH(M)$, $k \in \mathbb{N}$, we write $a^{*k}$ for the $k$'th
power of $a$ with respect to this product.

Let $S \subset M$ be an oriented Lagrangian $n$-sphere. Denote by $[S]
\in QH_n(M)$ the homology class represented by $S$ in the quantum
homology of $M$. Our first result shows that $[S]$ always satisfies a
cubic or quadratic equation of a very specific type:
\begin{mainthm} \label{t:cubic-eq-sphere}
   \begin{enumerate}
     \item \label{i:n-odd} If $n=$~odd then $[S]*[S]=0$.
     \item Assume $n=$~even. Then:
      \begin{enumerate}[(i)]
        \item \label{i:div} If $C_M | n$ then there exists a unique
         $\gamma_S \in \mathbb{Z}$ such that $[S]^{*3} = \gamma_S [S]
         q^{n}$. If we assume in addition that $2C_M \centernot| n$,
         then $\gamma_S$ is divisible by $4$, while if $2C_M | n$ then
         $\gamma_S$ is either $0 (\bmod \,4)$ or $1 (\bmod \,4)$.
        \item \label{i:ndiv} If $C_M \centernot| n$ then $[S]^{*3} =
         0$.
      \end{enumerate}
   \end{enumerate}
\end{mainthm}

The proof of Theorem~\ref{t:cubic-eq-sphere}, given
in~\S\ref{sb:prf-cubic-eq-S}, follows from a simple argument involving
Lagrangian Floer homology.  The cases~\eqref{i:n-odd},~\eqref{i:ndiv}
are particularly simple, whereas case~\eqref{i:div} splits into two
sub-cases:
\begin{enumerate}
  \item [(2i-a)] \label{i:2CM-n} $2C_M | n$.
  \item[(2i-b)] \label{i:CM-n} $C_M | n$, but $2C_M \centernot| n$.
\end{enumerate}
We will see below that out of these two sub-cases the most interesting
is~(2i-a). In that case the constant $\gamma_S$ has other
interpretations coming from Floer theory and enumerative geometry of
holomorphic disks. These will be explained in detail in the sequel.

\begin{rem}
   \begin{enumerate}
     \item When $n$ is even it is easy to see that $[S]
     \in H_n(M)$ is neither $0$ nor a torsion class. Therefore in that
      case $\gamma_S$ is uniquely determined.
     \item Points~\eqref{i:n-odd} and~\eqref{i:ndiv} of the theorem
      cover the symplectically aspherical case (i.e.
      $[\omega]|_{\pi_2(M)}=0$) if we set $C_M = \infty$. Of course,
      the statement in that case is completely obvious.
     \item A version of Theorem \ref{t:cubic-eq-sphere} also holds
     in the non-monotone case for Lagrangian 2-spheres, the precise
     statement can be found in~\S\ref{s:non-monotone}.
    \item Theorem~\ref{t:cubic-eq-sphere} continues to hold also when
     $S$ is a $\mathbb{Z}$-homology sphere, except possibly when $2C_M
     | n$.  The difference between the case $2C_M | n$ and the others
     is that in that case $[S]$ a priori satisfies only the cubic
     equation~\eqref{eq:cubic-L} from Theorem~\ref{t:cubic-eq} below.
     For the vanishing of the coefficient of $[S]^{*2}$ we will use
     the Dehn twist along $S$ (see Corollary~\ref{c:sig=0} and the
     short discussion after it), hence we need to assume that $S$ is
     diffeomorphic to a sphere. At the same time we are not aware of
     interesting computable examples where $S$ is a
     $\mathbb{Z}$-homology sphere yet not a genuine sphere.
   \end{enumerate}
\end{rem}

For the rest of the introduction we concentrate on case~(2i-a) and its
possible generalizations. Assume from now on that $L \subset M$ is a
Lagrangian submanifold (not necessarily a sphere). Denote by
$HF_*(L,L)$ the self Floer homology of $L$ with coefficients in
$\mathbb{Z}$. See~\S\ref{s:floer-setting} for the Floer theoretical
setting. In what follows we will recurringly appeal to the following
set of assumptions or to a subset of it:
\begin{assumption-L}
   \begin{enumerate}
     \item $L$ is closed (i.e. compact without boundary). Furthermore
      $L$ is monotone with minimal Maslov number $N_L$ that satisfies
      $N_L \mid n$ (see~\S\ref{sb:monotone} for the definitions). Set
      $\nu = n/N_L$.
     \item $L$ is oriented. Moreover we assume that $L$ is spinable
      (i.e. can be endowed with a spin structure).
     \item $HF_n(L,L)$ has rank $2$.
     \item Write $\chi = \chi(L)$ for Euler-characteristic of $L$. We
      assume that $\chi \neq 0$.
   \end{enumerate}
\end{assumption-L}
Note that conditions $(1)$ and $(2)$ together imply that $n=$ even,
since orientable Lagrangians have $N_L=$ even. Independently,
conditions $(2)$ and $(4)$ also imply that $n=$even. As we will see
later there are many Lagrangian submanifolds that satisfy
Assumption~$\mathscr{L}$ -- for example, even dimensional Lagrangian
spheres in monotone symplectic manifolds $M$ with $2C_M | n$.
See~\S\ref{sb:exps} and~\S\ref{s:examples} for more examples.

\pbred{Unless otherwise stated, from now on we implicitly assume all
  Lagrangian submanifolds to be connected.}

\subsection{The Lagrangian cubic equation} \label{sb:lcubic-eq} Here
we need to work with $\mathbb{Q}$ as the base ring. Denote by $QH(M;
\mathbb{Q}[q])$ the quantum homology of $M$ with coefficients in the
ring $\mathbb{Q}[q]$. Given an oriented Lagrangian submanifold $L
\subset M$ denote by $[L] \in QH_n(M;\mathbb{Q}[q])$ its homology
class in the quantum homology of the ambient manifold $M$. We will
also make use of the following notation $\varepsilon =
(-1)^{n(n-1)/2}$.

Our first result is the following.
\begin{mainthm}[The Lagrangian cubic equation] \label{t:cubic-eq} Let
   $L \subset M$ be a Lagrangian submanifold satisfying
   assumption~$\mathscr{L}$. Then there exist unique \cmred{constants
     $\sigma_L \in \tfrac{1}{\chi^2}\mathbb{\mathbb{Z}}$, $\tau_L \in
     \tfrac{1}{\chi^3} \mathbb{Z}$} such that the following equation
   holds in $QH(M;\mathbb{Q}[q])$:
   \begin{equation} \label{eq:cubic-L} [L]^{*3} - \varepsilon \chi
      \sigma_L [L]^{*2}q^{n/2} - \chi^2 \tau_L [L]q^{n} = 0.
   \end{equation}
   \cmred{If $\chi$ is square-free then $\sigma_L \in
     \tfrac{1}{\chi}\mathbb{Z}$ and $\tau_L \in
     \tfrac{1}{\chi^2}\mathbb{Z}$.} Moreover, the constant $\sigma_L$
   can be expressed in terms of genus $0$ Gromov-Witten invariants as
   follows:
   \begin{equation} \label{eq:GW-LLL} \sigma_L = \frac{1}{\chi^2}
      \sum_A GW^M_{A,3}([L],[L],[L]),
   \end{equation}
   where the sum is taken over all classes $A \in H_2(M)$ with
   $\langle c_1, A \rangle = n/2$.
\end{mainthm}

In~\S\ref{s:lag-cubic-eq} we will prove a more general result
concerning a Lagrangian submanifold $L$ and an arbitrary class $c \in
H_n(M)$ which satisfies $c \cdot [L] \neq 0$. We will prove that they
satisfy a mixed equation of degree three involving $[L]$ and $c$.
Equation~\eqref{eq:cubic-L} is the special case $c = [L]$.

Here is an immediate corollary of Theorem~\ref{t:cubic-eq}:
\begin{maincor} \label{c:sig=0} Let $L \subset M$ be a Lagrangian
   submanifold satisfying Assumption $\mathscr{L}$. Assume in addition
   that there exists a symplectic diffeomorphism $\varphi: M
   \longrightarrow M$ such that $\varphi_*([L]) = -[L]$. Then
   $\sigma_L = 0$, hence equation~\eqref{eq:cubic-L} reads in this
   case:
   \begin{equation*}
      [L]^{*3} - \chi^2 \tau_L [L]q^{n} = 0.
   \end{equation*}

\end{maincor}
When $L$ is a Lagrangian sphere in a symplectic manifold $M$ with
$2C_M | n$ then point~\eqref{i:div} of Theorem~\ref{t:cubic-eq-sphere}
follows from Corollary~\ref{c:sig=0}. Indeed, we can take $\varphi$ to
be the Dehn twist along $L$. The Picard-Lefschetz formula (see
e.g.~\cite{Dimca:sing-hyper-book, Ar:sing-theory-I}) gives
$\varphi_*([L]) = -[L]$ since $n=\dim L$ is even and $\chi = 2$.
Corollary~\ref{c:sig=0} then implies that $\sigma_L = 0$ (and we have
$\gamma_L = 4 \tau_L$).  \cmred{ Note that in this case we have
  $\tau_L \in \tfrac{1}{4}\mathbb{Z}$.}

\begin{proof}[Proof of Corollary~\ref{c:sig=0}]
   Applying $\varphi_*$ to the equation~\eqref{eq:cubic-L} and
   comparing the result to~\eqref{eq:cubic-L} yields $\varepsilon \chi
   \sigma_L [L]^{*2}=0$. Since $\chi \neq 0$ it follows that $\sigma_L
   [L]^{*2}=0$. But $[L] \cdot [L] = \varepsilon \chi \neq 0$, hence
   $[L]^{*2} \neq 0$. This implies that $\sigma_L=0$.
\end{proof}

\subsection{The discriminant} \label{sb:discr-intro} \cntrsb Let $A$
be a quadratic algebra over $\mathbb{Z}$. By this we mean that $A$ is
a commutative unital ring such that $\mathbb{Z}$ embeds as a subring
of $A$, $\mathbb{Z} \to A$, and furthermore that $A/\mathbb{Z} \cong
\mathbb{Z}$. Thus the underlying additive abelian group of $A$ is a
free abelian group of rank $2$. Pick a generator $p \in A/\mathbb{Z}$
so that $A/\mathbb{Z} = \mathbb{Z} p$. We have the following exact
sequence:
\begin{equation} \label{eq:ex-seq-A} 0 \longrightarrow \mathbb{Z}
   \longrightarrow A \xrightarrow{\;\;\epsilon \;\;} \mathbb{Z} p
   \longrightarrow 0,
\end{equation}
where the first map is the ring embedding and $\epsilon$ is the
obvious projection.  Choose a lift $x \in A$ of $p$, i.e. $\epsilon(x)
= p$. Then additively we have $A \cong \mathbb{Z} x \oplus
\mathbb{Z}$.  With these choices there exist $\sigma(p,x), \tau(p,x)
\in \mathbb{Z}$ such that $$x^2 = \sigma(p,x) x + \tau(p,x).$$ The
integers $\sigma(p,x), \tau(p,x)$ depend on the choices of $p$ and of
$x$.  However, a simple calculation (see~\S\ref{sbsb:discr-well-def})
shows that the following expression
\begin{equation} \label{eq:discr-A} \Delta_A := \sigma(p,x)^2 + 4
   \tau(p,x) \in \mathbb{Z}
\end{equation}
is independent of $p$ and $x$, hence is an invariant of the
isomorphism type of $A$. In fact in~\S\ref{sbsb:discr-inv-class} we
show that $\Delta_A$ determines the isomorphism type of $A$. We call
$\Delta_A$ the discriminant of $A$.

\begin{remsnonum}
   \begin{enumerate}
     \item Another description of $\Delta_A$ is the following. Write
      $A$ as $A \cong \mathbb{Z}[T] / (f(T))$, where $f(T) \in
      \mathbb{Z}[T]$ is a monic quadratic polynomial. Then $\Delta_A$
      is the discriminant of $f(T)$ (and is independent of the choice
      of $f(T)$). In particular $A_{\mathbb{C}} := A \otimes
      \mathbb{C}$ is semi-simple iff $\Delta_A \neq 0$.
     \item When $\Delta_A$ is not a square $A_{\mathbb{Q}} := A
      \otimes \mathbb{Q}$ is a quadratic number field. The
      discriminant $\Delta_A$ is related to the discriminant of
      $A_{\mathbb{Q}}$ as defined in number theory.
     \item It is easy to see from~\eqref{eq:discr-A} that the only
      values $\Delta_A (\bmod \,4)$ can assume are $0$ and $1$.
   \end{enumerate}
\end{remsnonum}

Let $L$ be a Lagrangian submanifold satisfying conditions $(1)-(3)$ of
Assumption~$\mathscr{L}$ and choose a spin structure on $L$ compatible
with its orientation. Consider $A = HF_n(L,L)$ endowed with the
Donaldson product $$*: HF_n(L,L) \otimes HF_n(L,L) \longrightarrow
HF_n(L,L), \quad a \otimes b \longmapsto a*b.$$ Recall that $A$ is a
unital ring with a unit which we denote by $e_L \in HF_n(L,L)$. The
conditions $(1)-(3)$ of Assumption~$\mathscr{L}$ ensure that $A$ is a
quadratic algebra over $\mathbb{Z}$. (In case $A$ has torsion we just
replace it by $A/T$, where $T$ is its torsion ideal.) Denote by
$\Delta_L$ the discriminant of $A$, $\Delta_L := \Delta_A$ as defined
in~\eqref{eq:discr-A}. (We suppress here the dependence on the spin
structure, as we will soon see that in our case $\Delta_L$ does not
depend on it.)

The following theorem shows that the discriminant $\Delta_L$ depends
only on the class $[L] \in QH_n(M)$ and can be computed by means of
the ambient quantum homology of $M$.
\begin{mainthm} \label{t:rel-to-discr} Let $L \subset M$ be a
   Lagrangian submanifold satisfying Assumption~$\mathscr{L}$. Let
   $\sigma_L, \tau_L \in \mathbb{Q}$ be the constants from the cubic
   equation~\eqref{eq:cubic-L} in Theorem~\ref{t:cubic-eq}. Then
   $$\Delta_L = \sigma_L^2 + 4 \tau_L.$$
\end{mainthm}
The proof appears in~\S\ref{s:lag-cubic-eq}.
\begin{remsnonum}
   \begin{enumerate}
     \item \textbf{Warning:} The pair of coefficients $\sigma_L,
      \tau_L$ and $\sigma(p,x), \tau(p,x)$ should not be confused.
      The first pair is always uniquely determined by $[L]$ and can be
      read off the ambient quantum homology of $M$ via the cubic
      equation~\eqref{eq:cubic-L}. In contrast, the second pair
      $\sigma(p,x), \tau(p,x)$ are defined via Lagrangian Floer
      homology and strongly depend on the choice of the lift $x$ of
      $p$. For example, we have seen that if $L$ is a sphere then
      $\sigma_L=0$, but as we will see later (e.g.
      in~\S\ref{s:disc-lcob}) for some (useful) choices of $x$ we have
      $\sigma(p,x) \neq 0$. Additionally, $\sigma(p,x), \tau(p,x) \in
      \mathbb{Z}$ while $\sigma_L, \tau_L \in \mathbb{Q}$. Still, the
      two pairs of coefficients are related in that $\sigma(p,x)^2 + 4
      \tau(p,x) = \sigma_L^2 + 4 \tau_L = \Delta_L$.

      As we will see in the proof of Theorem~\ref{t:rel-to-discr}, the
      coefficients $\sigma_L, \tau_L$ do occur as $\sigma(p,x_0),
      \tau(p,x_0)$ but for a special choice of $x_0$, which however
      requires working over $\mathbb{Q}$.

     \item A different version of the discriminant $\Delta_L$ was
      previously defined and studied by Biran-Cornea
      in~\cite{Bi-Co:lagtop}. In that paper the discriminant occurs as
      an invariant of a quadratic form defined on $H_{n-1}(L)$ via
      Floer theory. In the case $L$ is a $2$-dimensional Lagrangian
      torus the discriminant from~\cite{Bi-Co:lagtop} and $\Delta_L$,
      as defined above, happen to coincide due to the associativity of
      the product of $HF_n(L,L)$.  Moreover, in dimension $2$,
      $\Delta_L$ has an enumerative description in terms of counting
      holomorphic disks with boundary on $L$ which satisfy certain
      incidence conditions. This description continues to hold also
      for $2$-dimensional Lagrangian spheres with $N_L = 2$ (or more
      generally for all $2$-dimensional Lagrangian submanifolds
      satisfying Assumption~$\mathscr{L}$) and the proof is the same
      as in~\cite{Bi-Co:lagtop}.
     \item Since $\sigma_L, \tau_L$ do not depend on the spin
      structure chosen for $L$ (although $\sigma(p,x)$ and $\tau(p,x)$
      do) it follows from Theorem~\ref{t:rel-to-discr} that $\Delta_L$
      does not depend on that choice either. As for the orientation on
      $L$, if we denote $\bar{L}$ the Lagrangian $L$ with the opposite
      orientation then it follows from Theorem~\ref{t:cubic-eq} that
      $\sigma_{\bar{L}} = - \sigma_{L}$ and $\tau_{\bar{L}} = \tau_L$.
      In particular $\Delta_{\bar{L}} = \Delta_L$.
   \end{enumerate}
\end{remsnonum}

The next theorem is concerned with the behavior of the discriminant
under Lagrangian cobordism. We refer the reader to~\cite{Bi-Co:cob1}
for the definitions.

\begin{mainthm} \label{t:cob} Let $L_1, \ldots, L_r \subset M$ be
   monotone Lagrangian submanifolds, each satisfying conditions $(1)$
   -- $(3)$ of Assumption~$\mathscr{L}$. Let $V^{n+1} \subset
   \mathbb{R}^2 \times M$ be a connected monotone Lagrangian cobordism
   whose ends correspond to $L_1, \ldots, L_r$ and assume that $V$
   admits a spin structure. Denote by $N_V$ the minimal Maslov number
   of $V$ and assume that:
   \begin{enumerate}

     \item $H_{j N_V}(V,\partial V) = 0$ for every $j$.
     \item $H_{1+jN_V}(V) = 0$ for every $j$.
   \end{enumerate}
   Then $\Delta_{L_1} = \cdots = \Delta_{L_r}$. Moreover if $r \geq 3$
   then $\Delta_{L_i}$ is a perfect square for every $i$.
\end{mainthm}
The proof is given in~\S\ref{s:disc-lcob}. As a corollary we obtain:
\begin{maincor} \label{c:del_1=del_2} Let $(M, \omega)$ be a monotone
   symplectic manifold with $2 C_M \mid n$, where $C_M$ is the minimal
   Chern number of $M$. Let $L_1, L_2 \subset M$ be two Lagrangian
   spheres that intersect transversely at exactly one point. Then
   $\Delta_{L_1} = \Delta_{L_2}$ and moreover this number is a perfect
   square.
\end{maincor}
We will in fact prove a stronger result in~\S\ref{sb:lag-1-pt} (see
Corollary~\ref{c:L1-L2-1pt}).

\subsection{Examples} \label{sb:exps} \cntrsb

We begin with a topological criterion that assures that condition~(3)
in Assumption~$\mathscr{L}$ is satisfied. This provides us with examples
of Lagrangian submanifolds to which the theory applies.
\begin{mainprop} \label{p:criterion} Let $L \subset M$ be an oriented
   Lagrangian submanifold satisfying condition~$(1)$ of
   Assumption~$\mathscr{L}$. Assume in addition that:
   \begin{enumerate}
     \item $[L] \neq 0 \in H_n(M;\mathbb{Q})$ (this is satisfied e.g.
      when $\chi(L) \neq 0$).
     \item $H_{j N_L}(L) = 0$ for every $0<j<\nu$.
   \end{enumerate}
   Then condition $(3)$ in Assumption~$\mathscr{L}$ is satisfied too.
   In particular Lagrangian spheres $L$ that satisfy condition $(1)$
   of Assumption~$\mathscr{L}$ satisfy the other three conditions in
   Assumption~$\mathscr{L}$.
\end{mainprop}
The proof appears in~\S\ref{sb:prf-p-criterion}.

We now provide a sample of examples. More details will be given
in~\S\ref{s:examples}

\subsubsection{Lagrangian spheres in blow-ups of $\mathbb{C}P^2$}
\label{sbsb:intro-exp-blcp2}

Let $(M_k, \omega_k)$ be the monotone symplectic blow-up of
${\mathbb{C}}P^2$ at $2 \leq k \leq 6$ points. We normalize $\omega_k$
so that it is cohomologous to $c_1$. Denote by $H \in H_2(M_k)$ the
homology class of a line not passing through the blown up points and
by $E_1, \ldots, E_k \in H_2(M_k)$ the homology classes of the
exceptional divisors over the blown up points. With this notation the
Poincar\'{e} dual of the cohomology class of the symplectic form
$[\omega_k] \in H^2(M_k)$ satisfies $$PD [\omega_k] = PD(c_1) = 3H -
E_1 - \cdots - E_k.$$

The Lagrangian spheres $L \subset M_k$ lie in the following homology
classes (see~\S\ref{sb:lag-spheres-blow-ups} for more details):
\begin{enumerate}
  \item For $k=2$: $\pm (E_1 - E_2)$.
  \item For $2 \leq k \leq 5$: $\pm(E_i - E_j)$, $i < j$, and $\pm(H -
   E_i - E_j - E_l)$ with $i<j<l$.
  \item For $k=6$ we have the same homology classes as in~$(2)$ and in
   addition the class $\pm(2H - E_1 - \cdots - E_6)$.
\end{enumerate}
Note that all these Lagrangian spheres satisfy
Assumption~$\mathscr{L}$ since $N_L = 2$.

The discriminants of these Lagrangian spheres are gathered in
Table~\ref{tb:classes-intro}, the detailed computations being
postponed to~\S\ref{s:examples}. The column under $\lambda_L$ will be
explained in~\S\ref{sb:eigneval}.

\begin{table}[h]
   \begin{center}
      \begin{tabular}{l | l | r | r}
         & $[L]$ & $\Delta_L$ & $\lambda_L$ \\
         \hline
         $M_2$ & $\pm(E_1 - E_2)$ & 5 & -1 \\
         \hline
         $M_3$ & $\pm(E_i - E_j)$ & 4 & -2 \\
         & $\pm(H - E_1 - E_2 - E_3)$ & -3 & -3 \\
         \hline
         $M_4$ & $\pm(E_i - E_j)$ & 1 & -3 \\
         & $\pm(H - E_i - E_j - E_l)$ & 1 & -3 \\
         \hline
         $M_5$ & $\pm(E_i - E_j)$ & 0 & -4 \\
         & $\pm(H - E_i - E_j - E_l)$ & 0 & -4 \\
         \hline
         $M_6$ & $\pm(E_i - E_j)$ & 0 & -6 \\
         & $\pm(H - E_i - E_j - E_l)$ & 0 & -6 \\
         & $\pm(2H - E_1 - \ldots - E_6)$ & 0 & -6
      \end{tabular}
      \vspace{4mm}
      \caption{Classes representing Lagrangian spheres and their
        discriminants.}
      \label{tb:classes-intro}
   \end{center}
\end{table}

The Lagrangian spheres in the three homology classes $E_i - E_j$,
$i<j$, of $M_3$ all have the same discriminant. This can also be seen
by noting that one can choose three Lagrangian spheres $L_1, L_2,
L_3$, one in each of these homology classes so that every pair of them
intersects transversely at exactly one point. The equality of their
discriminants as well (as the fact that they are perfect squares)
follows then by Corollary~\ref{c:del_1=del_2}. We elaborate more on
these examples in~\S\ref{s:examples}.

\subsubsection{Lagrangian spheres in hypersurfaces of
  ${\mathbb{C}}P^{n+1}$} \label{sbsb:exp-intro-hypsurf} Let $M^{2n}
\subset \mathbb{C}P^{n+1}$ be a hypersurface of degree $d \leq n+1$
endowed with the induced symplectic form. By the assumption on $d$,
$M$ is monotone (in fact Fano) and the minimal Chern number is $C_M =
n+2-d$. Note that when $d \geq 2$, $M$ contains Lagrangian spheres.
Assume further that $n\geq 3$, and $d \geq 3$.  Let $L \subset M$ be a
Lagrangian sphere, hence $[L]$ belongs to the primitive homology of
$M$ (see~\cite{Gr-Ha:alg-geom, Voi:hodge-book-I}). Using the
description of the quantum homology of $M$
from~\cite{Co-Ji:QH-hpersurf, Gi:equivariant} we obtain $[L]^{*3}=0$.

Whenever $n$ is a multiple of $2C_M = 2(n+2-d)$ the Lagrangian spheres
$L \subset M$ satisfy Assumption~$\mathscr{L}$, hence the discriminant
is defined and we obtain $\Delta_L = 0$.

Consider now the case $d=2$, i.e. $M$ is the quadric of complex
dimension $n$, and let $S \subset M$ be a Lagrangian sphere. We have
$C_M = n$, so case~\eqref{i:div} of Theorem~\ref{t:cubic-eq-sphere}
applies. If $n=$~odd, then $H_n(M)=0$, hence $[S]=0$. If $n=$~even,

then from the quantum product in the quadric we obtain:
\[ [S]^{*3} = (-1)^{\frac{n(n-1)}{2}+1}4 [S] q^n.
\]

More details on all the above calculations are given
in~\S\ref{s:examples}.

\subsection*{Acknowledgments}
We would like to thank Jean-Yves Welschinger for a discussion
convincing us that all Lagrangian tori in symplectic $4$-manifolds
with $b_2^+=1$ are null-homologous.


TITLE: $\sum\limits_{k=0}^{19} \sqrt{1+u_k^2} \rightarrow \min$
QUESTION [2 upvotes]: Solve $\sum\limits_{k=0}^{19} \sqrt{1+u_k^2} \rightarrow \min$,
  such that $x_0 = 0, x_{20} = 5$ and $x_{k+1} - x_k = u_k$.

I think I know how to solve problems like these recursively, but I don't know how I should attack this specific problem as it involves $20$ different $u_k$'s that need to be calculated (I think there must be a way to solve for general $u_k$ instead of recursively calculating each $u_k$). Could anyone please help?

REPLY [2 votes]: Here is another way to solve this problem.
First, we make the observation that
$$\frac{d^2}{dx^2} \sqrt{1+x^2} = \frac{1}{\sqrt{1+x^2}^3} > 0$$
This implies the function $\sqrt{1+x^2}$ is a strictly convex function for $x$ over $\mathbb{R}$. Second, we have
$$\sum_{k=0}^{19} u_k = \sum_{k=0}^{19}(x_{k+1} - x_{k}) = x_{20} - x_0 = 5$$
Using Jensen's inequality, we obtain:
$$\sum_{k=0}^{19}\sqrt{1+u_k^2} \ge 20 \sqrt{1+\left(\frac{1}{20}\sum_{k=0}^{19}u_k\right)^2}
= 20 \sqrt{1 + \frac{1}{4^2}} = 5\sqrt{17}
$$
It is clear above equality can be achieved when all $u_k$ is the same, i.e. equal to $\frac{5}{20} = \frac14$. This means the desired minimum is $5\sqrt{17}$.


TITLE: the triangle cosine relation in a complex plane
QUESTION [0 upvotes]: I have a triangle $ABC$ in a complex plane. The arrangement of vertices is in a counterclockwise direction. The coordinates of $A$,$B$,$C$ are $z_A$,$z_B$,$z_C$ respectively.
It is given that length of side $AB = c, AC = b$ and $\angle BAC = \alpha$. I need to find the other sides and angles of the triangle. How do i do this with complex numbers?
I know with trigonometry using the sine and cosine rules, all the length and angles can be derived. but how to get it using complex numbers?

REPLY [0 votes]: Here is the connection with the law of cosines. You can see which quantities correspond to which.
You have $z_B-z_A=ce^{i\alpha_1}$ and $z_C-z_A=be^{i\alpha_2}$, hence $z_A-z_C=be^{i(\alpha_2+\pi)}$. Clearly $\alpha_2-\alpha_1=\alpha$. Then
$z_B-z_C=(z_B-z_A)+(z_A-z_C)$ and
$$
a^2=|z_B-z_C|^2=(z_B-z_C)\overline{(z_B-z_C)}=(z_B-z_A)\overline{(z_B-z_A)}+(z_A-z_C)\overline{(z_A-z_C)}+2Re[(z_B-z_A)\overline{(z_A-z_C)}]=
$$
$$
=c^2+b^2+2bcRe(e^{i(\alpha_1-\alpha_2-\pi)})=c^2+b^2-2bc\cos\alpha
$$


TITLE: Uniqueness of determinant
QUESTION [14 upvotes]: In Artin Algebra 2nd edition page 22, the author proved the uniqueness of determinant by saying that any matrix $A$ can be written in reduced row-echelon form $A'$: $A'=E_1\cdots E_kA$ where $E_i$ are the elementary matrix. Then $A'$ is either $I$ or has a zero row. If $A'=I$, then $\delta(A')=1$. Otherwise, $\delta(A')=0$. In both cases, $\delta(A')$ is determined, and hence by
$$\delta(A')=\delta(E_1)\cdots\delta(E_k)\delta(A)$$
$\delta(A)$ is determined uniquely.
However, as he himself pointed out immediately in the following paragraph, the sequence $E_1\cdots E_k$ is not unique. Then why is $\delta(A)$ uniquely determined?
Edit:
The author defined determinant as a function $\delta(A)=d\in \mathbb{R}$ satisfying the following 3 conditions:
(i) $\delta(I)=1$
(ii) $\delta$ is linear in the rows of the matrix $A$
(iii) If two adjacent rows of $A$ are equal, then $\delta(A)=0$
He then proved that the above conditions imply some properties that all of us know, e.g.,
(a) Interchanging two rows reverses the sign
(b) If $A$ has a zero row, then $\delta(A)=0$
(c) Multiplying one row by a number and adding it to another row doesn't change the determinant
(d) $\delta(E)=\pm1$ or $c$
(e) $\delta(AB)=\delta(A)\delta(B)$
Then he proved that the function $\delta$ so defined is unique, as shown in the beginning of my post, which I don't understand

REPLY [2 votes]: The proof mentioned in the first paragraph of the question is not the proof for uniqueness of the Determinant Function. It says: The determinant of a matrix A, det (A), can be determined from determinant of it's row reduced form det (A'). It just says it can be determined. As you mentioned, the Author also clarifies that since the product of elementary matrices can be written in many ways, uniqueness can't be proved in this way. So, the uniqueness proof is yet incomplete.
When the Author starts off the Determinants topic, he mentions:
"The determinants of an nxn matrix is a functions of it's $n^2$ entries. There is one such function for each positive integer n. Unfortunately, there are many formulas for these determinants and all of them are complicated when n is large. Not only are the formulas complicated, but it may not be easy to show that two of them define the same function.
We use the following strategy: We choose one of the formulas, and take it as our definition of the determinant. In that way we are talking about a particular function. We show that our chosen function is the only one having certain special properties. Then, to show that other formula defines the same determinant function, one needs only to check those properties for the other function. This is often not too difficult."
Using the above statements, to prove the uniqueness, the author goes ahead to prove that the chosen standard determinant function (which is the expansion of minors on the first column) satisfies the properties of a Determinant function.
The way this proof is done: Using induction on the size of the matrices. We know that the properties are true for 1x1 matrices. Assuming that the properties are true for determinant of (n-1)x(n-1) matrices, we prove for nxn matrix. This completes the uniqueness proof.


TITLE: Is the space of continuous function with given order of decrease closed?
QUESTION [2 upvotes]: For example, denote $O^1$ the space of continuous function with property $\lim_{x\to\infty}{|x|f(x)}=0$ or $f(x)=o\left(|x|^{-1}\right)$ as $x\to\infty$. It's obviously an intermediate vector space between $C_c$ and $C_0$. Is it closed?
Assume knowledge of completeness of $C_0$, then for a convergent sequence $f_n\to f$, we know $f\in C_0$. Now we prove $f\in O^1$. $\forall\varepsilon,\exists N_1,\text{s.t. }d_{\sup}{(f,f_{N_1})}<\varepsilon /2,\exists N_2,\text{s.t. } |xf_{N_1}(x)|<\varepsilon /2\text{ if }|x|>N_2,\text{ then }...$ Ah, I see the argument break down here.
$O^1$ can't be closed since if it's closed, it will contradict the fact that $C_0=\overline{C_c}$.
My question is: is there any example of a sequence of continuous functions with given order of decrease uniformly convergent to a limit function with less order of decrease?
I have an additional question: Is space $O=\cap_{n=1}^{\infty}{O^n}$ closed? Any proof or example?
Third question: Is space $\cup_{n=1}^{\infty}{O^{1/n}}=C_0$?
PS: $C_c$ means continuous function with compact support, $C_0$ means continuous function vanishing at infinity. $O^n$ is the space of continuous functions with property $\lim_{x\to\infty}{|x|^nf(x)}=0$

REPLY [2 votes]: We can show that $O$ is dense in $C_0$ for the supremum norm. Let $\chi_k$ a continuous function, $\chi_k(x)=1$ if $-k\leq x\leq k$, $\chi_k(x)=0$ if $|x|\geq k+1$ and $0\leq \chi\leq 1$. If $f\in C_0$, we have $f\chi_k\in O$. Now we check uniform convergence:
\begin{align}
\sup_{x\in\Bbb R}|f(x)-f(x)\chi_k(x)|&\leq\sup_{|x|\geq k+1}|f(x)|+\sup_{k\leq |x|\leq k+1}f(x)|(1-\chi_k(x))\\
&\leq \sup_{|x|\geq k}|f(x)|.
\end{align}
For a fixed $\varepsilon>0$, fix $k$ such that $|f(x)|\leq \varepsilon$ if $|x|\geq k$ to get the result.
In particular, this proves that $O^1$ is dense in $C^0$, and it's strict since $x\mapsto\frac 1{1+\sqrt{|x|}}$ is in $C_0$ but not in $O^1$.
Let $V:=\bigcup_{n\geq 1}O^{1/n}$. It's not equal to $C_0$ since the map
$$f(x):=\frac 1{1+(\log x)^2}$$
is in $C_0$ but not in $O^{1/n}$ for any $n$.


text:
\begin{document}
\title{Lower Bounds for Boxicity}

\author{Abhijin Adiga\inst{1}, L. Sunil Chandran\inst{1}, and Naveen
Sivadasan\inst{2}}
\institute{Department of Computer Science and Automation, Indian Institute
of Science, Bangalore--560012, India. \\email: sunil@csa.iisc.ernet.in
\and
Advanced Technology Centre, TCS, Deccan Park, Madhapur, Hyderabad-–500 081,
India. email: s.naveen@atc.tcs.com}
\date{}
\maketitle
\begin{abstract}
An axis-parallel $b$-dimensional box is a Cartesian product $R_1\times
R_2\times\cdots\times R_b$ where $R_i$ is a closed interval of the
form $[a_i,b_i]$ on the real line. For a graph $G$, its \emph{boxicity}
$\boxi(G)$ is the minimum dimension $b$, such that $G$ is representable
as the intersection graph of boxes in $b$-dimensional space.  Although
boxicity was introduced in 1969 and studied extensively, there are no
significant results on lower bounds for boxicity. In this paper, we
develop two general methods for deriving lower bounds. Applying these
methods we give several results, some of which are listed below:
\begin{enumerate}
\item The boxicity of a graph on $n$ vertices with no universal vertices
and minimum degree $\delta$ is at least $n/2(n-\delta-1)$.
\item Consider the $\mathcal{G}(n,p)$ model of random graphs. Let $p$ be
such that $c_1/n\le p\le1-c_2\frac{\log n}{n^2}$, where $c_1$ and $c_2$
are predetermined constants. Then, for $G\in\mathcal{G}(n,p)$, almost
surely $\boxi(G)=\Omega(np(1-p))$. On setting $p=1/2$ we immediately infer
that almost all graphs have boxicity $\Omega(n)$. Another consequence of
this result is as follows: Let $m$ be an integer such that $c_1n \le m \le c_3 n^2$
($c_3$ is a suitable constant). Then, there exists a constant $c_4$ such that
almost all graphs on $n$ vertices and exactly $m$ edges have boxicity at
least $c_4m/n$.
\item Let $G$ be a connected $k$-regular graph on $n$ vertices. Let
$\lambda$ be the second largest eigenvalue in absolute value of the
adjacency matrix of $G$. Then, the boxicity of $G$ is at least
\(
\left(\frac{k^2/\lambda^2}{\log\left(1+k^2/\lambda^2\right)}\right)\left(\frac{n-k-1}{2n}\right).
\)
\item The boxicity of random $k$-regular graphs on $n$ vertices (where $k$ is
fixed) is $\Omega(k/\log k)$.
\item Consider all balanced bipartite graphs with $2n$ vertices. Let $m$
be an integer such that $c_1'n\log n\le m\le n^2-c_2'n$, where $c_1'$
and $c_2'$ are predetermined constants. There exists a positive constant
$c_3'$ such that almost all balanced bipartite graphs with exactly $m$
edges have boxicity at least $c_3'm/(n\log n)$. We can also show that
almost all balanced bipartite graphs have boxicity $\Omega(n/\log n)$.
\end{enumerate}
\paragraph{Key words:} Boxicity, Cubicity, Eigenvalue, Vertex
Isoperimetric Problem, Minimum interval supergraph, Random graphs.
\end{abstract}
\section{Introduction}
Let $G(V,E)$ be a simple undirected graph with vertex set $V$ and
edge set $E$. Let $\mathcal{F} = {S_x\subseteq U : x\in V}$ be a family of
subsets of a universe $U$, where $V$ is an
index set. The intersection graph $\Omega(\mathcal{F})$ of $F$ has $V$ as
vertex set, and two distinct vertices $x$ and $y$ are adjacent if and only
if $S_x\cap S_y\ne\emptyset$.
An axis-parallel $b$-dimensional box is a Cartesian
product $R_1\times R_2\times\cdots\times R_b$ where $R_i$ is a closed
interval of the form $[a_i,b_i]$ on the real line. For a graph $G$,
its \emph{boxicity} $\boxi(G)$ is the minimum dimension $b$, such
that $G$ is representable as the intersection graph of boxes in
$b$-dimensional space.  Roberts \cite{recentProgressesInCombRoberts}
introduced the concept of boxicity. Its applications include niche overlap
(competition) in ecology and problems of fleet maintenance in operations
research. Cozzens \cite{phdThesisCozzens} showed that computing the
boxicity of a graph is NP-hard. This was later strengthened by Yannakakis
\cite{complexityPartialOrderDimnYannakakis} and finally, by Kratochvil
\cite{specialPlanarSatisfiabilityProbNPKratochvil}, who showed that
deciding whether boxicity of a graph is at most 2 itself is NP-complete.

The class of graphs with boxicity at most 1 is exactly the popular class
of \emph{interval graphs}. A graph $G(V,E)$ is an interval graph if
there exists a mapping, say $f$, from $V$ to intervals on the real line
such that two vertices in $G$ are adjacent if and only if the intervals
to which they are mapped overlap. $f$ is called an \emph{interval
representation} of $G$.
Given a graph $G(V,E)$, let $\igr=\{I_i(V,E_i),1\le i\le k\}$ be a set of
$k$ interval graphs such that $E=E_1\cap E_2\cap\cdots\cap E_k$. Then, we
say that $\mathcal{I}$ is an \emph{interval graph representation} of $G$.
The concept of boxicity can be equivalently formulated using the interval
graph representation as follows:
\begin{theorem}
\textnormal{\textbf{(Roberts \cite{recentProgressesInCombRoberts})}}
The minimum $k$ such that there exists an interval graph representation
of $G$ using $k$ interval graphs  $\igr=\{I_i(V,E_i),1\le i\le k\}$
is the same as $\boxi(G)$.
\end{theorem}

\subsection{Some Known Bounds on Boxicity}
There have been several attempts to establish upper bounds on
boxicity, especially for graphs with special structures. Roberts,
in his seminal work \cite{recentProgressesInCombRoberts}, proved that
the boxicity of a complete $k$-partite graph is $k$, thereby showing
that boxicity of a graph with $n$ vertices cannot exceed $\floor{n/2}$.
Chandran and Sivadasan \cite{boxicityTreewidthSunilNaveen} showed that
$\boxi(G)\le\mbox{tw}(G)+2$, where, $\mbox{tw}(G)$ is the treewidth of
$G$. Chandran et al \cite{boxicityMaxDegreeSunilNaveenFrancis} proved
that $\boxi(G)\le\chi(G^2)$ where, $G^2$ is the supergraph of $G$ in
which two vertices are adjacent if and only if they are at a distance
of at most 2 in $G$, and $\chi(G^2)$ is the chromatic number of $G^2$. From
this result, they inferred that $\boxi(G)\le2\Delta^2$, where $\Delta$
is the maximum degree of $G$. Scheinerman \cite{phdThesisScheinerman} showed
that the boxicity of outer planar graphs is at most 2. Thomassen
\cite{intervalRepPlanarGraphsThomassen} proved that the boxicity of
planar graphs is at most 3. In \cite{computingBoxicityCozzensRoberts},
Cozzens and Roberts studied the boxicity of split graphs.

In contrast, the literature provides few results regarding lower
bounds on boxicity. Even ad hoc constructions that achieve high
boxicity are rare.  In \cite{recentProgressesInCombRoberts}, to prove
that a complete $k$-partite graph has boxicity at least $k$, Roberts
uses the pigeon-hole principle in conjunction with the fact that an
interval graph does not contain an induced $C_4$. As a consequence,
he shows that the boxicity of a $\ceil{n/2}$-partite graph is at least
$\floor{n/2}$. In \cite{forbiddenTrotter} Trotter has characterized
all graphs with boxicity $\floor{n/2}$. Similar arguments are used by
Cozzens and Roberts \cite{computingBoxicityCozzensRoberts} to show that
the boxicity of the complement of a cycle or a path of length $n$, is
at least $\ceil{n/3}$. Motivated by the concept of boxicity, McKee and
Scheinerman \cite{chordalityMcKeeScheinerman} study a parameter called
\emph{chordality} of a graph $G$, $\mbox{chord}(G)$ (a better name
would be chordal dimension). It is the minimum $k$ such that $G$ can be
expressed as the intersection of $k$ chordal graphs. Since, every interval
graph is chordal, it follows that $\boxi(G)\ge\mbox{chord}(G)$. To
obtain lower bounds for chordality, the authors use the property that
if a graph has chordality at most $k$, then $G$ contains a vertex whose
neighbours induce a subgraph of chordality at most $k-1$. Using this,
they have managed to show that the chordality and hence the boxicity
of a bipyramid graph is at least $3$. Unfortunately, it does not
look like it is adequate to give strong and general lower bounds. In
\cite{boxicityTreewidthSunilNaveen}, Chandran and Sivadasan provide a
specialized construction to show that for any integer $k\ge1$, there
are graphs with treewidth at most $t+\sqrt{t}$ whose boxicity is at
least $t-\sqrt{t}$.

It is interesting to note that coloring problems on low boxicity
graphs were considered as early as 1948 \cite{problem56Bielecki}.
Kostochka \cite{coloringIntersectionGraphsKostochka} provides an
extensive survey on colouring problems of intersection graphs. In
\cite{findingImaiAsano,optimalPackingFowlerPatersonTanimoto}, the
complexity of finding the maximum independent set in bounded boxicity
graphs is considered.
Researchers have also tried to generalize or extend the concept of boxicity
in various ways. The poset boxicity \cite{posetBoxicityTrotterWest}, the
rectangle number \cite{rectNumHypercubesChangeWest}, grid dimension
\cite{gridIntBoxicityBellantoniEtal}, circular dimension
\cite{circDimensionFeinberg,noteCircDimensionShearer}, and the boxicity of
digraphs \cite{intNumBoxDigraphs} are some examples.

\subsection{Our Results}
In this paper, we present two methods to obtain lower bounds on
boxicity. The underlying idea of both the methods is to make use of the
vertex isoperimetric properties of the given graph (sometimes
modified to suit our purpose). The first method allows us to derive strong
lower bounds, but has the drawback that it is not of much use when there
is a large independent set in the graph (consider for example, the case
of bipartite graphs). But the second method overcomes this difficulty and
is much more general, though the lower bounds derivable using it seem to be
relatively weaker for comparable cases. Most of the already known lower
bounds can be re-derived using these methods.  Applying these methods
we derive several new results, some of which are listed below:
\begin{enumerate}
\item The boxicity of a graph on $n$ vertices with no universal vertices and
minimum degree $\delta$ is at least $n/2(n-\delta-1)$ (Theorem
\ref{thm:universal}, Section \ref{sec:consMainThm}).
\begin{remark}
There are two
parameters, namely \emph{cubicity} and \emph{sphericity} which are closely
related to boxicity. There have been several instances in the literature when these
two parameters were compared with each other.  Cubicity (Sphericity)
of $G$ denoted as $\cub(G)$ ($\sph(G)$) is the minimum dimension $b$, such
that $G$ can be represented as the intersection graph of axis-parallel
unit cubes (unit spheres) in $b$-dimensional space. Since cubicity is
a stricter notion of boxicity, $\cub(G)\ge\boxi(G)$. Apparently, there
is no such relationship between cubicity (or boxicity) and sphericity.

Havel \cite{phdThesisHavel} showed that there
are graphs with sphericity 2 and arbitrarily high cubicity while Fishburn
\cite{onTheSphCubGraphsFishburn} constructed some graphs of cubicity at
most 3 with sphericity greater than their cubicity. Maehara et al
\cite{embeddingTreesMaeharaEtal} proved that the sphericity of the
complement of a tree is at most 3. Using our result mentioned above, we can
easily infer that if $G$ is the complement of a bounded degree tree, then
$\boxi(G)=\Omega(n)$. Thus we have a large number of graphs that have
arbitrarily higher value of boxicity (not just cubicity!) than their
sphericity. This is a much stronger result compared to that of Havel's, who
refers to the class of star graphs (Consider the five--pointed star
graph $K_{1,5}$: $\cub(K_{1,5})=3$ while $\sph(K_{1,5})=2$. But the
boxicity of any star graph is 1).
\end{remark}
\item Consider the $\mathcal{G}(n,p)$ model of random graphs. Let $p$ be
such that $c_1/n\le p\le1-c_2\frac{\log n}{n^2}$, where $c_1$ and $c_2$
are predetermined constants. Then, for $G\in\mathcal{G}(n,p)$, almost
surely $\boxi(G)=\Omega(np(1-p))$ (Theorem \ref{thm:randThm}, Section
\ref{sec:rand1}).

On setting $p=1/2$ we immediately infer that almost all graphs have
boxicity $\Omega(n)$. Another consequence of this result is as follows:
Let $m$ be an integer such that $c_1n \le m \le c_3 n^2$ ($c_3$ is
a suitable constant). Then, there exists a constant $c_4$ such that
almost all graphs on $n$ vertices and exactly $m$ edges have boxicity
at least $c_4m/n$.
\item Let $G$ be a connected $k$-regular graph on $n$ vertices. Let
$\lambda$ be the second largest eigenvalue in absolute value of the
adjacency matrix of $G$. Then, the boxicity of $G$ is at least
\(
\left(\frac{k^2/\lambda^2}{\log\left(1+k^2/\lambda^2\right)}\right)\left(\frac{n-k-1}{2n}\right)
\)
(Theorem \ref{thm:spec}, Section \ref{sec:spec}).

Bilu and Linial \cite{sphericityBiluLinial} have a similar result for
sphericity of regular graphs. They prove that an $\epsilon n$-regular
graph of order $n$, with bounded diameter has sphericity
$\Omega(n/(\lambda+1))$, where $0\le\epsilon\le\frac{1}{2}$ is a constant.
Note that if $G$ is an $\epsilon n$-regular graph, the lower bound for
boxicity that we get is almost the square of the Bilu-Linial bound for
sphericity.
\item The boxicity of random $k$-regular graphs on $n$ vertices (where $k$ is
fixed) is $\Omega(k/\log k)$ (Corollary \ref{cor:specAlmost}, Section
\ref{sec:spec}).

This lower bound should be compared with the known upper bound of $2k^2$
from \cite{boxicityMaxDegreeSunilNaveenFrancis}. Hence, we see that for
$k$-regular graphs the lower bound and upper bound become comparable. It
is conjectured in \cite{boxicityMaxDegreeSunilNaveenFrancis} that the
upper bound may come down to $\mathcal{O}(\Delta)$ and therefore for
$k$-regular graphs to $\mathcal{O}(k)$. It may be true that the correct
lower bound is indeed $\Omega(k)$ and not $\Omega(k/\log k)$.
\item Consider all balanced bipartite graphs with $2n$ vertices. Let $m$
be an integer such that $c_1'n\log n\le m\le n^2-c_2'n$, where $c_1'$
and $c_2'$ are predetermined constants. There exists a positive
constant $c_3'$ such that almost all balanced bipartite graphs
with $m$ edges have boxicity at least $c_3'm/(n\log n)$ (Corollary
\ref{cor:bipartiteThmEdges}, Section \ref{sec:consMainThm}). We can
also show that almost all balanced bipartite graphs have boxicity
$\Omega(n/\log n)$.
\end{enumerate}

\section{Preliminaries}\label{sec:prelims}
For a graph $G(V,E)$, $\numed{G}$ denotes the number of edges in $G$.
The complement of $G$ is denoted by $\comp{G}$. A balanced
($A,B$)-bipartite graphs is a bipartite graph with $V=A\uplus B$
and $|A|=|B|$. $\delta(G)$ and $\Delta(G)$ are the minimum degree and
maximum degree of $G$ respectively.

\subsection{Interval Graphs}\label{sec:intProp}
Suppose $I(V,E)$ is an interval graph and $f$ is an
interval representation of $I$. For a vertex $u$, let $l_f(u)$
and $r_f(u)$ denote the real numbers corresponding to the left end-point
and right end-point respectively of the interval $f(u)$. When there is
no ambiguity regarding the interval representation under consideration,
we shall discard the subscript $f$ and use the abbreviated forms $l(u)$
and $r(u)$ respectively. Further, we refer to $l(u)$ as the ``left
end-point" and $r(u)$ as the ``right end-point".

We can assume without loss of generality that for any interval graph $G$,
there is an interval representation such that all the interval end points
map to distinct points on the real line.

\paragraph{\textnormal{\textbf{Induced vertex numbering:}}} Given an
interval representation of $I$ with distinct end-points, we define the
induced vertex numbering $\eta(\cdot)$ as a numbering of the vertices in the
increasing order of their right end-points, i.e. for any two distinct
vertices $u$ and $v$, $\eta(u)<\eta(v)\Longleftrightarrow r(u)<r(v)$.

\begin{definition}
A \textbf{minimum interval supergraph} of a graph $G(V,E)$, is an interval
supergraph of $G$ with vertex set $V$ and with least number of edges
among all interval supergraphs of $G$.
\end{definition}

\subsection{Neighbourhoods}\label{sec:neighbours}
Given a subset of vertices, say $X$, we define several vertex
neighbourhoods of $X$.
\begin{enumerate}
\item{\textbf{Vertex-boundary}} $\vb(X,G) = \{u\in V-X|\exists v\in
X\mbox{~with~}uv\in E\}$. The term vertex-boundary is
borrowed from \cite{globalMethodsHarper}.
\item{\textbf{Strong vertex-boundary}} $\sn(X,G)=\left\{u\in V-X| uv\in E,
\forall v\in X\right\}$.
\item{\textbf{Vertex neighbourhood}} $N'(X,G) = \{u|\exists v\in
X\mbox{~with~}uv\in E\}$.
\item{\textbf{Closed vertex neighbourhood}} $N[X,G] = X \cup N(X,G)$.
\end{enumerate}
When $X$ is a singleton set, say $X=\{v\}$, we will use the notations
$\vb(v,G)$, $\sn(v,G)$, $N'(v,G)$ and $N[v,G]$ respectively.
When there is no ambiguity regarding the graph under consideration,
we discard the second argument and simply denote the neighbourhoods
as $\vb(X)$, $\sn(X)$, $N'(X)$ and $N[X]$ respectively.

\subsubsection{Probability Spaces of Random Graphs}
\begin{enumerate}
\item $\mathcal{G}(n,p)$: The probability space of graphs on $n$
vertices in which the edges are chosen independently with probability
$p$.
\item $\mathcal{G}(n,m)$: The probability space of graphs on $n$
vertices having $m$ edges, in which the graphs have the same probability.
\item $\mathcal{G}_R(n,k)$: The probability space of all simple $k$-regular
graphs on $n$ vertices with each graph having the same probability.
\item $\mathcal{G}_B(2n,p)$: The probability space of all balanced
bipartite graphs on $2n$ vertices in which the edges are chosen
independently with probability $p$.
\item $\mathcal{G}_B(2n,m)$: The probability space of all balanced
bipartite graphs on $2n$ vertices and $m$ edges, in which the graphs
have the same probability.
\end{enumerate}
If $X$ is a random variable, $E(X)$ denotes the expectation of $X$.
\subsubsection{Standard Asymptotic Notations:}
(From \cite{probabilisticMethodAlonSpencerErdos}) For two functions
$f$ and $g$, we write $f=\mathcal{O}(g)$ if $f\le c_1g+c_2$ for all
possible values of the variables of the two functions, where $c_1,c_2$
are absolute constants. We write $f=\Omega(g)$ if $g=\mathcal{O}(f)$
and $f=\Theta(g)$ if $f=\mathcal{O}(g)$ and $f=\Omega(g)$. If the limit
of the ratio $f/g$ tends to $0$ as the variables of the functions tend
to infinity, we write $f=o(g)$. We use $f=\omega(g)$ if $g=o(f)$.

\section{The First Method: Based on Minimum Interval Supergraph}
\label{sec:firstMethod}
Given any positive integer $k$, the \emph{vertex-isoperimetric problem}
\cite{globalMethodsHarper} is to minimize $|\vb(X,G)|$ over all
$X\subseteq V$ such that $|X|=k$. Let
\begin{equation}\label{eqn:bvi}
b_v(k,G)=\min_{\stackrel{X\subseteq V}{|X|=k}}|\vb(X,G)|.
\end{equation}
A brief introduction to isoperimetric problems can be found in
\cite{combinatoricsBollabas}. Harper \cite{globalMethodsHarper} gives
a detailed treatment of the vertex-isoperimetric problem.

Let $c_v(k,G)=\max_{\stackrel{X\subseteq V}{|X|=k}}|\sn(X,G)|$.
It is easy to see that $\sn(X,\comp{G})=V-X-\vb(X,G)$. From this we infer
the following:
\begin{eqnarray}\label{eqn:cvk}
c_v(k,\comp{G})&=&\max_{\stackrel{X\subseteq
V}{|X|=k}}|V-X-\vb(X,G)|=n-k-\min_{\stackrel{X\subseteq
V}{|X|=k}}|\vb(X,G)|=n-k-b_v(k,G).
\end{eqnarray}
\begin{observation}\label{obs:cvObs1}
Let $i$ and $j$ be two positive integers such that $i>j$. Then,
$c_v(i,G)\le c_v(j,G)$.
\end{observation}
\begin{proof}
If $c_v(i,G)=k$, it implies that there exists a pair of sets
$X,Y\subseteq V$ with $|X|=i$ and $|Y|=k$ such that $Y$ is the strong
vertex boundary of $X$. For any set $A\subseteq X$ such that $|A|=j$,
$Y\subseteq\sn(A,G)$. Therefore, $c_v(j,G)\ge k$.
\end{proof}
\begin{observation}\label{obs:cvObs2}
Suppose $i$ and $j$ are non-negative integers. If $c_v(i,G)=j$, then,
for any integer $k>j$, $c_v(k,G)<i$.
\end{observation}
\begin{proof}
If $c_v(k,G)\ge i$, then, it implies that there exists a pair of sets
$X,Y\subseteq V$ with $|X|=k$ and $|Y|\ge i$, such that $Y=\sn(X,G)$. Then
clearly $X\subseteq \sn(Y,G)$. It follows that $c_v(i,G)\ge c_v(|Y|,G)\ge
k>j$, contradicting the assumption that $c_v(i,G)=j$.
\end{proof}

\subsection{Lower Bound for Boxicity}
\begin{lemma}\label{lem:iminLem}
Let $G(V,E)$ be any non-complete graph. Let $\imin$ be a minimum interval
supergraph of $G$. Then,
\begin{equation}\label{eqn:gi}
\boxi(G)\ge \numed{\comp{G}}/\numed{\comp{\imin}}.
\end{equation}
\end{lemma}
\begin{proof}
Let $\igr=\{I_1,I_2,\ldots,I_k\}$ be an interval graph representation
of $G$. Since each graph $I\in \igr$ is an interval supergraph of $G$,
$\numed{I}\ge \numed{\imin}$, $\forall I\in \igr$. Hence, in any $I\in
\igr$, at most $\numed{\comp{\imin}}$ edges can be absent. In $G$,
$\numed{\comp{G}}$ edges are absent. Since, an edge absent in $G$
should be absent in at least one interval graph in $\igr$, there should
be at least $\numed{\comp{G}}/\numed{\comp{\imin}}$ interval graphs in
$\igr$. Hence proved.\qed
\end{proof}

\begin{theorem}\label{thm:cvithm}
Let $G$ be a non-complete graph with $n$ vertices. Then,
\begin{equation}\label{eqn:cvi}
\boxi(G)\ge \frac{\numed{\comp{G}}}{\ds\sum_{i=1}^{n-1}c_v(i,\comp{G})}.
\end{equation}
\end{theorem}
\begin{proof}
In view of Lemma \ref{lem:iminLem}, it is enough to show that
$\numed{\comp{\imin}}\le\sum_{i=1}^{n-1}c_v(i,\comp{G})$. Consider
an interval representation with distinct end-points for $\imin$
and, let $\eta$ be the induced vertex numbering (see Section
\ref{sec:intProp} for definition). Given an integer $k$, $1\le k\le n$, let
\[
S_k(\eta)=\eta^{-1}\left(\{1,2,\ldots,k\}\right)=\left\{v\in V|\eta(v)\le k\right\},
\]
be the set of the first $k$ vertices numbered by $\eta$. We observe
that, in any interval graph, for any three vertices $u$, $v$ and $w$
such that $\eta(u)<\eta(v)<\eta(w)$, if $w$ is adjacent to $u$, then
$w$ is also adjacent to $v$ and therefore $N\left(S_k(\eta)\right)=\{u\in
N\left(\eta^{-1}(k)\right)| \eta(u)>k\}$. Using this fact, we have
\[
\sum_{k=1}^{n-1}|\vb\left(S_k(\eta)\right)|=\sum_{u\in V}|\left\{v|
uv\in E\mbox{ and }\eta(v)>\eta(u)\right\}|=\numed{\imin}.
\]
By definition, $|\vb\left(S_k(\eta),G\right)|\ge b_v(k,G)$ and therefore,
$\numed{\imin}\ge\sum_{k=1}^{n-1}b_v(k,G)$. Now, the upper bound on
$\numed{\comp{\imin}}$ follows by applying equation (\ref{eqn:cvk}):
\begin{eqnarray*}
\numed{\comp{\imin}}&&={n\choose 2}-\numed{\imin}\\
&&\le{n\choose 2}-\sum_{k=1}^{n-1}b_v(k,G)=\sum_{k=1}^{n-1}n-k-b_v(k,G)
=\sum_{k=1}^{n-1}c_v(k,\comp{G}).
\end{eqnarray*}
\qed
\end{proof}
\subsection{Some Immediate Applications of Theorem \ref{thm:cvithm}}
\label{sec:immAppMethod1}
\begin{theorem}\label{thm:nk2}
Let $G(V,E)$ be a $(n-k-1)$-regular graph for some positive integer $k$.
Then, $\boxi(G)\ge\frac{n}{2k}$.
\end{theorem}
\begin{proof}
Since $\comp{G}$ is a $k$-regular graph, $\numed{\comp{G}}=nk/2$
and $c_v(1,\comp{G})=k$.  For $2\le i\le k$, $c_v(i,\comp{G})\le k$
(by Observation \ref{obs:cvObs1}) and for $i>k$, $c_v(i,\comp{G})=0$ (by
Observation \ref{obs:cvObs2}). Hence, $\sum_{i=1}^{n-1}c_v(i,\comp{G})\le
k^2$. Applying Theorem \ref{thm:cvithm}, the result follows.\qed
\end{proof}
\paragraph{\textnormal{\textbf{Tightness of Theorem \ref{thm:nk2}:}}}
Consider the following co-bipartite graph $G(V,E)$: $V=A\uplus B$
and let $n$, $k$ and $l$ be integers such that, $|A|=|B|=kl=n/2$,
Further, let $A=A_1\uplus A_2\uplus\cdots\uplus A_l$ and $B=B_1\uplus
B_2\uplus\cdots\uplus B_l$, where, $|A_i|=|B_i|=k$. For any two vertices,
$u$ and $v$, let $uv\notin E\Longleftrightarrow u\in A_i \mbox{ and }
v\in B_i$, $1\le i\le l$. Clearly, $G$ is an $(n-k-1)$-regular graph and
therefore by Theorem \ref{thm:nk2}, $\boxi(G)\ge n/2k=l$. Now, we present
a set of $l$ interval graphs $\mathcal{I}=\{I_i| 1\le i\le l\}$ whose edge
intersection gives $G$. The interval representation $f_i$ for each $I_i$
is as follows: $f_i(u)=[0,1]$ if $u\in A_i$, $f_i(u)=[2,3]$ if $u\in
B_i$, and $f_i(u)=[1,2]$ otherwise. Therefore, $\boxi(G)=l=n/2k$. In fact,
we note that each $I_i$ is a unit-interval graph by construction.
Therefore, this graph acts as a tight example even if we were to replace
$\boxi(G)$ with $\cub(G)$ in Theorem \ref{thm:nk2}.

\begin{theorem} \label{thm:nkExamples}
Let $k\ge 1$ be an integer.
\begin{enumerate}
\item Let $G$ be a ($n-k-1$)-regular co-planar graph. Then,
$\boxi(G)\ge\frac{n}{8}$.
\item Let $G$ be the complement of a $k$-regular $C_4$-free graph. Then,
$\boxi(G)\ge\frac{n}{4}$.
\item $\boxi(\comp{C_n})\ge\frac{n}{3}$.
\end{enumerate}
\end{theorem}
\begin{proof}
(1) Since $\comp{G}$ is a planar graph, it does not contain $K_{3,3}$
as a subgraph. Hence, $c_v(i,\comp{G})\le 2$ for $3\le i\le k$. From
Observation \ref{obs:cvObs2}, $c_v(i,\comp{G})=0$ for $i>k$. The result
follows by applying Theorem \ref{thm:cvithm} with $c_v(i,\comp{G})\le k$,
for $i=1,2$.\\
(2) Since $\comp{G}$ is $C_4$ or $K_{2,2}$ free, the result follows in the
same way as for (1).\\
(3) We have $\numed{C_n}=n$, $c_v(1,C_n)=2$, $c_v(2,C_n)=1$ and by
Observation \ref{obs:cvObs2}, $c_v(i,C_n)=0$ for $i>2$. Applying
Theorem \ref{thm:cvithm} the result follows. We recall that Cozzens
and Roberts \cite{computingBoxicityCozzensRoberts} showed that
$\boxi(\comp{C_n})=\ceil{n/3}$ by different methods. \qed
\end{proof}
\begin{remark}
Theorems \ref{thm:nk2} and \ref{thm:nkExamples} are only indicative. We can
bound the boxicity of various other graph classes using this
method. If $G$ is not regular we can give a lower bound in terms of the
ratio $\delta(\comp{G})/\Delta(\comp{G})$, i.e. $\boxi(G)\ge
\frac{n\delta(\comp{G})}{2\Delta(\comp{G})^2}$. Later, using the second method
we will show an better lower bound of $\frac{n}{2\Delta(\comp{G})}$.
\end{remark}

\subsection{Lower Bound for Random Graphs: $\mathcal{G}(n,p)$ and
$\mathcal{G}(n,m)$}\label{sec:rand1}
For the definitions of probability spaces such as $\mathcal{G}(n,p)$
and $\mathcal{G}(n,m)$ and asymptotic notations such as $\mathcal{O}$,
$\omega$, etc, we refer to Section \ref{sec:prelims}.
\begin{lemma} \label{lem:nci} Let $n$ and $i$ be positive integers. For
$n>1$ and $0<i\le n/e^2$, ${n \choose i}\le \left(\frac{n}{i}\right)^{2i}$.
\end{lemma}
\begin{proof}
We prove by induction on $i$. For $i=1$, the inequality is trivially
satisfied. Let $i=k+1$ and assume that the claim holds for $i\le k$.
\begin{eqnarray*}
{n\choose k+1}&&={n\choose k}\frac{n-k}{k+1}\le\left(\frac{n}{k}\right)^{2k}
\frac{n}{k+1}=\left(\frac{n}{k+1}\right)^{2k+1}\left(\frac{k+1}{k}\right)^{2k}
\le\left(\frac{n}{k+1}\right)^{2k+1}e^2.
\end{eqnarray*}
Since $k+1\le n/e^2$, it follows that $\left(\frac{n}{k+1}\right)^{2k+1}e^2\le
\left(\frac{n}{k+1}\right)^{2(k+1)}$. Hence proved.
\qed
\end{proof}

\begin{theorem}\label{thm:randThm}
Let $G\in \mathcal{G}(n,p)$ and $p$ be such that $c_1/n\le
p\le1-c_2\frac{\log n}{n^2}$, where $c_1=e^{e^e}$ and $c_2$
is some suitable positive constant. Then, almost surely,
$\boxi(G)=\Omega(np(1-p))$.
\end{theorem}
\begin{proof}
The outline of the proof is as follows. We will first
show that for almost all graphs $G\in\mathcal{G}(n,p)$,
$\numed{\comp{G}}=\Omega\left(n^2(1-p)\right)$. Then, we show that
$\sum_{i=1}^{n-1}c_v(i,\comp{G})=\mathcal{O}(n/p)$ for almost all
graphs. The result follows by the application of Theorem
\ref{lem:iminLem}.

Let $f=np$. The probability that a particular edge is present
in $\comp{G}$ is $q=1-f/n\le e^{-f/n}$. The expected number
of edges in $\comp{G}$ is ${n \choose 2}q$. Consider the event
$\mathcal{E}_1:\numed{\comp{G}}<(1-\epsilon){n \choose 2}q$. For some
constant $\epsilon\in(0,1)$, we set $c_2=10/\epsilon^2$. Using Chernoff's
bound on Poisson trials, we have
\begin{equation}\label{eqn:numFinal}
Pr\left(\mathcal{E}_1\right)\le
\exp\left(-\frac{\epsilon^2}{2}{n \choose 2}q\right)\le \frac{1}{n^2}.
\end{equation}
Next, we look at the following event:
\(
\mathcal{E}_2: \sum_{i=1}^{n-1}c_v(i,\comp{G})=\Omega(n^2/f).
\)
Our aim is to show that $Pr(\mathcal{E}_2)\rightarrow0$ as
$n\rightarrow\infty$. To this end, we divide the summation in to five
parts.

\paragraph{\textbf{Range \textrm{1} $\left(1\le i\le\frac{2n}{5f}\log
f\right)$:}} Let $A\subseteq V$, $|A|=i$. Consider the random
variable $X=|\sn(A,\comp{G})|$ and the event $\mathcal{E}_A:
X > \epsilon(n-i)e^{-fi/n}$ for some constant $\epsilon>6$. Note
that $q=\left(1-\frac{f}{n}\right)\le e^{-fi/n}$. Observing that
$\mathcal{E}_A$ is a monotone increasing event\footnote{\label{mon}A property
$Q$ is a monotone increasing property if whenever $G$ satisfies $Q$,
any supergraph of $G$ on the same set of vertices also satisfies
$Q$. We make use of the property that, if $0\le p_1<p_2\le
1$, then, $Pr(G\in\mathcal{G}(n,p_1),G\mbox{ satisfies } Q)\le
Pr(G\in\mathcal{G}(n,p_2),G\mbox{ satisfies } Q)$ (see \cite[Theorem 1,
Chapter 2]{bollobasRandomGraphs}).}, for ease of computation we will
assume that $\comp{G}\in\mathcal{G}\left(n,e^{-fi/n}\right)$ instead of
$\mathcal{G}(n,q)$. Since $E(X)=(n-i)e^{-fi/n}$ with respect to
$\mathcal{G}(n,e^{-fi/n})$, we bound $Pr(\mathcal{E}_A)$ using Chernoff's
bound on Poisson trials:
\(
Pr(\mathcal{E}_A)\le2^{-\epsilon
E(X)}\le\exp\left(-\frac{\epsilon}{2}(n-i)e^{-fi/n}\right).
\)
Since $c_v(i,\comp{G})=\ds\max_{\stackrel{A\subseteq
V}{|A|=i}}|\sn(A,\comp{G})|$, using union bound and subsequent
application of Lemma \ref{lem:nci} we get,
\begin{equation}\label{eqn:xi}
Pr\left(c_v(i,\comp{G})\ge\epsilon(n-i)e^{-fi/n}\right)\le{n \choose
i}\exp\left(-\frac{\epsilon}{2}(n-i)e^{-fi/n}\right)\le\exp\left(2i\log(n/i)-\frac{\epsilon}{2}(n-i)e^{-fi/n}\right).
\end{equation}
Then, we note that for any two integers $a$ and $b$, such that $0<a\le
b$,
\begin{eqnarray}\label{eqn:cvsum}
\sum_{i=a}^b\epsilon(n-i)e^{-fi/n} \le \sum_{i=0}^\infty\epsilon ne^{-fi/n}
= \frac{\epsilon n}{1-e^{-f/n}}\le \frac{2\epsilon n^2}{f}.
\end{eqnarray}

The last expression is derived from the fact that $e^{-f/n}\le (1-f/2n)$
when $f/n<1$.  Let $\mathcal{E}_{21}:\sum_{i=a}^bc_v(i,\comp{G})\ge
\frac{2\epsilon n^2}{f}$. We want to show that
$Pr\left(\mathcal{E}_{21}\right)\rightarrow 0$ as $n\rightarrow\infty$
for $a=1$ and $b=\frac{2n}{5f}\log f$ in (\ref{eqn:cvsum})\footnote{We assume that
$\frac{2n}{5f}\log f$ is an integer. If not, we can replace it with its
floor, without affecting the proof. The same argument holds for the rest
of the ranges.}. We recall that $f\ge c_1=e^{e^e}$. Hence, we have $a\le
b\le n/e^2$. In view of equation (\ref{eqn:cvsum}),
\begin{eqnarray*}
Pr\left(\mathcal{E}_{21}\right)&&\le
Pr\left(\bigvee_{i=a}^bc_v(i,\comp{G})\ge \epsilon(n-i)e^{-fi/n}\right)\\
&&\le\sum_{i=a}^bPr\left(c_v(i,\comp{G})\ge \epsilon(n-i)e^{-fi/n}\right)\\
\mbox{(by (\ref{eqn:xi}))}&&\le
\sum_{i=a}^b\exp\left(2i\log(n/i)-\frac{\epsilon}{2}(n-i)e^{-fi/n}\right)

=\sum_{i=a}^b\exp\left(-h(i)\right),
\end{eqnarray*}
where $h(i)=\frac{\epsilon}{2}(n-i)e^{-fi/n}-2i\log(n/i)$.
Clearly $h(1)=\Theta(n)$. It is easy to verify that the slope of the
function $h(i)$ is negative and thus is a monotonically decreasing
function of $i$ for the range $1\le i\le\frac{2n}{5f}\log f$. Therefore,
\[
\sum_{i=a}^b\exp\left(-h(i)\right)\le b\exp(-h(b))=\exp(-h(b)+\log b).
\]
Since $b=\frac{2n}{5f}\log f$,
\begin{eqnarray}
h(b)-\log
b&&=\frac{\epsilon}{2}\frac{n}{f^{2/5}} -
\frac{\epsilon}{5}\frac{n}{f^{7/5}}\log f -
\frac{4n}{5f}\log f\log\frac{5f}{2\log f}-\log\left(\frac{2n}{5f}\log
f\right)=\Theta\left(nf^{-2/5}\right),
\end{eqnarray}
for $\epsilon\ge6$. Since $f\ge e^{e^e}$,
\begin{equation}\label{eqn:e1}
Pr(\mathcal{E}_{21})\le\exp\left(-\Theta\left(nf^{-2/5}\right)\right)\le\frac{1}{n^2}.
\end{equation}

\paragraph{\textbf{Range \textrm{2} $\left(\frac{2n}{5f}\log f\le i\le
\frac{5n}{f}\log f\right)$:}} Let $\mathcal{E}_{22}:\sum_{i=\frac{2n}{5f}\log
f}^{\frac{5n}{f}\log f}c_v(i,\comp{G})>\frac{5n^2}{f}$. Suppose $x$
and $y$ are positive integers. The event that $c_v(x,\comp{G})\ge y$
is equivalent to the following event
\begin{eqnarray*}
\mathcal{E}_{x,y}: &&\exists A,B\subseteq V, |A|=x \mbox{
and }|B|=y, \mbox{ such that } A\cap B=\varnothing \mbox{ and }
B\subseteq\sn(A,\comp{G}) \mbox{ and }\\ &&\mbox{therefore, } \forall
u,v \mbox{ such that } u\in A, v\in B \Rightarrow uv\in E(\comp{G}).
\end{eqnarray*}
Using this fact along with the union bound, we have
\begin{equation}\label{eqn:count}
Pr(c_v(x,\comp{G})\ge y)\le {n\choose x}{n\choose y}q^{xy}\le{n\choose
x}{n\choose y}e^{-fxy/n}.
\end{equation}
Let $x=\frac{2n}{5f}\log f$ and $y=\frac{n}{\log f}$. Applying
the above equation and subsequently Lemma \ref{lem:nci},
\begin{eqnarray}\label{eqn:range2Int}
Pr\left(c_v\left(\frac{2n}{5f}\log f,\comp{G}\right)\ge\frac{n}{\log
f}\right)\le \exp\left(\frac{4n}{5f}\log f\log\left(\frac{5f}{2\log f}\right) +
\frac{2n}{\log f}\log(\log f) - \frac{2n}{5}\right).
\end{eqnarray}
By Observation \ref{obs:cvObs1}, it follows that if
$c_v\left(\frac{2n}{5f}\log f,\comp{G}\right)\le\frac{n}{\log f}$, then
\[
\sum_{i=\frac{2n}{5f}\log f}^{\frac{5n}{f}\log
f}c_v(i,\comp{G})\le \frac{5n}{f}\log
f\times c_v\left(\frac{n}{5f}\log f,\comp{G}\right)\le\frac{5n}{f}\log
f \times \frac{n}{\log f}=\frac{5n^2}{f}.
\]
Using inequality (\ref{eqn:range2Int}) and the fact that $f\ge c_1$,
\begin{equation}\label{eqn:e2}
Pr\left(\mathcal{E}_{22}\right)\le Pr\left(c_v\left(\frac{2n}{5f}\log
f,\comp{G}\right)\ge\frac{n}{\log f}\right)\le
\exp\left(-\Theta(n)\right)\le\frac{1}{n^2}.
\end{equation}
\paragraph{\textbf{Range \textrm{3}} $\left(\frac{5n}{f}\log f\le
i\le\frac{n}{\log f}\right)$:} Let $\mathcal{E}_{23}:\sum_{i=\frac{5n}{f}\log
f}^{\frac{n}{\log f} }c_v(i,\comp{G})> \frac{5n^2}{f}$. We use the same
arguments as in the case of Range 2 to show that $Pr(\mathcal{E}_{23})\le
1/n^2$. Let $x=y=\frac{5n}{f}\log f$. Applying equation (\ref{eqn:count})
and subsequently Lemma \ref{lem:nci},
\begin{equation}\label{eqn:range3Int}
Pr\left(c_v\left(\frac{5n}{f}\log f,\comp{G}\right)\ge\frac{5n}{f}\log
f\right)\le\exp\left(20\frac{n}{f}\log f\log\left(\frac{f}{5\log
f}\right)-25\frac{n}{f}\log^2f\right).
\end{equation}
Again using Observation \ref{obs:cvObs1}, it follows that if
$c_v\left(\frac{5n}{f}\log f,\comp{G}\right)\le\frac{5n}{f}\log f$, then,
\[
\sum_{i=\frac{5n}{f}\log f}^{\frac{n}{\log f} }c_v(i,\comp{G})\le
\frac{n}{\log f}\times c_v\left(\frac{5n}{f}\log f,\comp{G}\right)\le
\frac{n}{\log f}\times\frac{5n}{f}\log f=\frac{5n^2}{f}.
\]
Using inequality (\ref{eqn:range3Int}) and the fact that $f\ge c_1$,
\begin{equation}\label{eqn:e3}
Pr\left(\mathcal{E}_{23}\right)\le Pr\left(c_v\left(\frac{5n}{f}\log
f,\comp{G}\right)\ge\frac{5n}{f}\log
f\right)\le\exp\left(-\frac{5n}{f}\log^2 f\right)\le\frac{1}{n^2}.
\end{equation}
\paragraph{\textbf{Range \textrm{4}} $\left(\frac{n}{\log f}\le
i\le n/e^2\right)$:} Let $\mathcal{E}_{24}:\sum_{i=\frac{n}{\log
f}}^{n/e^2}c_v(i,\comp{G})\ge 3n^2/f$. Applying equation (\ref{eqn:count})
with $x=i\ge\frac{n}{\log f}$ and $y=\frac{3n}{f}\log(n/i)$ and Lemma
\ref{lem:nci},
\begin{eqnarray}\label{eqn:range4Int}
Pr\left(c_v(i,\comp{G})\ge \frac{3n}{f}\log(n/i)\right)&&\le{n\choose i}{n\choose
\frac{3n}{f}\log(n/i)}\exp\left(-3i\log(n/i)\right)\nonumber\\
&&\le\exp\left(\log(n/i)\left(
\frac{6n}{f}\log\left(\frac{f}{3\log(n/i)}\right)-i\right)\right)\\
&&\le\exp\left(-\frac{i}{2}\log(n/i)\right).\nonumber
\end{eqnarray}
The final expression comes from the fact that $f\ge c_1$. Next we
observe that,
\[
\sum_{i=\frac{n}{\log
f}}^{n/e^2}\frac{3n}{f}\log(n/i)\le\int_{\frac{n}{\log
f}}^n\frac{3n}{f}\log(n/z)dz\le \frac{3n^2}{f}.
\]
Arguing as in the case of Range 1 and then applying (\ref{eqn:range4Int}),
\begin{eqnarray*}
Pr\left(\mathcal{E}_{24}\right)&&\le
Pr\left(\bigvee_{i=\frac{n}{\log f}}^{n/e^2}c_v(i,\comp{G})\ge \frac{3n}{f}\log(n/i)\right) \le \sum_{i=\frac{n}{\log
f}}^{n/e^2}\exp\left(-\frac{i}{2}\log(n/i)\right).
\end{eqnarray*}
The function $i\log(n/i)$ increases monotonically from $n/\log f$ and
has maxima at $n/e$. Therefore,
\begin{eqnarray}\label{eqn:e4}
Pr\left(\mathcal{E}_{24}\right)
\le\frac{n}{e^2}\exp\left(-\frac{n}{2\log f}\log\frac{n}{n/\log f}\right) =
\frac{n}{e^2}\exp\left(-\frac{n\log\log f}{2\log f}\right)\le\frac{1}{n^2}.
\end{eqnarray}
\paragraph{\textbf{Range \textrm{5}} $\left(n/e^2\le i\le n\right)$:}
Let $\mathcal{E}_{25}:\sum_{i=n/e^2}^nc_v(i,\comp{G})>6n^2/f$.
From (\ref{eqn:range4Int}), we note that $Pr(c_v(n/e^2,\comp{G})\ge
6n/f)\le1/n^2$. Again using Observation \ref{obs:cvObs1}, we see that if
$c_v(n/e^2,\comp{G})\le 6n/f$, then, $\sum_{i=n/e^2}^nc_v(i,\comp{G})\le
n\times 6n/f=6n^2/f$. Hence,
\begin{equation}\label{eqn:e5}
Pr(\mathcal{E}_{25})\le Pr\left(c_v\left(n/e^2,\comp{G}\right)\ge\frac{6n}{f}\right)\le\frac{1}{n^2}.
\end{equation}

Let $Q$ be the union of the events $\mathcal{E}_1$ and
$\mathcal{E}_{2}$. It is clear that $\boxi(G)=\Omega(np(1-p))$ if
the event $Q$ does not occur. From inequalities (\ref{eqn:numFinal}),
(\ref{eqn:e1}), (\ref{eqn:e2}), (\ref{eqn:e3}), (\ref{eqn:e4}) and
(\ref{eqn:e5}), it is evident that $Pr(Q)=\mathcal{O}(1/n^2)$. Hence,
almost surely $\boxi(G)=\Omega(np(1-p))$. \qed
\end{proof}
\begin{corollary}\label{cor:npRandThm}
Let $G\in \mathcal{G}(n,p)$. If $p$ is such that $c_1/n\le p\le c_3<1$, where
$c_3$ is a positive constant, then, almost surely, $\boxi(G)=\Omega(np)$.
\end{corollary}
\begin{corollary}\label{cor:randThmEdges}
Consider graphs with $n$ vertices and $m$ edges such that $c_1n/2\le
m\le c_2n^2/2$, where $c_1$ and $c_2$ are as defined in Corollary
\ref{cor:npRandThm}. Let $M=\ds{{n\choose 2}\choose m}$, be the total
number of graphs on $n$ vertices and $m$ edges. There exists a positive
constant $c$ such that, if $N_c$ is the number of graphs whose boxicity
is at most $cm/n$, then,
\[
\frac{N_c}{M}\rightarrow0 \mbox{ as } n\rightarrow\infty.
\]
\end{corollary}
\begin{proof}
We recall that, in the proof of Theorem \ref{thm:randThm},
$\boxi(G)=\Omega(np(1-p))$ if the event $Q$ does not occur. Let
$p=\frac{m}{{n\choose 2}}$. It can be shown that, given any property $\mathcal{P}$,
$Pr(G \mbox{ satisfies }\mathcal{P}, G\in\mathcal{G}(n,m))\le
3\sqrt{m}Pr(G \mbox{ satisfies }\mathcal{P},
G\in\mathcal{G}(n,p))$ (see \cite[Theorem 2 Chapter 2]{bollobasRandomGraphs}).
Hence, $Pr(G\mbox{ satisfies } Q,G\in\mathcal{G}(n,m))\le
3\sqrt{m}\mathcal{O}(1/n^2)=\mathcal{O}(1/n)$. Therefore, if
$G\in\mathcal{G}(n,m)$, then almost surely, $\boxi(G)=\Omega(m/n)$. Hence
proved.\qed
\end{proof}
For very dense graphs, i.e. with $p\rightarrow1$ as $n\rightarrow\infty$,
it is not possible to infer from Theorem \ref{thm:randThm} that
$\boxi(G)=\Omega(np)$ because of the additional factor $(1-p)$.
For this case we use a different approach to bound the boxicity. A
theorem follows in this regard.
\begin{theorem}
Let $G\in \mathcal{G}(n,p)$ with $p=1-g/n$, where $g(n)$ is any
non-negative function such that $g(n)=o(n)$ and $g(n)=\omega(1/n)$. Then,
\begin{enumerate}
\item for $g\ge c\log n$ where $c$ is some constant, almost surely
$\boxi(G)=\Omega\left(n\right)$,
\item for $g<c\log n$, almost surely,
$\boxi(G)=\Omega\left(\frac{ng}{\log n}\right)$,
\end{enumerate}
\end{theorem}
\begin{proof}
The flow of this proof is very similar to that of Theorem \ref{thm:nk2}.
The probability that a particular edge is present in $\comp{G}$ is
$q=g/n$. The expected number of edges in $\comp{G}$ is ${n \choose
2}q=\frac{(n-1)g}{2}$. Using Chernoff's bound on Poisson trials, we have,
\begin{equation}
Pr\left(\numed{\comp{G}}<(1-\epsilon)\frac{(n-1)g}{2}\right)\le
e^{-\frac{\epsilon^2}{2}\left(\frac{(n-1)g}{2}\right)},
\end{equation}
for a constant $\epsilon\in(0,1)$. Since $g=\omega(1/n)$,
$Pr(\numed{\comp{G}}<(1-\epsilon)(n-1)g/2)\rightarrow0$ as
$n\rightarrow\infty$.\\
Now we will give an upper bound for $\sum_{i=1}^{n-1}c_v(i,\comp{G})$. Let
the expected degree of a vertex in $\comp{G}$ be $d_E=\frac{(n-1)g}{n}$.
\paragraph{\textbf{Case \textrm{1}} $g\ge c\log n$:} First we consider
$c_v(1,\comp{G})$. Using
Chernoff's bound on Poisson trials and subsequently union bound,
\begin{equation}
Pr(c_v(1,\comp{G})\ge(1+\epsilon')d_E=(1+\epsilon)g)\le ne^{-\frac{\epsilon^2}{3}g}.
\end{equation}
for some constants $\epsilon',\epsilon\in(0,1)$.
Taking $c>3/\epsilon^2$, the expression $\rightarrow0$ as
$n\rightarrow\infty$.
\paragraph{\textbf{Case \textrm{2}} $g<c\log n$:} Here again we consider
$c_v(1,\comp{G})$ and apply another variant of Chernoff's bound on
Poisson trials and subsequently the union bound. For $R>6g$,
\begin{equation}
Pr(c_v(1,\comp{G})\ge R)\le n2^{-R}.
\end{equation}
Taking $R=2\log n$, we see that the expression $\rightarrow0$
as $n\rightarrow\infty$. Therefore, almost surely,
$c_v(1,\comp{G})=\mathcal{O}(\log n)$.

For $i>1$, we use Lemma \ref{lem:nci} and equation (\ref{eqn:count}),
\begin{eqnarray*}
Pr\left(c_v(i,\comp{G})\ge j\right)&&\le {n\choose i}{n\choose
j}\left(\frac{g}{n}\right)^{ij}\\
&&\le \exp\left(2i\log(n/i)+2j\log(n/j)+ij\log g-ij\log n\right).
\end{eqnarray*}
For $i>2$, choosing $j>6$, the right hand side for the above expression
$\rightarrow0$ as $n\rightarrow\infty$. Using Observation \ref{obs:cvObs2},
we note that $Pr\left(c_v(2\log n,\comp{G})>0\right)\rightarrow0$ as
$n\rightarrow\infty$. Therefore, almost surely,
\begin{eqnarray*}
\sum_{i=1}^{n-1}c_v(i,\comp{G})&&=\sum_{i=1}^{c_v(1,\comp{G})}c_v(i,\comp{G})\\
&&=\Theta(c_v(1,\comp{G})).
\end{eqnarray*}
Hence proved.  \qed
\end{proof}

\subsection{Spectral Lower Bounds}\label{sec:spec}
Consider a graph $G(V,E)$ and let  $X\subseteq V$.  Recalling the
definition of vertex-boundary and vertex neighbourhood from Section
\ref{sec:neighbours}, we have $\vb(X)\subseteq N'(X)$ and
\begin{equation}
\label{eqn:phiN} |\vb(X)| \ge |N'(X)|-|X|.
\end{equation}

Suppose $G(V,E)$ is a $k$-regular balanced $(A,B)$-bipartite graph with
$2n$ vertices. For any $X\subseteq A$, Tanner \cite{concentratorsTanner}
gives a lower bound for $|N'(X)|/|X|$ using spectral methods. Suppose
the vertices in $A$ and $B$ are ordered separately, we define
the \emph{bipartite incidence matrix} $M$ as follows: $M=[m_{ij}]$,
$m_{ij}=1$ if the $i$th vertex in $A$ is connected to $j$th vertex in
$B$. The largest eigenvalue of $MM^T$ is $k$. Let $\lambda'$ be the
second largest eigenvalue of $MM^T$. Then,
\begin{equation} \label{eqn:tannerBipartite}
|N'(X)| \ge \frac{k^2|X|}{\lambda'+(k^2-\lambda')\frac{2|X|}{n}}.
\end{equation}
This result can be extended to any $k$-regular graph $G(V,E)$ (see
\cite{phdThesisNabil}) as follows. Let $\lambda$ be the second largest
eigenvalue in absolute value of the adjacency matrix of $G$. For any
subset $X\subseteq V$,
\begin{equation} \label{eqn:tanner}
|N'(X)| \ge \frac{k^2|X|}{\lambda^2+(k^2-\lambda^2)\frac{|X|}{n}}.
\end{equation}
\begin{theorem}\label{thm:spec}
Let $G(V,E)$ be a connected $k$-regular graph on $n$ vertices. Let
$\lambda$ be the second largest eigenvalue in absolute value of the
adjacency matrix of $G$. Then,
\[
\boxi(G)\ge\left(\frac{k^2/\lambda^2}{\log\left(\frac{k^2}{\lambda^2}+1\right)}\right)\left(\frac{n-k-1}{2n}\right).
\]
\end{theorem}
\begin{proof}
We first note that $\numed{\comp{G}}=\frac{n(n-k-1)}{2}$. By the
definition of $b_v(i)$ in Equation (\ref{eqn:bvi}) (See Section
\ref{sec:firstMethod}) and by applying equations (\ref{eqn:phiN}) and
(\ref{eqn:tanner}):
\begin{equation}\label{eqn:bviub}
b_v(i,G) \ge \frac{k^2i}{\lambda^2+(k^2-\lambda^2)\frac{i}{n}} - i.
\end{equation}
Recalling that $c_v(i,\comp{G})=n-i-b_v(i,G)$ and applying Theorem
\ref{thm:cvithm} we get,
\begin{eqnarray*}
\boxi(G) &\ge&
\frac{n(n-k-1)/2}{\ds\sum_{i=1}^{n-1}n-i-\left(\frac{k^2i}{\lambda^2+(k^2-\lambda^2)\frac{i}{n}}
- i\right)} \\
&=&
\frac{(n-k-1)/2}{\ds\sum_{i=1}^{n-1}1-\frac{k^2i}{\lambda^2n+(k^2-\lambda^2)i}
} \\
&\ge&
\frac{(n-k-1)/2}{\ds\sum_{i=1}^{n-1}1-\frac{k^2i}{\lambda^2n+k^2i}} =
\frac{(n-k-1)/2}{\ds\sum_{i=1}^{n-1}\frac{\lambda^2n}{\lambda^2n+k^2i}} \\
&=&
\frac{(n-k-1)/2}{\ds\frac{\lambda^2n}{k^2}\ds\sum_{i=1}^{n-1}\frac{1}{\frac{\lambda^2n}{k^2}+i}} \\
&\ge&
\frac{(n-k-1)/2}{\ds\frac{\lambda^2n}{k^2}\left(\log\left(\frac{\lambda^2n}{k^2}+n\right)-\log\left(\frac{\lambda^2n}{k^2}\right)\right)} \\
&=&
\frac{k^2/\lambda^2}{\log\left(\frac{k^2}{\lambda^2}+1\right)}\left(\frac{n-k-1}{2n}\right).
\end{eqnarray*}
Hence proved. \qed
\end{proof}
\subsubsection{Tightness of Theorem \ref{thm:spec}}
Let $l$ and $p$ be integers $\ge 2$. Consider a complete $p$-partite graph
$K_{l,l,\ldots,l}$ where $n=lp$. $K_{l,l,\ldots,l}$ is a \emph{strongly
regular graph}, i.e. it is a $k$-regular graph where each pair of
adjacent vertices has the same number $a\ge0$ of common neighbours,
and each pair of non-adjacent vertices has the same number $c\ge1$ of
common neighbours. For a strongly regular graph, $\lambda$ can be obtained
by solving the quadratic equation $x^2+(c-a)x+(c-k)$ (See \cite[Chapter
3]{algGraphTheoryBiggs}). For $K_{l,l,\ldots,l}$, noting that $k=c=(p-1)l$
and $a=(p-2)l$, we get $\lambda=l$. Using Theorem \ref{thm:spec}
we get $\boxi(G)=\Omega\left(\frac{p}{\log(p)}\right)$. In
\cite{recentProgressesInCombRoberts}, it is
shown that $\boxi(K_{l,l,\ldots,l})=p$. Hence,
our result is tight up to a $\mathcal{O}(\log(p)) =
\mathcal{O}\left(\log\left(\frac{k^2}{\lambda^2}+1\right)\right)$
factor. It would be interesting to see if we can improve this bound to
$\boxi(G)=\Omega\left(\frac{k^2}{\lambda^2} \left(\frac{n-k-1}{2n}\right)\right)$. For
example, when $l=2$ (This graph was considered by Roberts in
\cite{recentProgressesInCombRoberts} and can be obtained by
removing a perfect matching from a complete graph), such an improved
bound will evaluate to $\frac{n-2}{8}$. The boxicity of this graph
was shown to be $n/2$ in \cite{recentProgressesInCombRoberts}.
\subsubsection{Applying the Spectral Bound to Random Regular Graphs}
In 1986, Alon and Boppana \cite{eigenvaluesExpandersAlon} proved that
for a fixed $k$, $\lambda\ge2\sqrt{k-1}$ for almost all $k$-regular
graphs. In the same paper it was conjectured that for any $k\ge3$ and
$\epsilon>0$, $\lambda\le2\sqrt{k-1}+\epsilon$. Recently, Friedman
\cite{proofAlonSecondEigenvalueConjectureFriedman04} proved this
conjecture albeit for a different model of regular graphs (involving
multiple edges and loops). However, using contiguity theorems
\cite{modelsRandomGraphsWormald} it is easy to infer that the same
result applies to the $\mathcal{G}_R(n,k)$ model too. Hence, we can
assume that $\lambda\approx2\sqrt{k-1}$ for a random $k$-regular graph.
We have the following corollary to Theorem \ref{thm:spec}.
\begin{corollary}\label{cor:specAlmost}
Let $\mathcal{G}_R(n,k)$ be the probability space of random $k$-regular
graphs, where $k$ is fixed. For $G\in\mathcal{G}_R(n,k)$, almost surely,
$\boxi(G)=\Omega\left(k/\log k\right)$.
\end{corollary}
We conjecture that for almost all $k$-regular graphs $\boxi(G)=\Omega(k)$.
The reader may be interested to know that a comparable upper bound of
$\mathcal{O}(k)$ for boxicity was conjectured in
\cite{boxicityMaxDegreeSunilNaveenFrancis}: In that paper it was shown that
for any graph $G$, $\boxi(G)\le2\Delta^2$ and it was conjectured that
$\boxi(G)=\mathcal{O}(\Delta)$.

\subsection{Limitations}
The presence of large independent sets in $G$ puts a limitation on the
lower bound that can be achieved using Theorem \ref{thm:cvithm}. For
example, consider a bipartite graph on $2n$ vertices. It contains an
independent set of size at least $n$, the best possible bound we can
get by applying Theorem \ref{thm:cvithm} is ${2n\choose 2}/{n\choose
2}=4$. In general, if $\alpha$ is the independence number of $G$,
we cannot do better than $(n/\alpha)^2$. In view of this limitation,
we seek to motivate the reader regarding the second method, where
effective lower bounds are provided for bipartite graphs (see Theorem
\ref{thm:biUniversal} onwards).

\section{The Second Method}
\subsection{Preliminaries}
\begin{definition}[Cross expansion] \label{def_cross_exp}
Let $A,B \subseteq V$.  Let $t$ be a fixed positive integer such that
$t \le |A|$.  Let $n_t = \min_{S \subseteq A, |S| = t} \{ |N[S,G] \cap
B| \}$.  The {cross expansion coefficient} $\beta_t(A,B)$ is defined as
$n_t / |B|$.
\end{definition}

Usually, in the literature on expander graphs or vertex isoperimetric
problems, to define the expansion coefficient, it is assumed that $A=B=V$
and the vertex boundary $N(S,G)$ is used instead of $N[S,G]$. We have
modified the notion to suit our purpose.

\begin{definition}[Co-expansion] \label{def_comp_exp}
Let $A,B \subseteq V$. Let $t$ be a fixed positive
integer such that $t \le |A|$.  For $S \subseteq A$, let $m_t = \min_{S
\subseteq A, |S| = t} \{ |N'(S,\comp{G}) \cap B| \}$. The {co-expansion
coefficient} $\alpha_t(A,B)$ is defined as $m_t / t$.  For $t \le 0$,
we define $\alpha_t(A, B) = \infty$.
\end{definition}

We have used the word co-expansion to indicate that this is a certain
type of expansion property in the complement of $G$. The reader may want
to observe that the interpretation of the ratios in the co-expansion
and cross expansion are somewhat different: In particular, note the
difference in the denominator.
\begin{observation}\label{obs:coe}
For any two positive integers $i$ and $j$ such that $i<j$,
$i\cdot\alpha_i(A,B)\le j\cdot\alpha_j(A,B)$. This property follows from
the fact that $m_i\le m_j$, by the definition of $N'(S,\comp{G})$.
\end{observation}
The following facts regarding co-expansion are easy to verify.

\begin{lemma}\label{lem:alpha_low}
Let $G(V,E)$ be a non-complete graph on $n$ vertices with maximum degree
$\Delta$ and minimum degree $\delta$, then for any $t\le n$ we have:
\begin{enumerate}
\item Let $|V|=n$. $\alpha_t(V,V)\ge\frac{n-\Delta-1}{n-\delta-1}$.
\item If $G$ is a balanced ($A,B$)-bipartite on $2n$ vertices, then,
$\alpha_t(A,B)=\frac{n-\Delta}{n-\delta}$.
\item If $G$ is $k$-regular, then, $\alpha_t(V,V)\ge1$.
\item If $G$ is $k$-regular and ($A,B$)-bipartite, then, $\alpha_t(A,B)\ge1$.
\end{enumerate}
\end{lemma}
\begin{definition}[$t$-expander] \label{def_t_exp}
A graph $G(V,E)$ is called a \emph{$t$-expander} if and only if the
following holds for any $S \subseteq V$ with $|S| = t$,
\[
|\{v\in V-S|uv \notin E \mbox{~for all~} u \in S\}|<t.
\]
It is easy to see that the above definition can be restated as
follows: $G$ is a $t$-expander if and only if $\comp{G}$ does not
contain a $K_{t,t}$ as a subgraph. For example, a co-planar graph is a
$3$-expander.
\end{definition}

\begin{definition}[Bipartite $t$-expander] \label{def_bi_t_exp}
An ($A,B$)-bipartite graph $G = (V,E)$ is called a bipartite \emph{$t$-expander}
if and only if the following holds for any $S \subseteq A$ with $|S| =
t$,
\[
|\{ v \in B ~|~ uv \notin E \mbox{~for all~} u \in S\}|<t.
\]
\end{definition}
The following lemma on interval graphs will be used in the next section.
\begin{lemma} \label{lem_basic}
Let $I$ be an interval graph. Two vertices $u$ and $v$ are adjacent in $I$
if and only if $l(u) < r(v)$ and $l(v) < r(u)$.  Alternately, $u$ and $v$
are non adjacent in $I$ if and only if $r(u) < l(v)$ or $r(v) < l(u)$.
\end{lemma}
\subsection{Lower Bound Theorem}
\newcommand{\dgone}[1]{\ensuremath{d_{(S_1,S_2)}(#1)}}
\newcommand{\dgtwo}[1]{\ensuremath{d_{(S_2,S_1)}(#1)}}
\newcommand{\dgmin}{\ensuremath{\delta_{(S_1,S_2)}}}
\newcommand{\dgmax}{\ensuremath{\Delta_{(S_2,S_1)}}}
\newcommand{\opt}{\ensuremath{b^*}}

\begin{theorem} \label{thm:thm_main}
Let $S_1, S_2 \subseteq V$ such that $S_1 \ne \emptyset$ and $S_2 \not=
\emptyset$ and $S_1 \cup S_2 = V$. Let there be no vertex $u \in S_2$
such that $N[u] \cap S_1 = S_1$. Let $\opt = \boxi(G)$.  Let $t$ be
a fixed positive integer such that $1 \le t \le |S_1|$.  Let $\beta_t
= \beta_t(S_1,S_2)$.  Let $t^* = |S_2|( 1 - 2\opt (1 - \beta_t))$.
Let $\alpha^{*} = \alpha_{t^*}(S_2, S_1)$.  Then
$$
  \boxi(G) \ge \frac{1}{2 \left( 1- \beta_t  + \frac{t-1}{\alpha^{*}|S_2|} \right) } \enspace .
$$
\end{theorem}

\begin{remark}\label{rem:remSecondMethod}
Before moving on to the proof, we would like to bring to
notice certain observations regarding the lower bound.
\begin{enumerate}
\item $\alpha_t>0$ and hence $\alpha^*>0$. This follows from the fact that
there is no $u\in S_2$ such that $N[u]\cap S_1=S_1$.
\item $(1-\beta_t)+\frac{t-1}{\alpha^*|S_2|}>0$. If $t=1$, then,
$(1-\beta_t)>0$.  This is because, if $\beta_1=1$, it implies that
every vertex in $S_1$ is connected to every vertex in $S_2$, which
contradicts the assumption that there is no $u\in S_2$ such that
$N[u]\cap S_1=S_1$. If $t>1$, then $\frac{t-1}{\alpha^*|S_2|}=0$ only
if $\alpha^*=\infty$, i.e. if $t^*\le0$. But, when $(1-\beta_t)=0$,
$t^*=|S_2|>0$. Hence, both $(1-\beta_t)$ and $\frac{t-1}{\alpha^*|S_2|}$
cannot be 0 at the same time.
\item The maximum value of
$\frac{1}{2\left(1-\beta_t+\frac{t-1}{\alpha^*|S_2|}\right)}$ can be
bounded above by $\max\left(\frac{|S_1|}{2},\frac{|S_2|}{2}\right)$. To see
this, we consider the following two cases:
\begin{enumerate}
\item Suppose $1-\beta_t>0$. The minimum value $1-\beta_t$ can take is
$\frac{1}{|S_2|}$.
\item Suppose $1-\beta_t=0$. From the above discussion $t>1$ and
$t^*=|S_2|$. Since, $\alpha^*\le|S_1|/|S_2|$,
$\frac{t-1}{\alpha^*|S_2|}$ achieves a minimum value at $t=2$, and this
value is equal to $1/|S_1|$.
\end{enumerate}
\item We can assume that $t^* > 0$ because if $t^* \le 0$, the lemma easily
holds as follows: From the definition of $t^*$,
we have $|S_2|( 1 - 2\opt (1 - \beta_t))\le0$ and also, $(1-\beta_t)\ne0$
in this case. Therefore,
\[
\opt \ge \frac{1}{2(1-\beta_t)}\ge \frac{1}{2 \left( 1- \beta_t  +
\frac{t-1}{\alpha^{*}|S_2|}\right)}.
\]
\end{enumerate}
\end{remark}

\begin{proof}[of Theorem \ref{thm:thm_main}]
Let $I_1, \ldots I_{\opt}$ be $\opt$ interval graphs such that $E(G)
= E(I_1) \cap \cdots \cap E(I_{\opt})$. For each interval graph $I_i$,
let $f_i$ be an interval representation with distinct end-points. We denote
$$
\lt{v}_i=l_{f_i}(v)\mbox{ and }\rt{v}_i = r_{f_i}(v) \enspace ,
$$
Let $x_i \in S_1$ be the vertex such that $ | \{ w \in S_1 ~|~ \lt{w}_i >
\lt{x}_i \} |  =  t -1$.  Similarly, let $y_i\in S_1$ be the vertex such
that $| \{ w \in S_1 ~|~ \rt{w}_i < \rt{y}_i \} | = t -1$. Define
$$
\lt{\mathbf{M}}_i =  \lt{x_i}~\mbox{and}~\rt{\mathbf{m}}_i =  \rt{y_i} \enspace
$$
and let
$$
\rt{X}_i = \{ v \in S_2 : \lt{v}_i > \rt{\mathbf{m}}_i\} ~~~~\mbox{and}~~~~ \lt{Y}_i = \{ v \in S_2 : \rt{v}_i < \lt{\mathbf{M}}_i\}  \enspace .
$$

\begin{claim} \label{cl_size}
For all $i \in \{1, \ldots, \opt\}$, $|\rt{X}_i| \le |S_2| (1 - \beta_t) $ ~and~ $|\lt{Y}_i| \le |S_2| (1 - \beta_t) $.
\end{claim}

\begin{proof}
Let $T_i = \{v \in S_1 ~|~ \rt{v_i} \le \rt{\mathbf{m}}_i \}$.

It follows from Lemma \ref{lem_basic} that for each $v \in N[T_i]$, $\lt{v}_i < \rt{\mathbf{m}}_i$.
Thus, if $u \in N[T_i] \cap S_2$ then $u \notin \rt{X}_i$.
Hence $\rt{X}_i \subseteq S_2 - \left( N[T_i] \cap S_2 \right)$.
Recalling the definition of
$\beta_t = \beta_t(S_1,S_2)$, we have $|N[T_i] \cap S_2| \ge
\beta_t |S_2|$.
It follows that  $|\rt{X}_i| \le |S_2| - \beta_t |S_2| = |S_2| ( 1 - \beta_t)$.
Using similar arguments, it follows that $|\lt{Y}_i| \le |S_2| ( 1 -
\beta_t)$. \bqed
\end{proof}
Let $Z = S_2 -\bigcup_{i \in \{1, \ldots, \opt\}} \rt{X}_i\cup\lt{Y}_i$,
i.e.
\[
Z = \left\{ u \in S_2 ~|~ \lt{u}_i < \rt{\mathbf{m}}_i \mbox{~and~}
\rt{u}_i > \lt{\mathbf{M}}_i \mbox{~for all~} i \in \{1, \ldots,
\opt\}\right\}.
\]

\begin{claim} \label{cl_z}
 $|Z| \ge t^*>0$.
\end{claim}
\begin{proof}
First, we recall the assumption that $t^*>0$ (see Remark
\ref{rem:remSecondMethod}, point 4).  Using the definition of $Z$ and
Claim \ref{cl_size}, it follows that $|Z| \ge |S_2| - \sum_{i \in \{1,
\ldots, \opt\}} |X_i^+| - \sum_{i \in \{1, \ldots, \opt\}} |Y_i^-| \ge
|S_2| - 2 \opt |S_2| (1 - \beta_t) \ge |S_2| ( 1 - 2 \opt (1 - \beta_t))
= t^*$.\bqed
\end{proof}

\begin{claim} \label{cl_each_inter}
For each interval graph $I_i$ , $i \in \{1, \ldots, \opt\}$, $$| \{v
\in S_1 ~|~ \exists u \in Z \mbox{~and~} uv \notin E(I_i) \} | \le 2 (
t - 1 ).$$
\end{claim}
\begin{proof}
Fix any interval graph $I_i$.  Let $R_i = \{ u \in S_1 ~|~ \rt{u}_i
\ge \rt{\mathbf{m}}_i \}$ and let $L_i = \{ u \in S_1 ~|~ \lt{u}_i \le
\lt{\mathbf{M}}_i \}$.  Recalling the definition of $\rt{\mathbf{m}}_i$
and $\lt{\mathbf{M}}_i$, it follows that  $|R_i| = |L_i| = |S_1| -
(t-1)$. From the definition of $Z$, we know that for each vertex $v \in
Z$, $\lt{v}_i < \rt{\mathbf{m}}_i$ and $\rt{v}_i > \lt{\mathbf{M}}_i$. If
vertex $u \in L_i \cap R_i$ then $\rt{u}_i \ge \rt{\mathbf{m}}_i>\lt{v}_i$ and
$\lt{u}_i \le \lt{\mathbf{M}}_i<\rt{v}_i$.  It follows from Lemma \ref{lem_basic}
that $uv \in E(I_i)$ for all $v\in Z$.  In other words, $ \{v \in S_1 ~|~ \exists u \in
Z \mbox{~and~} uv \notin E(I_i) \}  \subseteq S_1 - ( R_i \cap L_i) =
( S_1 - R_i )  \cup (S_1 - L_i)$.  Since $|S_1 - R_i| = t -1$ and $|S_1 -
L_i| = t -1$, we obtain the claimed bound.\bqed
\end{proof}
From the definition of $\alpha_t$ it follows that $|N'(Z,\comp{G})
\cap S_1| \ge \alpha_{|Z|}(S_2, S_1) |Z|$. Recalling that $|Z|\ge t^*$
(from Claim \ref{cl_z}) and using Observation \ref{obs:coe} we obtain
\begin{equation} \label{eq_two}
|N'(Z,\comp{G}) \cap S_1| \ge \alpha_{|Z|} (S_2, S_1) |Z| \ge \alpha_{t^*}
(S_2, S_1) t^* = \alpha^* t^*.
\end{equation}
Clearly $N'(Z,\comp{G}) \cap S_1 = \{v \in S_1 ~|~ \exists u \in Z
\mbox{~and~} uv \notin E(G) \}$.  Since each missing edge in $G$ should be
missing in at least one of the $\opt$ interval graphs, it follows from
Claim \ref{cl_each_inter} that $|N'(Z,\comp{G}) \cap S_1| \le 2 \opt
(t-1)$.  Combining this with inequality (\ref{eq_two}), we obtain
$2 \opt(t-1) \ge |N'(Z,\comp{G}) \cap S_1| \ge \alpha^* t^*.$
It follows that
\begin{equation} \label{eq_lower}
2 ( t - 1 ) \opt  \ge \alpha^* t^*.
\end{equation}
Substituting for $t^*$ with $|S_2| ( 1 - 2 \opt(1 - \beta_t))$,
inequality (\ref{eq_lower}) implies that
$$
2 (t -1 ) \opt  \ge \alpha^* |S_2| (1 - 2\opt (1 - \beta_t)).
$$
Rearranging the terms, it follows that
\begin{equation} \label{eq_3}
   {2 \opt \left( \alpha^*(1- \beta_t)  + \frac{t-1}{|S_2|} \right) }   \ge
   {\alpha^*}.
\end{equation}
Recalling that $\alpha^*>0$ and $(1-\beta_t)+\frac{t-1}{\alpha^*|S_2|}>0$
(see Remark \ref{rem:remSecondMethod}, points 1 and 2), on rearranging
the above inequality we get the required expression.  \qed
\end{proof}

\subsection {Consequences}\label{sec:consMainThm}
In a graph $G$, a vertex is called a \emph{universal vertex} if it is
adjacent to all other vertices.
\begin{theorem}\label{thm:universal}
Let $G$ be a non-complete graph with minimum degree $\delta$.
Let $n_u$ be the number of universal vertices in $G$. Then
$$
	\boxi(G) \ge \frac{n - n_u}{ 2 ( n - \delta - 1) } \enspace .
$$
\end{theorem}
\begin{proof}
Let $U$ be the set of universal vertices in $G$. We have $|U| = n_u$.
Let $G'$ be the graph induced by $V - U$ on $G$.
Let $\delta'$ be the minimum degree of $G'$. It is easy to see
that $\delta' = \delta - n_u$.
We apply Theorem \ref{thm:thm_main} on $G'$ as follows:
take $S_1 = S_2 = V - U$ and fix $t = 1$.
Note that, we can apply Theorem \ref{thm:thm_main} since there are no
universal vertices in $G'$. Clearly $\beta_t = \beta_1(S_1, S_2) = \frac{ \delta' + 1}{ n - n_u}$,
and thus $1 - \beta_t = \frac{n - \delta - 1}{n - n_u}$. Hence, from Theorem
\ref{thm:thm_main}
we obtain that
$\boxi(G') \ge \frac{1}{2( 1 - \beta_t) } = \frac{n - n_u}{ 2(n - \delta -
1)}$.\qed
\end{proof}
For a $(n-k-1)$-regular graph, this result is same as Theorem
\ref{thm:nk2}. Note however that for general graphs, the above result
is better than the one mentioned in Section \ref{sec:immAppMethod1},
namely $\boxi(G)\ge \frac{n\delta(\comp{G})}{2\Delta(\comp{G})^2}$.

\begin{theorem}\label{thm:biUniversal}
Let $G$ be a non-complete bipartite graph with two parts $A$ and
$B$. Let $u_B$ be the number  of vertices in $B$ that are adjacent to
all vertices in $A$. Let $\delta_A$ be the minimum degree of the vertices
in $A$ . Then,
$$
	\boxi(G) \ge \frac{|B| - u_B }{ 2 ( |B| - \delta_A) } \enspace .
$$
\end{theorem}
\begin{proof}
Let $U_B \subseteq B$ be the set of vertices that are adjacent to
all the vertices in $A$. We have $|U_B| = u_B$. Let $G'$ be the graph
induced by $A \cup (B - U_B)$ on $G$.  Apply Theorem \ref{thm:thm_main}  on
$G'$ as follows: fix $S_1 = A$, $S_2 = B - U_B$ and $t = 1$. Note that
Theorem \ref{thm:thm_main} can be applied since there is no vertex $u\in
B-U_B$ that is adjacent to all vertices in $A$. Clearly,
the minimum degree of the vertices in $S_1$ is $\delta'_A = \delta_A -
u_B$.  We have $\beta_t = \beta_1(S_1, S_2) = \frac{\delta'_A}{|B| - u_B}$,
and thus $1 - \beta_t = \frac{|B| - \delta_A}{|B| - u_B}$. Applying Theorem
\ref{thm:thm_main} we obtain that $\boxi(G') \ge \frac{1}{2 (1 - \beta_t)} =
\frac{|B| - u_B}{2(|B| - \delta_A)}$.\qed
\end{proof}

\paragraph{\textnormal{\textbf{Tightness of Theorem
\ref{thm:biUniversal}:}}} Let $G$ be a balanced (A,B)-bipartite
graph on $2n$ vertices with the following structure: Let $n$, $k$
and $l$ be integers such that $kl=n$. Further, let $A=A_1\uplus
A_2\uplus\cdots\uplus A_l$ and $B=B_1\uplus B_2\uplus\cdots\uplus
B_l$, where, $|A_i|=|B_i|=k$. For any two vertices, $u\in A_i$ and
$v\in B_j$, let $uv\in E\Longleftrightarrow i\ne j$. Clearly, $G$
is an $(n-k)$-regular graph. From Theorem \ref{thm:biUniversal},
$\boxi(G)\ge n/2k=l/2$. Now, we present a set of $l+2$ interval
graphs $\mathcal{I}=\{I_i| 1\le i\le l+2\}$ whose edge intersection
gives $G$. The interval representation for each $I_i$, $1\le
i\le l$ is as follows: Vertices in $A_i$ are mapped to the interval
$[0,1]$ and vertices in $B_i$ is mapped to the interval $[2,3]$. The
rest of the vertices are mapped to the interval $[0,3]$. For $i=l+1$
(resp. $l+2$), we have a one-to-one mapping of vertices in $A_i$ ($B_i$)
to $n$ disjoint intervals $[2j,2j+1]$, $j\in\{0,1,\ldots,n-1\}$. The
rest of the vertices are assigned the interval $[0,2n-1]$. Thus we note
that Theorem \ref{thm:biUniversal} is tight up to a constant factor.

\begin{theorem}\label{thm:tExp}
Let $G$ be a graph on $n$ vertices with minimum degree
$\delta$ and maximum degree $\Delta<n-1$. If $G$ is a $t$-expander then
$$
\boxi(G) \ge \frac{n (n - \Delta-1)}{2(t-1)\left[(n - \Delta-1) + (n -
\delta-1)\right]} \enspace .
$$
\end{theorem}
\begin{proof}
We apply Theorem \ref{thm:thm_main} on $G$ as follows. Fix $S_1 = S_2
= V$.  It is easy to see that if $G$ is a $t$-expander then $n ( 1-
\beta_t)\le t-1$. From Lemma \ref{lem:alpha_low} we have $\alpha^* \ge
(n-\Delta-1)/(n-\delta-1)$. Substituting for $1-\beta_t$ and $\alpha^*$
in Theorem \ref{thm:thm_main} we obtain the result.
\end{proof}
In Theorem \ref{thm:nkExamples} of Section \ref{sec:immAppMethod1}, we
obtained lower bounds for the boxicity of regular co-planar graphs and
regular $C_4$-free graphs based on the absence of $K_{3,3}$ and $K_{2,2}$
respectively as subgraphs in their complements. We observe that these
graphs are specific subclasses of regular $t$-expanders. The same results
can be obtained using the following corollary to Theorem \ref{thm:tExp}.

\begin{corollary}
Let $G$ be a regular non-complete $t$-expander graph. Then
$$
\boxi(G) \ge \frac{n}{4(t-1)} \enspace .
$$
\end{corollary}

\begin{theorem}\label{thm:bipartiteRandThm}
Let $G\in \mathcal{G}_B(2n,p)$ be a random balanced $(A,B)$-bipartite
graph on $2n$ vertices. Suppose $c_1'\frac{\log n}{n}\le
p\le e^{-\frac{c_2'}{n}}$, for some constant $c_1'>4$ and any positive constant
$c_2'$, then almost surely,
$\boxi(G)=\Omega\left(\frac{np}{\log n}\right)$.
\end{theorem}
\begin{proof}
Let $U_B$ be the random variable for the number of vertices in $B$ that
are adjacent to all vertices in $A$. We easily see that $E(U_B)=np^n$. Let
us consider the event $\mathcal{E}:U_B>(1+\epsilon)ne^{-c_2'}$
where $\epsilon\in(0,1)$ is a constant chosen such that
$(1+\epsilon)e^{-c_2'}<1$. For $p=\exp(-\frac{c_2'}{n})$,
$E(U_B)=ne^{-c_2'}$. Using Chernoff's bounds on Poisson trials,
$Pr(\mathcal{E})\le\exp\left(-\frac{\epsilon^2}{3}ne^{-c_2'}\right)
\le\frac{1}{n^2}$. Since $U_B$ is a monotonically increasing event (See
Footnote \ref{mon}), for any $p<e^{-c_2'/n}$,
$Pr(\mathcal{E})\le\frac{1}{n^2}$.

We use Theorem \ref{thm:thm_main} with $S_1=A$ and $S_2=B'$, where $B'$ is
the subset of $B$ without the vertices which are adjacent to all vertices
in $A$.
We will first show that, for $t=c_1'\log n/p$, almost surely
$n(1-\beta_t)<t$, where $c_1'>4$. This is
equivalent to showing that there exists no pair of sets, say $X\subseteq
A$ and $Y\subseteq B$, $|X|=|Y|=t$, such that $\forall x\in X$ and $y\in
Y$, $xy\notin E(G)$. Applying union bound, we have
\begin{eqnarray*}
Pr\left((1-\beta_t)\ge t/n\right)&& \le{n\choose t}{n\choose t}q^{t^2},
\end{eqnarray*}
where, $q=1-p\le e^{-p}$. Applying Lemma \ref{lem:nci},
\begin{eqnarray*}
Pr\left((1-\beta_t)\ge t/n\right)&&\le\exp\left(4t\log(n/t)-t^2p\right),\\
\mbox{(Substituting $t=c_1'\log n/p$)}&&\le\exp\left(\frac{c_1'\log^2
n}{p}(4-c_1')\right)\le\frac{1}{n^2}.
\end{eqnarray*}
Using Chernoff's
bound on Poisson trials and union bound, we have
$Pr\left(\delta(G)<(1-\epsilon)np\right)\le\exp\left(-\frac{
\epsilon^2}{2}np\right)\le \frac{1}{n^2}$ and
$Pr\left(\Delta(G)>(1+\epsilon)np\right)\le\exp\left(-\frac{
\epsilon^2}{3}np\right)\le \frac{1}{n^2}$ for some constant
$\epsilon\in(0,1)$. Applying Lemma
\ref{lem:alpha_low}, we have $\alpha^*=\Omega(1)$, almost
surely. Substituting these values in Theorem \ref{thm:thm_main}, we get
the desired result. \qed
\end{proof}

\begin{corollary}\label{cor:bipartiteThmEdges}
Consider balanced bipartite graphs with $2n$ vertices and $m$ edges
such that $c_1'n\log n\le m\le n^2-c_2'n$, where $c_1'$ and $c_2'$ are
as defined in Theorem \ref{thm:bipartiteRandThm}. Let $M=\ds{n^2\choose
m}$, be the total number of balanced bipartite graphs on $2n$ vertices
with exactly $m$ edges. There exists a positive constant $c$ such that,
if $N_c^B$ is the number of balanced bipartite graphs whose boxicity is
at most $cm/(n\log n)$, then,
\[
\frac{N_c^B}{M}\rightarrow0 \mbox{ as } n\rightarrow\infty.
\]
\end{corollary}
\begin{proof}
The proof is very similar to that of Corollary \ref{cor:randThmEdges}.
In Theorem \ref{thm:bipartiteRandThm}, we recall that for
$G\in\mathcal{G}_B(2n,p)$, where $c_1'\frac{\log n}{n}\le p\le
e^{-\frac{c_2'}{n}}$, $box(G)=\Omega\left(\frac{np}{\log n}\right)$
with probability $\mathcal{O}(1/n^2)$. With $p=\frac{m}{n^2}$,
we note that $p$ is in the permissible range as required by
Theorem \ref{thm:bipartiteRandThm}. It can be shown that,
given any property $\mathcal{P}$, $Pr(G \mbox{ satisfies
}\mathcal{P}, G\in\mathcal{G}_B(2n,m))\le 3\sqrt{m}Pr(G \mbox{
satisfies }\mathcal{P}, G\in\mathcal{G}_B(2n,p))$ (this is a
variant of \cite[Theorem 2 Chapter 2]{bollobasRandomGraphs}).
Hence, $Pr(G\mbox{ satisfies } Q,G\in\mathcal{G}_B(2n,m))\le
3\sqrt{m}\mathcal{O}(1/n^2)=\mathcal{O}(1/n)$. Therefore, if
$G\in\mathcal{G}_B(2n,m)$, then almost surely, $\boxi(G)=\Omega(m/(n\log
n))$. Hence proved.\qed
\end{proof}

\begin{theorem}
Let $G$ be a random $k$-regular balanced ($A,B$)-bipartite graph
on $2n$ vertices. Let $\lambda'$ be the second largest eigenvalue
of $MM^T$, where $M$ is the bipartite incidence matrix of $G$ (See
Section \ref{sec:spec} for definition). If $\lambda'\ne 0$, then,
$\boxi(G)=\frac{k}{4\sqrt{\lambda'}}$.
\end{theorem}
\begin{proof}
We use Theorem \ref{thm:thm_main} with $S_1=A$ and $S_2=B$. Since $G$
is regular, by Lemma \ref{lem:alpha_low} we have $\alpha^*\ge 1$. Using
(\ref{eqn:tannerBipartite}) from Section \ref{sec:spec}, for any set
$X\subseteq A$, $|X|=t$, we have
\[
n\beta_t\ge|N[X,G]\cap B|=|N(X,G)|\ge
\frac{k^2t}{\lambda'+(k^2-\lambda')\frac{t}{n}}.
\]
On substituting $t=\frac{n}{\frac{k}{\sqrt{\lambda'}}+1}$ in the above
inequality, we observe that $(1-\beta_t)\le t/n$. Substituting in
Theorem \ref{thm:thm_main} we get the desired result. \qed
\end{proof}

\section*{Acknowledgements}
We thank Joel Friedman for personal communication regarding his proof of
Alon's conjecture.

config: arxiv