text:
\begin{document}

\title{$k$-Sets and Rectilinear Crossings in Complete Uniform Hypergraphs}

\author{Rahul Gangopadhyay\inst{1} \and
Saswata Shannigrahi\inst{2}}

\authorrunning{R. Gangopadhyay et al.}

\institute{ IIIT Delhi, India\\
\email{rahulg@iiitd.ac.in}\\
\and
IIT Ropar, India\\
\email{saswata@iitrpr.ac.in}}

\maketitle

\begin{abstract}
 In this paper, we study the $d$-dimensional rectilinear drawings of the complete $d$-uniform hypergraph $K_{2d}^d$. Anshu et al. [Computational Geometry: Theory and Applications, 2017] used Gale transform and Ham-Sandwich theorem to prove that there exist  $\Omega \left(2^d\right)$ crossing pairs of hyperedges in such a drawing of $K_{2d}^d$.  We improve this lower bound by showing that there exist  $\Omega \left(2^d \sqrt{ d}\right)$ crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$. \par
\indent ~~ In addition, we show that there are  $\Omega \left(2^d {d^{3/2}}\right)$ crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$ when its $2d$ vertices are either not in convex position in $\mathbb{R}^d$ or form the vertices of a $d$-dimensional convex polytope satisfying one of the following two conditions: (a) the polytope is $t$-neighborly but not $(t+1)$-neighborly for some constant $t\geq1$ independent of $d$, (b) the polytope is $\left(\floor{d/2}-t'\right)$-neighborly for some constant $t' \geq 0$ independent of $d$.

  \keywords{Rectilinear Crossing Number \and Neighborly Polytope \and Gale Transform \and Affine Gale Diagram \and $j$-Facet \and $k$-Set \and Balanced Line}

\end{abstract}
\vspace{-0.5cm}
\section{Introduction}
\label{Intro}
For a sufficiently large positive integer $d$, let $K_{n}^d$ denote the complete $d$-uniform hypergraph with $n \geq 2d$ vertices. A \textit{$d$-dimensional rectilinear drawing} of $K_{n}^d$ is defined as an embedding of it in $\mathbb{R}^d$ such that the vertices of $K_{n}^d$ are points in general position in $\mathbb{R}^d$ and each hyperedge is drawn as the $(d-1)$-simplex formed by the $d$ corresponding vertices \cite{AS}. Note that a set of points in $\mathbb{R}^d$ is said to be in \textit{general position} if no $d+1$ of them lie on a $(d-1)$-dimensional hyperplane. A $u$-simplex and a $v$-simplex are said to be {\textit{crossing}} if they are vertex disjoint and contain a common point in their relative interiors \cite{DP}.  As a result, a pair of hyperedges in a $d$-dimensional rectilinear drawing of  $K_{n}^d$ are said to be \textit{crossing} if they do not have a common vertex  and  contain a common point in their relative interiors \cite{AS,AGS,DP}. The {\textit{$d$-dimensional rectilinear crossing number}} of $K_{n}^d$, denoted by $\overline {cr}_d(K_{n}^d)$, is defined as the minimum number of crossing pairs of hyperedges among all $d$-dimensional rectilinear drawings of $K_{n}^d$ \cite{AS,AGS}. \par
Since the crossing pairs of hyperedges formed by a set containing $2d$ vertices of $K_{n}^d$  are distinct from the crossing pairs of hyperedges formed by another set of $2d$ vertices, it can be observed that $\overline {cr}_d(K_{n}^d) \geq \overline {cr}_d(K_{2d}^d)\dbinom{n}{2d}$ \cite{AS}. The best-known lower bound on $\overline {cr}_d(K_{2d}^d)$ is $\Omega (2^d)$ \cite{AGS}.  Anshu et al. \cite{AGS} also studied a $d$-dimensional rectilinear drawing of $K_{2d}^d$ where all its vertices are placed on the {\textit{$d$-dimensional moment curve}} $\gamma=\{(a,a^2,\ldots, a^d): a \in \mathbb{R}\}$ and proved that the number of crossing pairs of hyperedges is  $\Theta\left(4^d/ \sqrt{d}\right)$ in this drawing. \par
As described above, an improvement of the lower bound on  $\overline {cr}_d(K_{2d}^d)$  improves the lower bound on  $\overline {cr}_d(K_{n}^d)$.
Let us denote the points corresponding to the set of vertices in a $d$-dimensional rectilinear drawing of the hypergraph $K_{2d}^d$ by
$V = \{v_1, v_2, \ldots, v_{2d}\}$.
The points in $V$ are said to be in  {\textit{convex position}} if there does not exist any point $v_i \in V$ (for some  $i$ in the range $1\leq i \leq 2d$) such that $v_i$ can be expressed as a convex combination of the points in $V \setminus \{v_i\}$, and such a drawing of $K_{2d}^d$ is called a {\textit{$d$-dimensional convex drawing}} of it \cite{AGS}.  \par
 Note that the convex hull of the vertices of $K_{2d}^d$ in a $d$-dimensional convex drawing of it forms a $\textit{$d$-dimensional convex polytope}$ with its vertices in general position.  For any $t\geq 1$, a \textit{$d$-dimensional $t$-neighborly polytope} is a
$d$-dimensional convex polytope in which each subset of its vertex set having less than or equal to $t$ vertices forms a face \cite[Page 122]{GRU}.  Such a polytope is said to be  \textit{neighborly}  if it is $\floor{d/2}$-neighborly. Note that any $d$-dimensional convex polytope can be at most $\floor{d/2}$-neighborly unless it is a $d$-simplex which is $d$-neighborly \cite[Page 123]{GRU}. The {\textit{$d$-dimensional cyclic polytope}} is a special kind of neighborly polytope where all its vertices are placed on the $d$-dimensional moment curve \cite[Page 15]{ZIE}. Using these definitions and notations, let us describe our contributions in this paper.

In Section \ref{imprvcross}, we improve the lower bound on $\overline {cr}_d(K_{2d}^d)$. In particular, we prove the following theorem which implies Corollary \ref{thm41}.

\begin{theorem}
\label{thm4}
$\overline {cr}_d(K_{2d}^d)= \Omega(2^d \sqrt{d})$.
\end{theorem}
\begin{corollary}
\label{thm41}
$\overline {cr}_d(K_{n}^d)= \Omega(2^d \sqrt{d})\dbinom{n}{2d}$.
\end{corollary}
We then prove the following theorems to obtain lower bounds on the number of crossing pairs of hyperedges in some special types of $d$-dimensional rectilinear drawings of  $K_{2d}^d$.
 \begin{theorem}
\label{thm1}
The number of crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$ is $\Omega (2^d {d^{3/2}})$ if the vertices of $K_{2d}^d$ are not in convex position.\end{theorem}
\begin{theorem}
\label{thm2}
For any constant $t \geq 1$ independent of $d$, the number of crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$ is $\Omega (2^d {d^{3/2}})$ if the vertices of $K_{2d}^d$ are placed as the vertices of a $d$-dimensional $t$-neighborly polytope that is not $(t+1)$-neighborly.
\end{theorem}
\begin{theorem}
\label{thm3}
For any constant $t' \geq 0$ independent of $d$, the number of crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$ is $\Omega (2^d d^{5/2})$ if the vertices of $K_{2d}^d$ are placed as the vertices of a $d$-dimensional $(\floor{d/2}-t')$-neighborly polytope.
\end{theorem}

\noindent Note that the $t'=0$ case in Theorem \ref{thm3} corresponds to a neighborly polytope. As mentioned above, the number of crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$ is known to be $\Theta(4^d/\sqrt{d})$ when such a polytope is cyclic.\\

\noindent {\bf Techniques Used:} We use the properties of Gale transform, affine Gale diagram, $k$-sets and balanced lines to prove Theorems
\ref{thm4}, \ref{thm1}, \ref{thm2} and \ref{thm3}. We discuss these properties in detail in Sections \ref{TU} and \ref{TU1}. In addition, a few other results used in these proofs are mentioned below.
Let us first state  the Ham-Sandwich theorem and the Caratheodory's theorem  that are used in the proofs of Theorems \ref{thm4} and \ref{thm1}, respectively.\\

 \noindent{\textbf {Ham-Sandwich Theorem:}} \cite{JM,STO}  There exists a $(d-1)$-hyperplane $h$ which simultaneously bisects $d$
finite point sets $P_1, P_2, \ldots, P_d$ in $\mathbb{R}^d$, such that each of
the
open half-spaces created by $h$ contains at most
$\left\lfloor\small{{|P_i|}/{2}}\right\rfloor$
points of $P_i$ for each $i$ in the range $1 \leq i \leq d$.\\

\noindent{\textbf {Carath\'{e}odory's Theorem:}} \cite{JM,ST} Let $X \subseteq \mathbb{R}^d$. Then, each point in the convex hull $Conv(X)$ of $X$ can be expressed as a convex combination of at most $d+1$ points in $X$.\\

\noindent In the following, we state the Proper Separation theorem that is used in the proof of Lemma \ref{extension}. Two non-empty convex sets are said to be \textit{properly separated} in $\mathbb{R}^d$ if they lie in the opposite closed half-spaces created by a $(d-1)$-dimensional hyperplane and both of them are not contained in the hyperplane.  \\

\noindent{\textbf {Proper Separation Theorem:}} \cite[Page 148]{OG} Two non-empty convex sets can be properly separated in $\mathbb{R}^d$ if and only if  their relative interiors are disjoint.\\

\noindent The proof of the following lemma, which is used in the proofs of all four theorems, is the same proof mentioned in \cite{AGS} for the special case $u=v=d-1$. For the sake of completeness, we repeat its proof in full generality.
\begin{lemma}\cite{AGS}
\label{extension}
Consider a set $A$ that contains at least $d+2$ points in general position in $\mathbb{R}^d$. Let $B$ and $C$ be its disjoint subsets such that $|B|= b$, $|C|=
c$, $2 \leq b,c \leq d$ and $b+c \geq d+2$. If the $(b-1)$-simplex formed by
$B$ and the
$(c-1)$-simplex formed by $C$ form a crossing pair, then the $u$-simplex ($u \geq b-1$) formed by a point set $B'\supseteq B$ and  the $v$-simplex ($v \geq c-1$) formed by a point set $C' \supseteq C$ satisfying $B' \cap C' = \phi$, $|B'|, |C'| \leq d$  and $B', C' \subset A$ also form a crossing pair.
\end{lemma}
 \begin{proof}
For the sake of contradiction, we assume that there exist a $u$-simplex and a $v$-simplex, formed respectively by the disjoint point sets $B' \supseteq B$ and $C' \supseteq C$, that do not cross. We consider two cases.
\begin{case**}
{\normalfont Let us assume that $Conv(B') \cap Conv(C') = \phi$. It clearly leads to a contradiction since $Conv(B) \cap Conv(C) \ne \phi$.}
\end{case**}
\begin{case**}
{\normalfont Let us assume that $Conv(B') \cap Conv (C') \neq \phi$. Since the relative interiors of $Conv(B')$ and $Conv(C')$ are disjoint, the Proper Separation theorem implies that there exists a $(d-1)$-dimensional hyperplane $h$ such that $Conv(B')$ and $Conv(C')$ lie in the opposite closed half-spaces determined by $h$.   It implies that $Conv(B)$ and $Conv(C)$ also lie in the opposite closed half-spaces created by $h$. Since the relative interiors of $Conv(B)$ and $Conv(C)$ are not disjoint and they lie in the opposite closed halfspaces of $h$, it implies that all $b+c \geq d+2$ points in $B \cup C$ lie on $h$.  This leads to a contradiction since the points in $B \cup C$ are in general position in $\mathbb{R}^d$.} \qed
\end{case**}

\end{proof}
\vspace{-0.5cm}
\section{Gale Transform and its Properties}
\label{TU}
The {\textit{Gale transformation}} is a useful technique to investigate the properties of high dimensional point sets \cite{GL}. Consider a sequence of $m>d+1$ points $P=$ $<p_1,p_2, \ldots, p_m>$ in $\mathbb{R}^d$ such that the affine hull of the points is $\mathbb{R}^d$. Let the  $i^{th}$ point $p_i$ be represented as $(x_1^i, x_2^i, \ldots, x_d^i)$. To compute a Gale transform  of $P$, let us consider the $(d+1)\times m$ matrix $M(P)$ whose $i^{th}$ column is
$\begin{pmatrix}
  x_1^i \\
  x_2^i \\
  \vdots \\
  x_d^i \\
  1
\end{pmatrix}.
$
Since there exists a set of $d+1$ points in $P$ that is affinely independent, the rank of  $M(P)$ is $d+1$. Therefore, the dimension of the null space of $M(P)$ is $m-d-1$.  Let $\{(b_1^1, b_2^1, \ldots, b_m^1),$  $(b_1^2, b_2^2, \ldots,
b_m^2), \ldots,(b_1^{m-d-1}, b_2^{m-d-1},$ $\ldots, b_m^{m-d-1}) \}$ be a set of $m-d-1$ vectors that spans the null space of $M(P)$. A Gale transform $D(P)$ is the sequence of vectors $D(P)$ $=$ $<g_1,g_2, \ldots, g_m>$ where $g_i= (b_i^1$, $b_i^2$, $\ldots,
b_i^{m-d-1})$ for each  $i$ satisfying $1 \leq i \leq m$. Note that $D(P)$ can also be treated as a point sequence in $\mathbb{R}^{m-d-1}$.\par
We define a {\textit{linear separation}}  of $D (P)$ to be a partition of the vectors in $D(P)$  into two disjoint sets of vectors $D^+(P)$ and $D^-(P)$ contained in the opposite open half-spaces created by a linear hyperplane (i.e., a hyperplane passing through the origin). A linear separation is said to be \textit{proper} if one of the sets among  $D^+(P)$ and $D^-(P)$ contains $\floor{{m}/{2}}$ vectors and the other contains $\ceil{{m}/{2}}$ vectors.  We use the following properties of $D(P)$ in the proofs of our theorems. The first two of these properties are used in the proofs of all four theorems. The third property is used in the proof of Theorem \ref{thm1} and the last one is used in the proof of Theorem \ref{thm2}.

\begin{lemma}\cite[Page 111]{JM}
\label{genposi}
If the points
in $P$ are in general position in $\mathbb{R}^d$, each collection of $m-d-1$ vectors in $D(P)$ spans $\mathbb{R}^{m-d-1}$.
\end{lemma}

\begin{lemma}\cite[Page 111]{JM}
\label{bjection}
Consider two integers $u$ and $v$ satisfying $u+v+2 = m$ and $u,v \geq 0$. If the points in $P$ are in general
position in $\mathbb{R}^d$, there exists a
bijection between the crossing pairs of $u$ and $v$-simplices
in $P$ and the linear separations of  $D(P)$ into $D^+(P)$ and $D^-(P)$
such that $|D^+(P)| = u+1$ and $|D^-(P)| = v+1$.
\end{lemma}
\begin{lemma}\cite[Page 111]{JM}
\label{convexity}
The points in $P$ are in convex position in $\mathbb{R}^d$ if
and only if there
is
no linear hyperplane  with exactly one vector from $D(P)$ in one of the open half-spaces created by it.
\end{lemma}
\begin{lemma}\cite[Page 126]{GRU}
\label{neigh}
If the points in $P$ are in convex position, the $d$-dimensional polytope formed by the convex hull of the points in $P$ is $t$-neighborly if and only if each of the open half-spaces created by a linear hyperplane  contains at least $t+1$ vectors of $D(P)$.
\end{lemma}
The proofs of the first three lemmas are easy to see. The fourth lemma, a generalized version of which is given as an exercise in \cite{GRU}, can be proved using Lemma \ref{bjection} and the fact \cite[Page 111]{JM} that any $t$-element subset $P'= \{p_{i_1},p_{i_2}, \ldots,$ $ p_{i_t}\}  \subset P$ forms a $(t-1)$-dimensional face of the  $d$-dimensional polytope formed by the convex hull of the  points in $P$ if and only if the convex hull of the points in $D(P)\setminus \{g_{i_1},g_{i_2}, \ldots, g_{i_t}\}$ contains the origin.
\iffalse
\begin{figure}[h]
    \centering
    \includegraphics[width = 0.6\textwidth]{Standard-Gale-Dia.eps}
    \caption{Standard Gale Transform of $Q$}
    \label{fig:stddia}
\end{figure}

\begin{proof}
Suppose $Q$ is a $t$-neighborly polytope with $d+3$ vertices. Let there be a partition of $D^*(Q)$ in two sets of size $d+3-k$ and $k$. Lemma \ref{bjection} implies that there exist a $(k-1)$-simplex and a $(d+2-k)$-simplex such that they form a crossing. This is a contradiction to the fact that every set of $k$-vertices of $Q$ forms a face of $Q$. This implies each open hemisphere of $S^1$ contains at least $k+1$ points of $D^*(Q)$.

To prove the other side, let us consider a standard Gale Transform $D^*(Q)$ which is a collection of $d+3$ unit length vector is $\mathbb{R}^2$. This implies that all the end points of the vectors lie on the unit circle centred at origin. Consider a linear partition (a partition of the vectors by a line passing through the origin) of the vectors in $D^*(Q)$by a line $l$, such that one of the partition contains $k+1$ vectors and another side contains $d+2-k$ vectors. We label the vectors as shown in the Figure \ref{fig:stddia}. Let us assume that $Q$ is not $k$-neighborly, i.e.,there exist a collection of $k$ vectors $\overline V=\{v_{i_1},v_{i_2}, \ldots, v_{i_k}\}$in $D^*(Q)$, such that the corresponding $k$-vertices in $Q$ do not span a face. This implies that convex hull of the points $D^*(Q)\setminus \overline V$ does not contain origin inside it. Let us consider following $3$ cases to prove that if $Q$ is not a $k$-neighborly polytope with $d+3$ vertices, then there exist a open hemisphere of $S^1$ containing at most $k$ vectors.

\begin{case}
    Let $\overline V \subset \{v_{k+2}, v_{k+3}, \ldots, v_{d+2-k}\}$. This implies all the vectors in $ \{v_{k+2}, v_{k+3}, \ldots, v_{d+2-k}\} \setminus \overline V$ lie on the right side of the line $-v_{k+1}$ or on the left side of the line $-v_{1}$. This implies either a line along $v_1$ or a line along $v_{k+1}$ creates a open hemisphere of $S^1$ which contains at most $k$ vectors.
  \end{case}
  \begin{case}
 Let $\overline V \subset \{v_1, v_2, \ldots, v_{k+1}\}$. This implies there exist exactly one vector ${v_i}=\{v_1, v_2, \ldots, v_{k+1}\} \setminus \overline V$, for $1\ leq i \leq k+1$, such that all the vectors in  $\{v_{k+2}, v_{k+3}, \ldots, v_{d+2-k}\}$ lie on the one side of the line $l'$ drawn along $v_i$. Clearly,one open hemisphere created by $l'$ contains at most $k$ vectors.
   \end{case}

  \begin{case}

  Let us assume that $\overline V \cap \{v_1, v_2, \ldots, v_{k+1}\} \ne \phi$ and $\overline V \cap \{v_{k+2}, v_{k+3}, \ldots, v_{d+2-k}\} \ne \phi$. Let $v_i \in \{v_1, v_2, \ldots, v_{k+1}\} $ is the minimum indexed vector such that $v_i \not \in \overline V$ and  Let $v_j \in \{v_1, v_2, \ldots, v_{k+1}\} $ is the maximum indexed vector such that $v_j \not \in \overline V$. This implies all the vectors in $ \{v_{k+2}, v_{k+3}, \ldots, v_{d+2-k}\} \setminus \overline V$ lie on the right side of the line $-v_{j}$ or on the left side of the line $-v_{i}$. Hence, either a line along $v_i$ or a line along $v_{j}$ creates a open hemisphere of $S^1$ which contains at most $k$ vectors. \qed

\end{case}

\end{proof}
\fi

We obtain an {\textit{affine Gale diagram}} \cite[Page 112]{JM} of $P$ by considering a hyperplane $\bar{h}$ that is not parallel to any vector in $D(P)$ and  not passing through the origin. Since the points in $P$ are in general position in $\mathbb{R}^d$, Lemma \ref{genposi} implies that $g_i \neq 0$ for every $i$. For each $i$ in the range $1\leq i \leq m$, we extend the vector $g_i \in D(P)$ either in the direction of $g_i$ or in its opposite direction until it cuts $\bar{h}$ at the point $\overline {g_i}$.  We color $\overline {g_i}$ as \textit{white} if the projection is in the direction of $g_i$, and \textit{black} otherwise. The sequence of $m$ points $\overline{D(P)}$ $=$ $< \overline {g_1}, \overline {g_2}, \ldots, \overline {g_m}>$ in $\mathbb{R}^{m-d-2}$ along with the color of each point is defined as an affine Gale diagram of $P$. We define a {\textit {partition}} of the points in $\overline{D(P)}$ as two disjoint sets of points $\overline{D^+(P)}$ and $\overline{D^-(P)}$ contained in the opposite open half-spaces created by a hyperplane. Let us restate  Lemma \ref{bjection} using these definitions and notations.
\begin{lemma}\cite{JM}
\label{bjection1}
Consider two integers $u$ and $v$ satisfying $u+v+2 = m$ and $u,v \geq 0$.
If the points in $P$ are in general
position in $\mathbb{R}^d$, there exists a
bijection between the crossing pairs of $u$ and $v$-simplices
in $P$ and the partitions of the points in $\overline{D(P)}$ into $\overline{D^+(P)}$ and $\overline{D^-(P)}$
such that $the ~number~ of~ white$ $points~in~\overline{D^+(P)}$ $plus~the ~number$ $~ of~ black~ points~in$ $\overline{D^-(P)}$ $~is~u+1$ and $the ~number~ of$ $white~ points$ $~in~\overline{D^-(P)}~$ $plus$ $the ~number~ of~ black~ points$ $in~\overline{D^+(P)}~is~ v+1$.
\end{lemma}

\section{Balanced Lines, $j$-Facets and $k$-Sets }
\label{TU1}
In this section, we describe the properties of balanced lines, $j$-facets and $k$-sets that are useful in the proofs of all four theorems.

\vspace{-0.2cm}
\subsection{Balanced Lines}
\noindent Consider a set $R$ containing $r$ points in general position in $\mathbb{R}^2$, such that $\ceil{{r}/{2}}$ points are colored white and $\floor{{r}/{2}}$ points are colored black. Let us state the definitions of a {\textit {balanced line}} and an {\textit {almost balanced line}} of $R$, and discuss their properties that are used in the proof of Theorem \ref{thm4}.\\

\noindent\textbf{Balanced Line:} \cite{PP}  A balanced line $l$ of $R$ is a straight line that passes through a white and a black point in $R$ and the number of black points is equal to the number of white points in each of the open half-spaces created by $l$.\\

\noindent Note that a balanced line exists only when $r$ is even. The following lemma gives a non-trivial lower bound on the number of balanced lines of $R$.

\begin{lemma}\cite{PP}
\label{bline}
When $r$ is even, the number of balanced lines of $R$  is at least $r/2$.
\end{lemma}

\noindent We extend the definition of a balanced line to define an \textit{almost balanced directed line} of $R$.\\

\noindent\textbf{Almost Balanced Directed Line:}    An almost balanced directed line $l$ of $R$ is a directed straight line that passes through a white and a black point in $R$ such that the number of black points is equal to the number of white points in  the positive open half-space created by $l$.\\

\noindent We obtain the following observation from Lemma \ref{bline}.

\begin{observation}
\label{obs:222}
The number of almost balanced directed lines of $R$  is at least $\floor{{r}/{2}}$.
\end{observation}

\vspace{-0.3cm}

\subsection{$j$-Facets and  $k$-Sets}
Consider a set $S$ containing $s$ points in general position in $\mathbb{R}^3$. Let us first state the definitions of  a \textit{$j$-facet} and a \textit{$(\leq j)$-facet} of $S$ for some integer $j \geq 0$. We then state the definitions of a \textit{$k$-set} and a \textit{$(\leq k)$-set} of $S$ for some integer $k \geq 1$, and discuss their properties that are used in the proofs of Theorems \ref{thm1}, \ref{thm2} and \ref{thm3}.  \\

\noindent{\textbf {$j$-facet:}} \cite{ANDR}  A {\textit{$j$-facet}} of $S$ is an oriented $2$-dimensional hyperplane spanned by $3$ points in $S$ such that exactly $j$ points of $S$ lie in the positive open half-space created by it.
\vspace{0.2cm}\\
\noindent  Let us denote the number of $j$-facets of $S$ by $E_{j}$.
\vspace{0.2cm}\\
\noindent{\textbf {$(\leq j)$-facet:}} \cite{ANDR}   A $(\leq j)$-facet of $S$ is an oriented $2$-dimensional hyperplane $h$ spanned by $3$ points in $S$ such that at most $j$ points of $S$ lie in the positive open half-space created by it.\\

\noindent{\textbf {Almost Halving Triangle:}}  An almost halving triangle of $S$ is a $j$-facet of $S$ such that $\left| j - (s-j-3)\right|$ is at most one.\\

\noindent When $s$ is odd, note that an almost halving triangle is a {\textit{halving triangle}} containing an equal number of points in each of the open half-spaces
created by it. The following lemma gives a non-trivial lower bound on the number of halving triangles of $S$. In fact, it is shown in \cite{MS} that this lemma is equivalent to Lemma \ref{bline}.

\begin{lemma}\cite{MS}
\label{HTR}
When $s$ is odd, the number of halving triangles of $S$  is at least $\floor{{s}/{2}}^{2}$.
\end{lemma}

\noindent We obtain the following observation from Lemma \ref{HTR}.
\begin{observation}
\label{obs:htr}
The number of almost halving triangles  of $S$  is at least $\floor{{s}/{2}}^2$.
\end{observation}

\noindent We consider the following lemma which gives a non-trivial lower bound on the number of $(\leq j)$-facets of $S$.
\begin{lemma}\cite{ALCHO}
\label{ALCH}
For $j < {s}/{4}$ , the number of $(\leq j)$-facets of $S$  is at least $4\dbinom{j+3}{3}$.
\end{lemma}

\noindent{\textbf {$k$-Set:}} \cite[page 265]{JM}  A {\textit{$k$-set}} of $S$ is a non-empty subset of $S$ having size $k$ that can be separated from the rest of the points by a $2$-dimensional hyperplane that does not pass through any of the points in $S$.
\vspace{0.2cm}\\
 Let us denote the number of $k$-sets of $S$ by $e_{k}$.\\

\noindent{\textbf {$(\leq k)$-Set:}} \cite{ANDR} A subset $T \subseteq S$ is called a {\textit{$(\leq k)$-set}} if $1 \leq |T| \leq k$ and $T$ can be separated from $S \setminus T$ by a $2$-dimensional hyperplane that does not pass through any of the points in $S$.
\vspace{0.2cm}\\
Andrzejak et. al. \cite{ANDR} gave the following lemma about the relation between the $j$-facets and the $k$-sets of $S$.

\begin{lemma}\cite{ANDR}
\label{AND}
$e_1 = (E_0/2)+2$, $e_{s-1} = (E_{s-3}/2)+2$, and $e_{k} = (E_{k-1}+E_{k-2})/2+2$ for each $k$ in the range $2 \leq k \leq s-2$ .
\end{lemma}

\noindent We obtain the following observation from Observation $2$ and Lemma \ref{AND}.
\begin{observation}
\label{obs101}
There exist  a total of $\Omega(s^2)$  $k$-sets of $S$ such that $min\{k,s-k\}$  is at least $\ceil{(s-1)/2}$.
\end{observation}

\noindent We obtain the following observation from Lemma \ref{ALCH} and  Lemma \ref{AND}.
\begin{observation}
\label{obs100}
The number of $\left(\leq \ceil{{s}/{4}}\right)$-sets of $S$  is at least $\Omega(s^3)$.
\end{observation}

 \iffalse
We obtain the following observation as a  consequence of Observation \ref{obs:22} and \ref{obs:222}.

 \begin{observation}
\label{obs:3}
The number of almost balanced partitions in $S''$  is at least $\floor{n'/2}$.
\end{observation}
\fi
\vspace{-0.5cm}
\section{Improved Lower Bound on  $\overline {cr}_d(K_{2d}^d)$}
\label{imprvcross}

In this section, we first use Observation $1$ to improve the lower bound on  $\overline {cr}_d(K_{2d}^d)$ to  $\Omega (2^d \sqrt{d})$. We then present the proofs of Theorems \ref{thm1}, \ref{thm2} and \ref{thm3}. Note that  $V=\{v_1, v_2, \ldots, v_{2d}\}$ denotes the set of points corresponding to the vertices in a $d$-dimensional rectilinear drawing of  $K_{2d}^d$ and  $E$ denotes the set of $(d-1)$-simplices created by the corresponding hyperedges.\\

\noindent{\textbf{Proof of Theorem \ref{thm4}:}} Consider a set $V'=\{v_1, v_2, \ldots, v_{d+4}\} \subset V$, whose Gale transform $D(V')$ is a set of $d+4$ vectors in $\mathbb{R}^3$. As mentioned before, the vectors in $D(V')$ can be treated as points in $\mathbb{R}^3$. In order to apply the Ham-Sandwich theorem to obtain a proper linear separation of $D(V')$, we keep the origin in a set and all the points in $D(V')$ in another set. The Ham-Sandwich theorem implies that there exists a linear hyperplane $h$ such that each of the open half-spaces created by it contains at most $\floor{{(d+4)}/{2}}$ vectors of $D(V')$. Since the vectors in $D(V')$ are in general position in $\mathbb{R}^3$, note that at most $2$ vectors in $D(V')$ can lie on $h$ and no two vectors in $D(V')$ lie on a line passing through the origin. As a result, it can be easily seen that we can slightly rotate $h$  to obtain a linear hyperplane $h'$ which creates a proper linear separation of $D(V')$. Consider a hyperplane parallel to $h'$ and project the vectors in $D(V')$ on this hyperplane to obtain an affine Gale diagram $\overline{D(V')}$. Note that $\overline{D(V')}$ contains $\floor{{(d+4)}/{2}}$ points of the same  color and $\ceil{{(d+4)}/{2}}$ points of the other color in $\mathbb{R}^2$. Without loss of generality, let us assume that the majority color is white. Also, note that the points in $\overline{D(V')}$ are in general position in $\mathbb{R}^2$.
\vspace{0.2cm}\\
{\normalfont Observation $1$ implies that there exist at least $\floor{{(d+4)}/{2}}$ almost balanced directed lines of  $\overline{D(V')}$. Consider an almost balanced directed line that passes through a white and a black point in $\overline{D(V')}$. Consider the middle point $p$ of the straight line segment connecting  these two points. We  rotate the almost balanced directed line slightly counter-clockwise around $p$ to obtain a partition of $\overline{D(V')}$ by a directed line that does not pass through any point of $\overline{D(V')}$. Note that this partition of $\overline{D(V')}$ corresponds to a unique linear separation of  $D(V')$ having at least $\floor{{(d+2)}/{2}}$ vectors in each of the open half-spaces created by the corresponding linear hyperplane. \iffalse We can rotate each of the $\floor{{(d+4)}/{2}}$ almost balanced directed lines in the above mentioned way to obtain $\floor{{(d+4)}/{2}}$ such partitions in $\overline{D(V')}$. Note that each of  these partitions is unique.\fi This implies that there exist at least $\floor{{(d+4)}/{2}}$ distinct linear separations of $D(V')$ such that each such linear separation contains at least $\floor{{(d+2)}/{2}}$ vectors in each of the open half-spaces created by the corresponding linear hyperplane.  Lemma \ref{bjection} implies that there exists a unique crossing pair of $u$-simplex and $v$-simplex corresponding to each linear separation of $D(V')$, such that $u+v+2=d+4$ and $min\{u+1,v+1\} \geq \floor{{(d+2)}/{2}}$. It follows from Lemma \ref{extension} that each such crossing pair of $u$-simplex and $v$-simplex can be extended to obtain at least $\dbinom{d-4}{d-\floor{(d+2)/2}}= \Omega\left({2^d}/{\sqrt{d}}\right)$ crossing pairs of $(d-1)$-simplices formed by the hyperedges in $E$.  Therefore, the total number of crossing pairs of hyperedges in a $d$-dimensional rectilinear drawing of $K_{2d}^d$ is at least $\floor{{(d+4)}/{2}}\Omega\left({2^d}/{\sqrt{d}}\right)=\Omega \left(2^d \sqrt{d}\right)$}. \qed

\iffalse
\begin{case*}
{\normalfont Since $d+4$ is odd, without loss of generality we assume that the number of white points is one more than the number of black points in $\overline{D(V')}$. We ignore one white point. Let us denote this white point by $w_1$. Consider the point set  $\overline{D(V')} \setminus \{w_1\}$ having  $\floor{(d+4)/2}$ white points and  $\floor{(d+4)/2}$ black points.  Lemma \ref{bline} implies that there exist at least $\floor{\dfrac{d+4}{2}}$ balanced lines in  $\overline{D(V')} \setminus \{w_1\}$. As mentioned in the definition, each balanced line passes through one white point and one black point of  $\overline{D(V')} \setminus \{w_1\}$. As mentioned in $Case~1$, we obtain $\floor{\dfrac{d+4}{2}}$ distinct partitions of points in  $\overline{D(V')} \setminus \{w_1\}$. Let us assume that $w_1$ lies in the larger side in each partition. Note that the partitions remain distinct after adding $w_1$.  Each of these new partition in $\overline{D(V')}$ corresponds to a unique linear separation of vectors in $D(V')$ having at least $\floor{(d+2)/2}$ vectors in each of its open half-spaces created by the corresponding linear hyperplane.  Lemma \ref{bjection} implies that there exists a unique crossing pair of $u$-simplex and $v$-simplex corresponding to each linear separation of $D(V')$, such that $u+v+2=d+4$ and $min\{u+1,v+1\} \geq \floor{(d+2)/2}$. It follows from Lemma \ref{extension} that each such crossing pair of $u$-simplex and $v$-simplex can be extended to obtain at least $\dbinom{d-4}{d-\floor{(d+2)/2}}= \Omega\left(\dfrac{2^d}{\sqrt{d}}\right)$ crossing pairs of $(d-1)$-simplices formed by the hyperedges in $E$.  Therefore, the total number of crossing pairs of hyperedges in such a $d$-dimensional rectilinear drawing of $K_{2d}^d$ is at least $\floor{\dfrac{d+4}{2}}\times\Omega\left(\dfrac{2^d}{\sqrt{d}}\right)=\Omega \left(2^d \sqrt{d}\right)$}. \qed
\end{case*}
\fi
\noindent{\textbf{Proof of Theorem \ref{thm1}:}}
 Since the points in $V$ are not in  convex position in $\mathbb{R}^d$, we assume  without loss of generality that $v_{d+2}$ can be expressed as a convex combination of the points in $V \setminus \{v_{d+2}\}$. The Carath\'{e}odory's theorem implies that $v_{d+2}$  can be expressed as a convex combination of $d+1$ points in $V \setminus \{v_{d+2}\}$. Without loss of generality, we assume these $d+1$ points to be $\{v_1, v_2, \ldots, v_{d+1}\}$. \par
Consider the set of points $V'=\{v_1, v_2, \ldots,  v_{d+5}\} \subset V$. Note that a Gale transform $D(V')$ of it is a collection of $d+5$ vectors in $\mathbb{R}^4$. Lemma \ref{convexity} implies that there exists a linear hyperplane $h$ that partitions $D(V')$ in such a way that one of the open half-spaces created by $h$ contains exactly one vector of $D(V')$. Since the points in $V'$ are in general position in $\mathbb{R}^4$, Lemma \ref{genposi} implies that at most three vectors of $D(V')$  lie on $h$. Since the vectors in $D(V')$ are in general position, it can be easily seen that we can slightly rotate $h$  to obtain a linear hyperplane $h'$ that partitions $D(V')$ such that one of the open half-spaces created by $h'$ contains $d+4$ vectors and the other one contains exactly one vector. \par
 Consider a hyperplane parallel to $h'$.  We project the vectors in $D(V')$ on this hyperplane to obtain an affine Gale diagram $\overline{D(V')}$. Note that $\overline{D(V')}$ contains $d+4$ points of the same  color and one point of the other color in $\mathbb{R}^3$. Without loss of generality, let us assume that the majority color is white. Also, note that the points in $\overline{D(V')}$ are in general position in $\mathbb{R}^3$ since the corresponding vectors in the Gale transform $D(V')$ are in general position in $\mathbb{R}^4$.\par
 Consider the set $W$ containing $d+4$ white points of $\overline{D(V')}$ in $\mathbb{R}^3$.  Observation $3$ implies that there exist at least $\Omega(d^2)$ distinct $k$-sets of $W$ such that $min\{k,d+4-k\}$  is at least $\ceil{{(d+3)}/{2}}$. Each of these $k$-sets corresponds to a unique linear separation of  $D(V')$ having at least $\ceil{{(d+3)}/{2}}$ vectors in each of the open half-spaces created by the corresponding linear hyperplane. Lemma \ref{bjection} implies that there exists a unique crossing pair of $u$-simplex and $v$-simplex corresponding to each of these linear separations of  $D(V')$, such that $u+v+2=d+5$ and $min\{u+1,v+1\} \geq \ceil{({d+3})/{2}}$. It follows from Lemma \ref{extension} that each such crossing pair of $u$-simplex and $v$-simplex can be extended to obtain at least $\test{d-5}{d-\ceil{(d+3)/{2}}}$ crossing pairs of $(d-1)$-simplices formed by the hyperedges in $E$. Therefore, the total number of crossing pairs of hyperedges in such a $d$-dimensional rectilinear drawing of $K_{2d}^d$  is at least $\Omega(d^2)\test{d-5}{d-\ceil{({d+3})/{2}}}=\Omega\left(2^d{d}^{3/2}\right).$ \qed
\vspace{0.4cm}
\noindent{\textbf{Proof of Theorem \ref{thm2}:}}
Consider the points in $V$ that form the vertex set of a $d$-dimensional $t$-neighborly polytope which is not $(t+1)$-neighborly. Lemma \ref{neigh} implies that there exists a linear hyperplane $\widetilde{h}$ such that one of the open half-spaces created by it contains $t+1$ vectors. Without loss of generality, we denote the set of these $t+1$ vectors by $D^+(V)$.  It implies that one of the closed half-spaces created by $\widetilde{h}$ contains  $2d-t-1$ vectors of $D(V)$. If $d-2$ vectors of $D(V)$ do not lie on $\widetilde{h}$, we rotate $\widetilde{h}$ around the lower dimensional hyperplane spanned by the vectors on $\widetilde{h}$ till some new vector $g_i \in D(V)$ lies on it. We keep rotating $\widetilde{h}$ in this way till $d-2$ vectors of D(V) lie on it.  Lemma \ref{neigh} implies that none of these $d-2$ vectors belongs to the set $D^+(V)$.  After rotating $\widetilde{h}$ in the above mentioned way, we obtain a partition of  $D(V)$ by a linear hyperplane $\widetilde{h'}$ such that one of the open half-spaces created by it contains $t+1$ vectors and the other one contains $d+1-t$ vectors.  This implies that there exist a $t$-simplex and a $(d-t)$-simplex created by the vertices in $V$ such that they form a crossing. We choose any three vertices from the rest of  the $d-2$ vertices in $V$ and add these to the $(d-t)$-simplex to form a $(d+3-t)$-simplex. Lemma \ref{extension} implies that  the $t$-simplex forms a crossing with this $(d+3-t)$-simplex. This implies that the  $t$-neighborly sub-polytope formed by the convex hull of the $d+5$ vertices corresponding to these two simplices is  not $(t+1)$-neighborly.\\
\indent ~~Without loss of generality, let the vertex set of this sub-polytope be $V'=\{v_1, v_2,$  $\ldots, v_{d+5}\}$. Note that a Gale transform $D(V')$ of it is a collection of $d+5$ vectors in $\mathbb{R}^4$. Lemma \ref{neigh} implies that there exists a  linear hyperplane $h$ such that one of the open half-spaces created by it contains exactly $t+1$ vectors of $D(V')$. As described in the proof of Theorem \ref{thm1}, it follows from Lemma \ref{genposi} that at most $3$ vectors can lie on $h$. Since the vectors in $D(V')$ are in general position, we can slightly rotate $h$ to obtain a linear hyperplane $h'$ such that one of the open half-spaces created by $h'$ contains $t+1$ vectors and the other one contains $d+4-t$ vectors.\\
 \indent Consider a hyperplane parallel to $h'$ and project the vectors in $D(V')$ on this hyperplane to obtain an affine Gale diagram $\overline{D(V')}$. Note that $\overline{D(V')}$ contains $d+4-t$ points of the same  color and $t+1$ points of the other color in $\mathbb{R}^3$. Without loss of generality, let us assume that these d+4-t points of the same color are white. Also, note that the points in $\overline{D(V')}$ are in general position in $\mathbb{R}^3$.\\
\indent Let us consider the set $W$ consisting of $d+4-t$ white points of $\overline{D(V')}$. Observation $3$ implies that there exist at least $\Omega(d^2)$ distinct $k$-sets of $W$ such that $min\{k,d+4-t-k\}$  is at least $\ceil{({d+3-t})/{2}}$. Each of these $k$-sets corresponds to a unique linear separation of  $D(V')$ such that it contains at least $\ceil{{(d+3-t)}/{2}}$ vectors in each of the open half-spaces created by the corresponding linear hyperplane. Lemma \ref{bjection} implies that there exists a unique crossing pair of $u$-simplex and $v$-simplex corresponding to each of these linear separations of  $D(V')$, such that $u+v+2=d+5$ and $min\{u+1,v+1\} \geq$ ${\scriptstyle \ceil{{(d+3-t)}/{2}}}$. It follows from Lemma \ref{extension} that each such crossing pair of $u$-simplex and $v$-simplex can be extended to obtain at least $\test{d-5}{d-\ceil{{(d+3-t)}/{2}}}$ crossing pairs of $(d-1)$-simplices formed by the hyperedges in $E$. Therefore, the total number of crossing pairs of hyperedges in such a $d$-dimensional rectilinear drawing of $K_{2d}^d$  is at least $\Omega(d^2)\test{d-5}{d-\ceil{{(d+3-t)}/{2}}}=\Omega\left(2^d{d}^{3/2}\right).$ \qed
\vspace{0.2cm}

\noindent{\textbf{Proof of Theorem \ref{thm3}:}}
Since the points in $V$ form the vertex set of a $d$-dimensional $(\floor{d/2}-t')$-neighborly polytope, consider the sub-polytope of it having the vertex set $V'=\{v_1, v_2, \ldots, v_{d+5}\}$. Note that a Gale transform $D(V')$ of it is a collection of $d+5$ vectors in $\mathbb{R}^4$ and an affine Gale diagram $\overline{D(V')}$ of it  is a collection of $d+5$ points in $\mathbb{R}^3$. In this proof, we ignore the colors of these points. However, note that the points in $\overline{D(V')}$ are in general position in $\mathbb{R}^3$.\par
 Consider the set $\overline{D(V')}$.  It follows from Observation $4$ that the number of $\left(\leq\ceil{{(d+5)}/{4}}\right)$-sets of $\overline{D(V')}$ is $\Omega(d^3)$.  For each $k$ in the range $ 1\leq k \leq$ ${\scriptstyle \ceil{{(d+5)}/{4}}}$, a $k$-set of $\overline{D(V')}$  corresponds to a unique linear separation of  $D(V')$.  Lemma \ref{neigh} implies that each of these $\Omega(d^3)$ linear separations of $D(V')$ contains at least $\floor{d/2}-t'+1$ vectors in each of the open half-spaces created by the corresponding linear hyperplane. Lemma \ref{bjection} implies that there exists a unique crossing pair of $u$-simplex and $v$-simplex corresponding to each linear separation of $D(V')$, such that $u+v+2=d+5$ and $min\{u+1,v+1\} \geq \floor{d/2}-t'+1$. It follows from Lemma \ref{extension} that each such crossing pair of $u$-simplex and $v$-simplex can be extended to obtain at least $\dbinom{d-5}{d-\floor{d/2}+t'-1}= \Omega\left({2^d}/{\sqrt{d}}\right)$ crossing pairs of $(d-1)$-simplices formed by the hyperedges in $E$.  Therefore, the total number of crossing pairs of hyperedges in such a $d$-dimensional rectilinear drawing of $K_{2d}^d$ is at least $\Omega(d^3)\Omega\left({2^d}/{\sqrt{d}}\right)=\Omega \left(2^d d^{5/2}\right)$. \qed
\iffalse
\vspace{0.2 cm}
Consider a  sequence of points $P=<p_1,p_2, \ldots, p_n>$ having $n>d+1$ points in general position in $\mathbb{R}^d$. Let the coordinate of point $p_i$ is $(a_1^i, a_2^i, \ldots, a_d^i)$ Consider a subsequence $P'=<p_{i_1}, p_{i_2}, \ldots p_{i_{d+1}}>$ which follows the same precedence order of $P$ among the points. Consider the following determinant $D_{p'}$.
\[
D_{p'} =
\begin{vmatrix}
1 & 1 &  \ldots & 1\\
a_1^{i_1} & a_1^{i_2} & \ldots & a_1^{i_d} \\implies
\vdots & \vdots & \vdots & \vdots\\
a_d^{i_1} & a_d^{i_2} & \ldots & a_d^{i_d} \\
\end{vmatrix}
\]
Since the points are in general position, $D_{p'} \ne 0$. $P$ is said to be order type homogeneous, if for every $d+1$ length subsequence $P'$ of $P$, $D_{p'}$ has same sign.
A special type of $d$-dimensional neighborly polytope is the polytope which is combinatorially equivalent to a cyclic polytope. Strumfels \cite{STR} proved that, for even $d$, vertex set of any $d$-polytope which is combinatorially equivalent to a cyclic polytope can be arranged in a  order type  homogeneous sequence. As already mentioned the number of crossing pairs of hyperedges of   $K_{2d}^d$ is $\Theta\left(4^d /\sqrt{d}\right)$ when all the $2d$-vertices of $K_{2d}^d$ are placed on a $d$-dimensional moment curve. This result along with the result of Strumfels prove that, for even d, the number of crossing pairs of hyperedges of   $K_{2d}^d$ is $\Theta\left(4^d /\sqrt{d}\right)$, if the vertices of $K_{2d}^d$ are placed as the vertices of a $d$-dimensional polytope which is combinatorially equivalent to a cyclic polytope.
\fi
\iffalse
\vspace{-0.5cm}
\section{Concluding Remarks}
\label{CR}

In this paper, we proved that the number of crossing pairs of hyperedges of $K_{2d}^d$ is $\Omega (2^d \sqrt{d})$, when the vertices of $K_{2d}^d$ are placed either in a) the position in $\mathbb{R}^d$, or  b) as the vertices of $t$-neighborly $d$-polytope, for some constant $k$ independent of $d$. We also proved that  the number of crossing pairs of hyperedges of $K_{2d}^d$ is $\Omega (2^d d^{3/2})$, if the vertices of $K_{2d}^d$ are placed as the vertices of $(\floor{d/2}-k)$-neighborly $d$-polytope for some constant $k$ independent of $d$. We already mentioned that $\overline {cr}_d(K_{2d}^d)= \Omega (2^d)$. Based on this results, we conjecture the following.

\begin{conjecture}
\label{cnj1}
 $\overline {cr}_d(K_{2d}^d)= \Omega (2^d \sqrt{d})$.
\end{conjecture}
\fi

\iffalse
\begin{lemma} \cite{AS}
\label{coloring}
Consider a subset $V'=\{v_1, v_2, \ldots, v_{d+4}\} \subset V$ having $d+4$ points. The Gale transform $D(V')$ is a set of $d+4$ vectors in $\mathbb{R}^3$. There exist at least $\Omega(\log d)$ proper linear separations of  $D(V')$.
\end{lemma}
\begin{proof}
$D(V')=\{g_1,g_2, \ldots, g_{d+4}\}$ is a collection of $d+4$ vectors in $\mathbb{R}^3$. As already mentioned, the vectors in $D(V')$ can be treated as points in $\mathbb{R}^3$. We use the Ham-sandwich theorem to obtain the proper linear separations of $D(V')$. Since the points in $D(V')$ are in $\mathbb{R}^3$, we use three colors $c_0$,$c_1$ and $c_2$.  The coloring argument proceeds as following. \\

We color the origin with $c_0$ and all the points in $D(V')$ with  $c_1$. The color of the origin remains unchanged throughout the process. By the Ham-sandwich theorem and rotating the separating hyperplane if needed (as mentioned before), we obtain a proper linear separation of $D(V')$ into $D_{11}(V')$ and $D_{12}(V')$ having $\floor{(d+4)/2}$ and $\ceil{(d+4)/2}$ vectors, respectively.  We then color all the vectors in $D_{11}(V')$ with $c_1$ and all the vectors in $D_{12}(V')$ with $c_2$. The Ham-Sandwich theorem implies that we obtain a partition $D_{21}(V')$ and $D_{22}(V')$ of $D(V')$. Note that at least $\floor{(d+4)/4}$ points of $D(V')$ have stayed together in both the partitions. Next, we color these  $\floor{(d+4)/4}$ points in $D(V')$ with $c_1$ and rest of the points with $c_2$ to  obtain a new proper linear separation of $D(V')$ in two partitions $D_{31}(V')$ and $D_{32}(V')$. Note that $\floor{(d+4)/8}$ points of $D(V')$ have stayed together in all three proper linear separations. In particular, in the $k^{th}$ step we obtain a proper linear separation of $D(V')$ into $D_{k1}(V')$ and $D_{k2}(V')$. Note that the $k^{th}$ proper linear separation of $D(V')$ is distinct from all the $k-1$ proper linear separations obtained before. It is easy to observe that $\floor{(d+4)/2^k}$ points of $D(V')$ have stayed together in all the $k$ proper linear separations obtained so far. We then color these  $\floor{(d+4)/2^k}$ points of $D(V')$ with $c_1$ and rest of the points with $c_2$ to obtain the ${k+1}^{th}$ proper linear separation of $D(V')$. We keep on coloring in this way till a pair of points stays together. This implies that we can keep on coloring for $\Omega(\log d)$ times without repeating any of the previous proper linear separations of $D(V')$.
\end{proof}
 \begin{lemma}
 $\overline {cr}_d(K_{2d}^d) =\Omega (2^d \sqrt{\log d})$.
 \end{lemma}
\begin{proof}
Consider a subset $V'=\{v_1, v_2, \ldots, v_{d+4}\} \subset V$ having $d+4$ points. The Gale transform $D(V')$ is a set of $d+4$ vectors in $\mathbb{R}^3$. We apply the Ham-sandwich theorem to obtain $\Omega(\log d)$ proper linear separations of  $D(V')$ as mentioned in Lemma \ref{coloring}. Let us denote the $i^{th}$ proper linear separation by $PL_i$. Consider an affine Gale diagram $\overline{D(V')}$. Let us ignore the color of the points in $\overline{D(V')}$. Note that the $i^{th}$ proper linear separation of $D(V')$ $PL_i$ corresponds to a $k_i$-set of $\overline{D(V')}$ for some $k_i$ satisfying $1 \leq k_i \leq d+3$. For each of this $k_i$-set, we can obtain distinct $(k_i-1)$-edge in  $\overline{D(V')}$ as mentioned in the proof of Observation \ref{obs:22} and we denote the $(k_i-1)$-edge by $L_i^0$. Note that each $L_i^0$ is a directed line passing through the two points of $\overline{D(V')}$. We collect all the distinct endpoints of these lines. To span these $\Omega(\log d)$ lines, we need at least $\Omega(\sqrt{\log d})$ points of $\overline{D(V')}$. Let $\overline{D(V'')}= \{ \overline {g_{i_1}}, \overline {g_{i_2}}, \ldots, \overline {g_{i_{\sqrt{\log d}}}} \} \subset \overline{D(V')}$  denotes the set of these points. Consider the line $L_1^0$. Without the loss of generality,  let us assume that it is a directed line from $\overline {g_{i_1}}$ to $\overline {g_{i_2}}$ . We rotate the line $L_1^0$ counter clockwise as mentioned in the proof of Observation \ref{obs:22} to obtain the line $L_1^0(0)$. Note that $L_1^0(0)$ does not contain any point of  $\overline{D(V')}$. We get a partition of the points in $\overline{D(V')}$ by $L_1^0(0)$. This partition corresponds to a linear separation of vectors in $D(V')$ such that each of the open half-spaces contain at least $\floor{(d+1)/2}$ vectors. We now rotate $L_1^0$ counter-clockwise with respect to $\overline {g_{i_1}}$ until it meets the second point and let us denote this line by $L_1^1$. We then rotate the line $L_1^1$ counter clockwise as mentioned in the proof of Observation \ref{obs:22} to obtain the line $L_1^1(0)$. Note that $L_1^1(0)$ does not contain any point of  $\overline{D(V')}$. We get a partition of the points in $\overline{D(V')}$ by $L_1^1(0)$. This partition corresponds to a linear separation of vectors in $D(V')$. We now rotate $L_1^1$ counter-clockwise with respect to $\overline {g_{i_1}}$ until it meets the next point and let us denote this line by $L_1^2$. In general, we rotate $L_1^j$ counter clockwise as mentioned in the proof of Observation \ref{obs:22} to obtain a partition of points in $\overline{D(V')}$ created by the line $L_1^j(0)$.  This separation of points in  $\overline{D(V')}$ corresponds to a linear separation of vectors in $\overline{D(V')}$.  We then rotate $L_1^j$  with respect to ${g_{i_1}}$ until it meets the next point to obtain the line by $L_1^{j+1}$. Note that we can keep on rotating like this until all the points in $\overline{D(V')}\setminus \{g_{i_1}\}$ are covered. Note that we obtain $d+3$ distinct proper linear separations while rotating the line with respect to ${g_{i_1}}$. Let us denote the linear separation of $D(V')$ corresponds to the line $L_1^j(0)$ by $\{D_j^+(V'), D_j^-(V')\}$. Note that $\left|\left|D_j^+(V')\right|-\left|D_{j+1}^+(V')\right| \right| \leq 4$ for $j$ satisfying $0 \leq j \leq d+2$. Each of these proper linear separations corresponds to distinct crossing pair of $u$-simplex and $v$-simplex where $u+v=d+2$ and $1\leq u,v \leq d-1$. It follows from Lemma \ref{extension} that each such crossing pair of $u$-simplex and $v$-simplex can be extended to obtain at least $\dbinom{d-4}{d-u-1}$ crossing pairs of $(d-1)$-simplices formed by the hyperedges in $E$. The total number of crossing pairs of hyperedges obtained in this way is at least  $\dbinom{d-4}{d-\floor{(d+1)/2}}+ \dbinom{d-4}{d-\floor{d+1/2}-4}+ \ldots+ \dbinom{d-4}{d-4}= \Omega(2^d)$. For each of the points in $\overline{D(V'')}$, we obtain $\Omega(2^d)$ crossing pairs of hyperedges in a similar way. Note that Observation \ref{obs:22} implies that any partition of points in $\overline{D(V')}$ obtained during the rotation with respect to $\overline {g_{i_j}} \in \overline{D(V'')}$ is distinct from the any other partition of points in $\overline{D(V')}$ obtained during the rotation with respect to $\overline {g_{i_k}} \in \overline{D(V'')}\setminus \{\overline{g_{i_j}}\}$. This implies that  for each of the points in $\overline{D(V'')}$, we obtain $\Omega(2^d)$ distinct crossing pairs of hyperedges. This proves that $\overline {cr}_d(K_{2d}^d)= \Omega (2^d \sqrt{\log d})$.
\end{proof}
\fi

\vspace{-0.2cm}

config: arxiv


TITLE: Cartesian products and sets
QUESTION [1 upvotes]: I'm really confused on how to approach this question:

Recall that the Cartesian product $A \times A$ is defined as the set $\{(x, y) : x \in A \land y \in A \}$. Thus if for example $A = \{1, 2, 3\}$, $$A \times A = \{(1, 1),(1, 2),(1, 3),(2, 1),(2, 2),(2, 3),(3, 1),(3, 2),(3, 3)\}\;.$$
  Consider a set $A \ne \varnothing$ where the number $|A|$ of elements of $A$ is $20$ less than the number $|A\times A|$ of elements in $A\times A$. Thus $|A| + 20 = |A\times A|$. Determine the number of elements in $A$.

Thank you in advance!

REPLY [2 votes]: How many elements are in $|A\times A|$ in terms of $n=|A|$? Plug this in and you'll have an equation to solve in terms of $n$.
Hint: Imagine a table where both rows and columns are indexed by elements of the set $A$. In each component of the table - namely the row indexed by $a\in A$ and $b\in A$ we can put $(a,b)\in A\times A$, thus giving a full listing of all of the elements of the Cartesian product.

REPLY [1 votes]: Look at an example. Suppose that $A=\{1,2,3,4,5\}$. Then the members of $A\times A$ are:
$$\begin{array}{r|cc}
&1&2&3&4&5\\ \hline
1&(1,1)&(1,2)&(1,3)&(1,4)&(1,5)\\
2&(2,1)&(2,2)&(2,3)&(2,4)&(2,5)\\
3&(3,1)&(3,2)&(3,3)&(3,4)&(3,5)\\
4&(4,1)&(4,2)&(4,3)&(4,4)&(4,5)\\
5&(5,1)&(5,2)&(5,3)&(5,4)&(5,5)
\end{array}$$
Clearly $|A\times A|=5\cdot 5=25$. What happens in general? What is $|A\times A|$ in terms of $|A|$?
For future use, you should probably think about how $|A\times B|$ is determined by $|A|$ and $|B|$. You can use the same geometric idea. For instance, if $B=\{1,2,3\}$, with $A$ as in the previous example, the members of $A\times B$ are:
$$\begin{array}{r|cc}
&1&2&3\\ \hline
1&(1,1)&(1,2)&(1,3)\\
2&(2,1)&(2,2)&(2,3)\\
3&(3,1)&(3,2)&(3,3)\\
4&(4,1)&(4,2)&(4,3)\\
5&(5,1)&(5,2)&(5,3)
\end{array}$$
Clearly there are $5\cdot 3=15$ of them. What happens in general?

REPLY [0 votes]: The number of elements in A is 5.
|A X A| = |A|.|A|

|A| + 20 = |A X A|
|A| + 20 = |A|.|A|

and solve this equation. you will get answer.


TITLE: I dropped mathematics and want to self-teach it to myself starting from the basics
QUESTION [3 upvotes]: I will make this question as objective based as possible. My curriculum teaches maths in a way that does not work well with me. Further, I also do not like the textbooks used (It was voted the worst in the state). The only way to succeed in this course was to get a tutor, objectively speaking. The highest non-tutor mark was about 60%~, majority severely failed the exam. I dropped the course as a whole.
In lieu of this, I still have a passion for mathematics. Currently, I just begin Calculus, but I am missing a solid development in all pre-calculus topics.
By solid development, I mean I have no intuitive way of grasping things - just stuff and methods rote learned from formulas provided.
I need a good textbook, and that is my question here, that provides a solid, rigorous, theory intensive approach to mathematics from all pre-calculus topics to beyond.
I don't mind if its multiple book recommendations in order, I am willing to study them hard.
Much thanks. I'm sure someone on this site has exactly what I'm looking for and am hoping they can share it with me.

REPLY [1 votes]: Calculus and Analytic Geometry by George B. Thomas and  Ross L. Finney. This is a great book for self learning, it balances clear explanations with enough rigor and will help you gain some intuition from the basics all the way to the multivariate integral theorems.