On the number of vertices of projective polytopes
Let $X$ be a configuration of $n$ points in $\mathbb{R}^d$.What is the maximum number of vertices that $conv(T(X))$ can have among all the possible permissible projective transformations $T$?In this paper, we investigate this and connected questions. After presenting several upper bounds, we study a closely related problem (via Gale transforms) concerning the number of minimal Radon partitions of a set of points. We then present some bounds for this number that enable us to partially answer a question due to Pach and Szegedy. We also discuss another related problem concerning the size of topes in arrangements of hyperplanes.
\section{Introduction}

We consider the following question

\begin{quote}
Given a set of $n$ points in general position $X \subset \mathbb R^d$, what is the maximum number of $k$-faces that $conv(T(X))$ can have among all the possible {\em permissible projective transformations} $T$?
\end{quote}

More precisely, recall that a \emph{projective transformation} $T:\mathbb{R}^{d} \rightarrow \mathbb{R}^{d}$ is a function such that $T(x)=\frac{Ax+b}{\langle c,x \rangle + \delta}$, where $A$ is a linear transformation of $\mathbb{R}^{d}$, $b, c \in \mathbb{R}^{d}$ and $\delta \in \mathbb{R},$ is such that at least one of $c\neq 0$ or $\delta \neq 0.$  $T$ is said to be \emph{permissible} for a set $X\subset \mathbb{R}^{d}$ if and only if  $\langle c,x \rangle + \delta \neq 0$ for all $x\in X$.

Let $d\ge k\ge 0$ be integers and let $X$ be a set of points in $\mathbb R^d$, we define
\begin{equation}\label{eq:def-h}
h_X(d,k)= \max\limits_T \left\{f_k(conv(T(X)))\right\}
\end{equation}
maximum taken over all possible permissible projective transformations $T$ of $X$ and where $f_k(P)$ denotes the number of $k$-faces in the polytope $P$.

We consider the function $H_k(n,d)$ defined as,
$$H_k(n,d)=\min\limits_{X \subset \mathbb R^d, |X|=n}\left\{h_X(d,k)\right\}.$$



In this paper, we focus our attention to the values of $H_{0}(n,d),$ and $H_{d-1}(n,d)$.
These are closely related and they are natural generalizations of the well-known McMullen's problem  \cite{LARMAN72}:

\emph{What is the largest integer $\nu(d)$ such that any set of $\nu(d)$ points in general position, $X \subset \mathbb R^{d},$ can de mapped by a permissible projective transformation onto the vertices of a convex polytope?}

The best known bounds are
 \begin{equation}\label{eq:boundsmcmullen}
 2d+1 \leq \nu(d) < 2d + \left\lceil \frac{d+1}{2} \right\rceil.
 \end{equation}

The lower bound was given by Larman \cite{LARMAN72} while the upper bound was provided by Ramirez Alfonsin \cite{RAMIREZALFONSIN2001}.
In the same spirit, the following function has also been investigated:

\begin{quote}
$\nu(d,k):=$ the largest integer such that any set of $\nu(d,k)$ points in general position in $\mathbb R^d$ can be mapped, by a permissible projective transformation onto the vertices of a $k$--neighbourly polytope.
\end{quote}

Garc\'{i}a-Col\'{i}n \cite{NGC2015} proved that, for  each $2 \leq k \leq \left\lfloor \frac{d}{2}\right\rfloor$
 \begin{equation}\label{eq:boundsmcmullengen}
 d + \left\lceil \frac{d}{k} \right\rceil +1 \leq \nu(d, k) < 2d-k+1.
 \end{equation}


We now define the following closely related function, which will be useful to study $H_{0}(n,d).$ Let $t\ge 0$ be an integer, we define

\begin{quote}
$n(d,t):=$ the largest integer such that any set of $n(d,t)$  points in general position in $\mathbb R^d$ can be mapped, by a permissible projective transformation onto the vertices of a convex polytope with at most $t$ points in its interior.
\end{quote}

\begin{remark}\label{relationf_0andn(d,t)}
The functions $\nu(d),$ $\nu(d,k)$ and $n(d,t)$ are closely related to $H_0(n(d,t),d),$ in particular:
\begin{enumerate}[(a)]
\item $n(d,0)=\nu(d)$ where $\nu(d)$ is the desired maximum value in McMullen's problem
\item $H_0(n(d,t),d)=n(d,t)-t$.
\end{enumerate}

\end{remark}

The function $n(d,t)$ will allows us to study $H_0(n,d)$ in a more general setting in terms of oriented matroids. Our main contribution is the following results:

\begin{theorem}\label{boundsforf_o} Let $d,l$ and $n$ be integers. Then,
{\scriptsize $$H_0(n,d)\left\{\begin{array}{ll}
=2 & \text{ if } d=1,\ n\ge 2,\\
=5 & \text{ if } d=2, \  n\ge 5, \\
\le 7 & \text{ if } d=3, \ n\ge 7,\\
=n & \text{ if } d\ge 2, \ n\le 2d+1,\\
\le n-1& \text{ if } d\ge 4, \ n\ge 2d+\lceil\frac{d+1}{2}\rceil,\\
\le n-2 & \text{ if } d\ge 4, \ n\ge  2d+\lceil\frac{d+1}{2}\rceil+1,\\
\le n-(l+2) & \text{ if } d\ge 4, \ {2d+3+l(d-2) \leq n < 2d+3+(l+1)(d-2)}, \ l\ge 1.\\
\end{array}\right.$$}
\end{theorem}

\begin{theorem}\label{boundsforf_d-1} Let $d,l$ and $n$ be integers. Then,
{\scriptsize $$H_{d-1}(n,d)\left\{\begin{array}{ll}
=2 & \text{ if } d=1, \ n\ge 2,\\
=5 & \text{ if } d=2, \ n\ge 5, \\
\le 10 & \text{ if } d=3, \ n\ge 7,\\
\le f_{d-1}(C_d(n)) & \text{ if } d\ge 2, \ n\le 2d+1,\\
\le f_{d-1}(C_d(n-1))& \text{ if } d\ge 4, \ n\ge 2d+\lceil\frac{d+1}{2}\rceil,\\
\le f_{d-1}(C_d(n-2)) & \text{ if } d\ge 4, \ n\ge  2d+\lceil\frac{d+1}{2}\rceil+1,\\
\le f_{d-1}(C_d(n-l-2)) & \text{ if } d\ge 4, \ {2d+3+l(d-2) \leq n < 2d+3+(l+1)(d-2)}, \ l\ge 1.\\
\end{array}\right.$$}
where $C_d(n)$ denotes the $d$--dimensional {\em cyclic polytope} with $n$ vertices. Moreover, 
$H_{d-1}(n,d)\ge n(d-1)-(d+1)(d-2)$ when $d\ge 2,  n\le 2d+1$.

\end{theorem}

In the next section, we give some straightforward values and bounds. In Section \ref{sec:lawrence}, we discuss the aforementioned oriented matroid setting and recall some notions and results on the special class of {\em Lawrence oriented matroids} needed for the rest of the paper. In Section \ref{cotassupmatroides}, we prove our main results.  In Section \ref{sec:arrangements}, we discuss the following interpretation of $H_{0}(n,d)$ in terms of arrangements of (pseudo)hyperplanes:

\begin{quote}
What is the maximum size that a {\em tope} in \underline{any} given simple arrangement of $n$ (pseudo) hyperplanes in $\mathbb{P}^d$ can have?
\end{quote}

The latter is closely related to the so-called Las Vergnas' conjecture and yields to further bounds for $H_0(n,d)$ (Proposition \ref{lowerboundvd=2}).

In Section \ref{sec:anapplication}, we shall provide an answer to  the following question due to Pach and Szegedy \cite{PACH2003}:

\begin{question}\label{question:ps} Given $n$ points in general position in the plane, colored red and blue, maximize the number of multicolored 4-tuples with the property that the convex hull of its red elements and the convex hull of its blue elements have at least one point in common. In particular, show that when the maximum is attained, the number of red and blue elements are roughly the same.
\end{question}

We will first present a connection between $H_{d-1}(n,d)$ and the notion of {\em minimal Radon partitions} by using the relationship between {\em Gale transforms} and projective transformations (Theorem \ref{lem:radon}).  The latter induces an upper bound for the number of minimal Radon partitions (i.e $(d+2)$--tuples) induced by a red/blue partition of a set of $n$ points in general position in $\mathbb{R}^d$. We then show that attaining the maximum does not depend on the number of red/blue points, but on the projective class of the configuration (Theorem \ref{thm:unbalanced}).

We end by discussing some questions and open problems.

\section{Some basic results}\label{sec:basic}

The well-known Upper Bound Theorem  \cite{MCMULLEN1971187} states that $f_{k-1}(P) \leq f_{k-1}(C_d(n))$ for all $1\leq k \leq d$ among all simplicial (convex) polytopes $P \subset \mathbb R^d$ with $n$ vertices where $C_d(n)$ is the $d$--dimensional {\em cyclic polytope} with $n$ vertices, that is, a polytope formed as a convex hull of $n$ distinct points in the moment curve $x(t):=(t,t^2,\dots ,t^d)$.

A natural upper bound for $H_{d-1}(n,d)$ is thus given by
\begin{equation}\label{eq:upperbound}
H_{d-1}(n,d) \leq f_{d-1}(C_{d}(n)) \text{ for all } n\ge 1.
\end{equation}

Analogously,  the Lower Bound Theorem  \cite{BARNETTE1973, BILLERA1981} states that $f_k(P)\ge f_k(P_d(n))$ for all $1\leq k \le d-1$ among all simplicial (convex) polytopes $P \subset \mathbb R^d$ with $n$ vertices,  where $P_d(n)$ is a $d$-dimensional {\em stacked polytope} with $n$ vertices, that is, a polytope formed from a simplex by repeatedly gluing another simplex onto one of its facets. We thus have
\begin{equation}\label{eqn:lowerbound2}
f_{d-1}(P_d(n))\le H_{d-1}(n,d)
\end{equation}
Moreover, we may deduce that
\begin{equation}\label{upperboundcyclicp}
f_{d-1}(P_d(H_0(n,d)))\leq H_{d-1}(n,d)\leq f_{d-1}(C_d(H_0(n,d))).
\end{equation}

\begin{proposition}\label{easybounds} Let $d,n\ge 1$ be integers. Then,
$$H_0(n,d)\left\{\begin{array}{ll}
=n & \text{ if } n\le 2d+1,\\
<n & \text{ if } n \ge 2d+\lceil\frac{d+1}{2}\rceil,\\
=n & \text{ if } d \text{ is even and } n\le d+3,\\
=n & \text{ if } d \text{ is odd and } n\le d+4.\\
\end{array}\right.$$
\end{proposition}

\begin{proof} Let $n \leq 2d+1$. By the lower bound of $\nu(d)$ given in  \eqref{eq:boundsmcmullen}, it follows that any set of points of cardinality $n$ can be mapped to the vertices of a convex polytope by a permissible projective transformations, therefore $H_{0}(n,d)=n$. If $n \ge 2d + \lceil \frac{d+1}{2} \rceil$ then by the upper bound of $\nu(d)$ given in \eqref{eq:boundsmcmullen},  there exist a set of $n$ points such that cannot be mapped to the vertices of a convex polytope by any permissible projective transformation, therefore $H_0(n,d)\le n-1$.

If $d\ge 2$ is even (resp. is odd) and $n \leq d+3$ (resp. $n\leq d+4$) then, by taking $k=\lfloor \frac{d}{2}\rfloor$, the lower bound of \eqref{eq:boundsmcmullengen}, all polytopes with less than $d+3$ (resp. $d+4$) vertices are in the projective class of a neighbourly polytope (i.e. $k$--neighbourly for $k=\lfloor \frac{d}{2}\rfloor$). The last two equalities follow by using the same argument as above.
\end{proof}

The following result is an easy consequence of Proposition \ref{easybounds} and Equation \eqref{upperboundcyclicp}:


\begin{proposition}\label{easybounds1} Let $d,n\ge 1$ be integers. Then,
$$H_{d-1}(n,d)\left\{\begin{array}{ll}
\le f_{d-1}(C_{d}(n)) & \text{ if } n\le 2d+1,\\
\le f_{d-1}(C_{d}(n-1)) & \text{ if } n \ge 2d+\lceil\frac{d+1}{2}\rceil,\\
=f_{d-1}(C_d(n)) & \text{ if } d \text{ is even and } n\le d+3,\\
=f_{d-1}(C_d(n)).& \text{ if } d \text{ is odd and } n\le d+4.\\
\end{array}\right.$$
Moreover,  $f_{d-1}(P_d(n))\le H_{d-1}(n,d)$ when $n\le 2d+1$.\\
\end{proposition}

\section{Oriented matroid setting}\label{sec:lawrence}

Recall that an oriented matroid  $M$ is \emph{acyclic} if it does not contain positive circuits (otherwise, $M$ is
called \emph{cyclic}). We say that an element $e$ of an oriented acyclic matroid is \emph{interior} if there exists a signed circuit $C=(C^+,C^-)$ with $C^-=\{e\}$.
Cordovil and Da Silva \cite{CORDOVIL1985157} proved that a permissible projective transformation on $n$ points in $\mathbb R^d$ corresponds to an acyclic reorientation
of its corresponding oriented matroid $M$ of rank $r=d+1$ and conversely.

A natural generalization of $n(d,t)$ in terms of oriented matroids is given by the following function.

\begin{quote}
$\bar n(d,t):=$ the largest integer such that for any uniform matroid $M$ of rank $d+1$ with $\bar n(d,t)$ elements there is an acyclic reorientation of $M$ with at most $t$ interior elements.
\end{quote}

We notice that $n(d,t)=\bar n(d,t)$ in the case when $M$ is {\em realizable}. In this section we shall provide examples of uniform oriented matroids such that for any acyclic reorientation there are at least $t+1$ interior elements, thus providing upper bounds on $\bar{n}(d,t)$. To this end, we briefly outline some facts of the special class,
 {\em Lawrence oriented matroids,} (see \cite{OM1999,RAMIREZALFONSIN2001} for further details and proofs).

A {\em Lawrence oriented matroid} (LOM) ${M}$ of rank $r$ on the
totally ordered set $E=\{1,\ldots,n\}$, $r\le n$, is a uniform
oriented matroid obtained as the union of $r$ uniform oriented
matroids ${M}_1,\ldots,{M}_r$ of rank $1$ on $(E,<)$. LOM can also be defined via the signature
of their bases, that is, via their chirotope $\chi$. Indeed, the
chirotope $\chi$ corresponds to some LOM,
${M}_A,$ if and only if there exists a matrix $A=(a_{i,j})$,
$1\le i\le r$, $1\le j\le n$ with entries from $\{+1,-1\}$ (where
the $i$th row corresponds to the chirotope of the oriented matroid
$\mathcal{M}_i$) such that
\begin{equation}\label{eq3}
\chi(B)=\prod_{i=1}^{r} a_{i,j_i}
\end{equation}
 where $B$ is an ordered $r$-tuple, $j_1\le\ldots\le j_r,$ of elements of $E$.

\begin{remark} We highlight some useful Properties of LOM.
\begin{enumerate}[(a)]
\item Acyclic LOM are realizable as configurations of points (since they are unions of realizable oriented matroids).
\item LOM are closed under minors and duality.
\item The LOM corresponding to the reorientation of an element $c \in E,$  $_{\bar c}M_A$ is obtained by reversing the sign of all the coefficients of a column $c$ in $A$.
\end{enumerate}
\end{remark}

From now, we will denote $A=A_{r,n}$ as a matrix with entries $a_{i,j}\in \{+1,-1\}$, $1\le i\le r$, $1\le j\le n$.
Some of the following definitions and lemmas, which highlight the properties of $A$, and facilitate the study of these type of matroids, where introduced and proved in \cite{RAMIREZALFONSIN2001}:

A \emph{Top Travel}, denoted as $TT,$ in $A$ is a subset of the entries of \(A$, \linebreak
$\{ [a_{1, 1}, a_{1, 2},\dots ,a_{1, j_{1}}] , [a_{2, j_{1}}, a_{2, j_{1}+1},\dots , a_{2, j_{2}}] , \dots , [a_{s, j_{s-1}}, a_{s, j_{s-1}+1},\dots , a_{s, j_{s}}] \}$, with the following characteristics:
\begin{enumerate}
\item$ a_{i, j_{i-1}} \times a_{i, j}= 1, \quad \forall \quad\  j_{i-1} \leq j < j_{i};$
\item$ a_{i, j_{i-1}} \times a_{i, j_{i}}= -1;$  and
\item either
\begin{enumerate}
\item $1\leq s < r$;   then  $j_{s} = n$ or
\item $s=r$ and $ j_{s} \leq n.$
\end{enumerate}
\end{enumerate}

A \emph{Bottom Travel}, denoted as $BT$, in $A$ is a subset of the entries of \(A$, \linebreak
$\{ [a_{r, n}, a_{r, n-1},\dots ,a_{r, j_{r}}] , [a_{r-1, j_{r}}, a_{r-1, j_{r}-1},\dots , a_{r-1, j_{r-1}}] , \dots , [a_{s, j_{s-1}}, a_{s, j_{s-1}+1},\dots , a_{s, j_{s}}] \}$, with the following characteristics:
\begin{enumerate}
\item $ a_{i, j_{i+1}} \times a_{i, j}= 1, \quad \forall \quad\  j_{i} < j \leq j_{i+1};$
\item $ a_{i, j_{i+1}} \times a_{i, j_{i}}= -1;$  and
\item either
\begin{enumerate}
\item $1 < s \leq r$;   then  $j_{s} = 1$ or
\item $s=1$ and $ 1 \leq j_{s}.$
\end{enumerate}
\end{enumerate}

Note that every matrix $A$ has exclusively one $TT$ and one $BT$ and they carry surprising information about $M_{A}$.

In \cite{RAMIREZALFONSIN2001} was proved that if $A = A_{r,n}$  then the following conditions are equivalent:
\begin{enumerate}
\item$M_{A}$ is \emph{cyclic};
\item $TT$ ends at $ a_{r,s}$ for some $ 1 \leq s < n$; and
\item $BT$ ends at $ a_{1, s'}$ for some $ 1< s' \leq n$.
\end{enumerate}

We say that $TT$ and $BT$ are \emph{parallel} at column $k$ in $A$ if
$a_{i,k-1},a_{i,k},a_{i,k+1}\in TT$ and either $a_{i,k-1},a_{i,k},a_{i,k+1}\in BT$ or $a_{i+1,k-1},a_{i+1,k},a_{i+1,k+1}\in BT$, with $2\le k\le n-1$, $1\le i\le r$.

We have \cite{RAMIREZALFONSIN2001} that for $A = A_{r,n}$, then $k$ is an interior element of $M_A$ if and only if
\begin{itemize}
\item[(a)] $BT=(a_{r,n},\ldots,a_{1,2},a_{1,1})$ for $k=1$,
\item[(b)] $TT=(a_{1,1},\ldots,a_{r,n-1},a_{r,n})$ for $k=n$,
\item[(c)] $TT$ and $BT$ are parallel at $k$ for $2\le k\le n-1$.
\end{itemize}

The above imply that we can identify acyclic reorientations and interior elements of $M_{A}$ by studying the behaviour of the $TT$ and $BT$ in the re-orientations of $A$.

\begin{example} Let $M_A$ be the LOM associated to the matrix $A$ given in Figure \ref{ejemplo}.
We notice that $M_A$ is acyclic and that $4$, $5$ and $6$ are interior elements.
   \begin{figure}[htb]
\begin{center}
 \includegraphics[width=.4\textwidth]{ejemplo.pdf}
\caption{Top and Bottom travels in matrix $A$.} \label{ejemplo}
\end{center}
\end{figure}
\end{example}

Interestingly, all possible re-orientations of the matroid can be identified with yet another simple object;

A \emph{Plain Travel}  in $A$, denoted as PT, is a subset of the entries of \(A$ which satisfies:
\[PT=\{ [a_{1, 1}, a_{1, 2},\dots ,a_{1, j_{1}}] , [a_{2, j_{1}}, a_{2, j_{1}+1},\dots , a_{2, j_{2}}] , \dots , [a_{s, j_{s-1}}, a_{s, j_{s-1}+1},\dots , a_{s, j_{s}}] \} \]  with \( 2\leq j_{i-1} \leq j_{i}  \leq n \quad \forall \quad 1 \leq i \leq r ,\;\; 1< s \leq r$   and  $j_{s} = n$.

We have {\cite{RAMIREZALFONSIN2001}} that there is a bijection between the set of all plain travels of $A$ and the set of all acyclic reorientations of $M_{A}$. The correspondence between an acyclic reorientation of $M_{A}$ and a $PT$ of $A$ is given by the subset of columns of $A$ (i.e. a subset of elements of $E$) that have to be reoriented in order to transform the top travel of $A,$ $TT,$ into $PT$.

Finally, we recall  another useful object  that can be constructed from the matrix $A,$
the \emph{chessboard} $B[A]$ which is a black and white board of size $(r-1)*(n-1)$, such that the square $s(i,j)$ has its upper left hand corner at the intersection of row $i$ and column $j$. A square $s(i,j)$, with $1 \leq i \leq r-1$ and $ 1 \leq j \leq n-1$, will be said to be {\em black} if the product of the entries $a_{i,j}, a_{i,j+1}, a_{i+1,j}, a_{i+1,j+1}$ is $-1$, and {\em white} otherwise.

\begin{proposition} \cite{RAMIREZALFONSIN2001}
\label{prop:chessboard}
The following properties establish a link between chessboards, reorientations of a LOM, and travels:
\begin{enumerate}[(a)]
\item $B[A]$ is invariant under reorientations of $M_A$.
\item If in a pair of consecutive columns there is one black square between the top travel $TT$ and the bottom travel $BT$, they follow symmetrically opposite paths through the entries of the matrix; in other words, if $TT$ makes a single horizontal movement from $a_{i,j}$ to $a_{i,j+1}$ and continues its movement forward in the same row (i.e $a_{i,j} = a_{i,j+1}$) , then $BT$ goes from  $a_{i+h,j+1}$ to $a_{i+h,j}$  and moves vertically to  $a_{i+h-1, j}$ (i.e. $a_{i+h,j+1}\neq a_{i+h,j}$), with $h\geq{1}$, and vice versa.
\end{enumerate}

\end{proposition}

\section{Upper bounds for $\bar{n}(d,t)$}\label{cotassupmatroides}

\subsection{Small dimensions} We first show that $\bar{n}(d,t)\le 2d+1+t$ for $d=2,3$ and every $t\ge0$. The following remark will be very useful throughout this section.

 \begin{remark} \label{dim1}
Any acyclic reorientation of a rank $2$ oriented matroid on $n$ elements  has
 $n-2$ interior elements.
\end{remark}

Given a matrix $A=A_{n,r}$, let $A^+_{i,j}$ be  the submatrix of $A$  that results after removing rows $i+1,\ldots, r$ and columns $j+1,\ldots, n$. Similarly, let $A^-_{i,j}$ be the submatrix of $A$ resulting after the removal of rows $1,\ldots, i-1$ and columns $1,\ldots,j-1,$.

 \begin{theorem}\label{dimension2}
$\bar{n}(2,t)<t+6$ for every  $t\ge 0$.
\end{theorem}\begin{proof}
Let $A=A_{3,t+6}$  be such that the corresponding chessboard $B[A]$ has exactly one black square for each column and   let  $PT$ be any plane travel in $A$. We shall prove that the corresponding $\mathcal{A}$ in which $PT$ is the Top Travel has at least $t+1$ interior elements.
 Let $j$ be the smallest number such that column $j$ is not an interior element in $\mathcal{A}$ and there are not vertical movements in column $j$ of $PT$ neither of $BT$.
  If $j$ does not exists, as $PT$ and $BT$ can make at most $2$ vertical movements each, then $\mathcal{A}$ would have at least $t+2$ interior elements. Hence, we may suppose that $j$ exists.  By the rules of Property \ref{prop:chessboard}, $PT$ and $BT$  make a vertical movement in column $j+1$ and $j-1$, respectively.
   Notice by the definition of $j$ that $PT$ and $BT$ arrives in column $j$ at row $1$ and $3$, respectively, otherwise $j$ would be an interior element. Then,  each interior element of $A^+_{2,j-1}$  and $A^-_{2,t+6-j}$ is an interior element of $\mathcal{A}$. Therefore,   $A^+_{2,j-1}$  has  $j-3$ interior elements and  $A^-_{2,t+6-j}$ has $t+6-j-2$ interior elements  by  Remark \ref{dim1}, concluding the proof.
 \end{proof}



Given a matrix $A=A_{r,n}$, we say that a chess board $B[A]$ has the \emph{sequence} $(x_1,x_2,\ldots,x_{r-1})$ if the square $s(i,j)$ is black if and only if $\sum\limits_{k=0}^{i-1}x_{k}+1\le j\le \sum\limits_{k=0}^{i}x_{k}$ with $1 \leq i \leq r-1$ and $1 \leq j \leq n-1$, where we define $x_0=0$.


\begin{example} Figure \ref{figurehypothesis} illustrates a chessboard with sequence $(2,3,2,3)$.
\end{example}


 \begin{theorem}\label{dimension3}
$\bar{n}(3,t)<t+8$ for  $t\ge 0$.
\end{theorem}\begin{proof}
 Let $A=A_{4,t+8}$  be such that the corresponding chessboard $B[A]$ has a sequence $(2,t+3,2)$ and  let  $PT$ be any plane travel in $A$. We prove that the corresponding $\mathcal{A}$ in which $PT$ is the Top Travel has at least $t+1$ interior elements. Let $j$ be the smallest number such that column $j$ is not an interior element in $\mathcal{A}$ and there are not vertical movements in column $j$ of $PT$ neither of $BT$. 
  If $j$ does not exists, as $PT$ and $BT$ can make at most $3$ vertical movements each, then $\mathcal{A}$ would have at least $t+2$ interior elements. Hence, we may suppose that $j$ exists.  By the rules of Property \ref{prop:chessboard}, $PT$ and $BT$  make a vertical movement in column $j+1$ and $j-1$, respectively.  
  
By the definition of  $j$, $TT$ arrives in column $j$ at row $1$ or $BT$ arrives in column $j$ at row $4$, otherwise $j$ would be an interior element. Suppose without loss of generality that $TT$ arrives in column $j$ at row $1$. Then, $BT$ arrives in column $j$ at row $2$ or $3$ (see Figure \ref{dim3}).
   \begin{figure}[htb]
\begin{center}
 \includegraphics[width=.2\textwidth]{fig_dim3caso1.pdf}
\caption{$BT$ in blue and $TT$ in red.}
 \label{dim3}\end{center}
\end{figure}
Notice that each interior element of $A^+_{3,j-1}$   and $A^-_{2,t+8-j}$ is an interior element of $\mathcal{A}$. If $BT$ arrives in column $j$ at row $3$, by the rules of Property \ref{prop:chessboard}, $A^+_{3,j-1}$  has  $j-4$ interior elements and $A^-_{2,t+8-j}$ has $t+5-j$ interior elements, concluding the proof in this case.  If $BT$ arrives in column $j$ at row $2$, by the rules of Property \ref{prop:chessboard} and by Remark \ref{dim1}, one can check that $A^+_{3,j-1}$  has  $j-3$ interior elements and $A^-_{2,t+8-j}$ has at least $t+4-j$ interior elements, concluding the proof.
 \end{proof}


\subsection{High dimensions $d$}
In what follows, we will consider different matrices $A=A_{r,h(r)}$ where $h(r)$ is a strictly increasing function. If $B[A]$ has the sequence $(x_1,x_2,\ldots,x_{r-1})$, we will consider functions, $h(r),$ where $h(1)=1$, $\sum\limits_{k=1}^{m-1}x_{k}+1\le h(m)\le \sum\limits_{k=1}^{m}x_{k}+1$ if  $2\le m\le r-1$ and $\sum\limits_{k=1}^{r-1}x_{k}+1\le h(r)$.

For every $1\le m\le r-1$, we will say that the element $a_{m,h(m)}$  is  the \emph{$m$--th corner} of $A$.

\begin{example} Figure \ref{figurehypothesis} illustrates a chessboard with $h(r)=2(r-1)+\lceil\frac{r}{2}\rceil$.
\end{example}

The following lemmas will be very useful.
 \begin{lemma}\label{lemmageneral1}
 Let $A=A_{r,h(r)}$ be a matrix with $r\ge 3$ such that $B[A]$ has the sequence $(x_1,x_2,\ldots,x_{r-1})$, with $x_i\ge1$, $1\le  i\le r-1$. Suppose that $TT$ always passes strictly above all corners after  the $1$--st corner, then

\begin{itemize}
 \item [(i)] $a_{i,h(2)}\in BT$ for some $i\le \max\{2,2r-h(r-1)+h(2)-3\}$,
\item [(ii)] $a_{i,h(2)}\in BT$ for some $i\le \max\{2,2r-h(r)+h(2)-1\}$ if $TT$ and $BT$ do not share steps from columns $h(2)$ to $h(r)$.
 \end{itemize}
 \end{lemma}
\begin{proof}
We will proceed by induction  on $r\ge3$.  Using the rules of Property \ref{prop:chessboard},  one can check that the lemma holds for $r=3$. 
Suppose that the result holds for $r-1$ and we show it for $r\ge4$. If $BT$ arrives at the $m$--th corner for $3\le m\le r-1$, the result follows by the induction hypothesis. Moreover, if $BT$ arrives at the $2$--th corner, the result follows.
Similarly, the result follows if $BT$ arrives at $a_{i,h(m)}$ for $2\le m\le r-1$ and $i\le m$.  Then, we may suppose that $BT$ always passes strictly below the $m$--th corner for every $2\le m\le r-1$.

Notice that $TT$ makes exactly $h(r)-h(2)$ horizontal movements and at most $r-1$ vertical movements, from right to left, to arrive at  $a_{1,h(2)}$. We know, by the rules of construction of $TT$ that for each vertical movement we must also count one horizontal movement. So, $TT$ makes at least $h(r)-h(2)-(r-1)$ single horizontal movements, from right to left, until   $a_{1,h(2)}$ is attained.


On the other hand, as $TT$ always passes strictly above all corners after  the $1$--st corner and $BT$ always passes strictly below the $m$--th corner for every $2\le m\le r-1$,  then $TT$ and $BT$  do not share steps from columns $h(2)$ to $h(r-1)$. However, $TT$ and $BT$ could share at most $h(r)-h(r-1)-2$ steps from columns $h(r-1)+1$ to $h(r)$ (see Figure \ref{figurehypothesis}).
\begin{figure}[htb]
\begin{center}
 \includegraphics[width=.35\textwidth]{fig_hypothesislemma2.pdf}
 \caption{The chessboard $B[A]$ with sequence $(2,3,2,3)$ and $h(r)=2(r-1)+\lceil\frac{r}{2}\rceil$. The points represent the corners of $A=A_{5,h(5)}$. We observe that $TT$ and $BT$ share the final step.} \label{figurehypothesis}
 \end{center}
\end{figure}

Therefore, by the rules of Property \ref{prop:chessboard},  for each single horizontal movement that $TT$ does not share with $BT$, $BT$ makes a vertical movement. So, $BT$ makes at least  $h(r)-h(2)-(r-1)-(h(r)-h(r-1)-2)=h(r-1)-h(2)-r+3$ vertical movements, from right to left, until   column $h(2)$ is attained. Hence,
 $BT$ arrives at $a_{i,h(2)}$ for some $i\le \max\{2,r-(h(r-1)-h(2)-r+3)\}$  concluding the first part of the proof.  If  $TT$ and $BT$ do not share steps from columns $h(2)$ to $h(r)$, then $BT$ makes at least  $h(r)-h(2)-(r-1)$ vertical movements, from right to left, until   column $h(2)$  is attained, concluding that
 $BT$ arrives at $a_{i,h(2)}$ for some $i\le \max\{2,r-(h(r)-h(2)-(r-1))\}$.
  \end{proof}

\begin{lemma}\label{lemmageneral2}Let  $A=A_{r,h(r)}$ be a matrix and suppose that  $TT$ always passes strictly above all corners after  the $1$--st corner. Then the following holds:
\begin{itemize}
  \item [(i)] If $B[A]$ has a sequence $(x_1,x_2,\ldots,x_{r-1})$, $x_i\ge2$  for odd $i$, $x_j\ge3$ for even $j$ and $h(m)=\sum\limits_{k=0}^{m-1}x_{k}+1$ for every $1\le m\le r$,   then $a_{1,1},a_{1,2}\in BT$ when $r\ge4$.  When $r=3$,  $a_{1,1}, a_{1,2}\in BT$, or column $h(r)$ is an interior element and $a_{2,1},a_{1,1}\in BT$.

  \item [(ii)]   If $B[A]$ has a sequence $(x_1,x_2,\ldots,x_{r-1})$, $x_i\ge3$  for odd $i$, $x_j\ge2$ for even $j$ and $h(m)=\sum\limits_{k=0}^{m-1}x_{k}+1$ for every $1\le m\le r$, then $a_{1,1},a_{1,2}\in BT$ when $r\ge3$.

  \item [(iii)] If $B[A]$ has a sequence $(2,t+3,2,t+1,t+1,\ldots,t+1)$ for some $t\ge2$,  $h(2)=t+3$, $h(3)=t+6$ and $h(m)=(t+1)(m-3)+7$ for $4\le m\le r$ for every  $4\le m\le r$, then $a_{i,t+3}\in BT$ for some $i\le 2$ when $r\ge4$ (see Figure \ref{cotageneral2}).
   
    

\item [(iv)]  If $B[A]$ has a sequence $(t+1,\ldots,t+1,2,t+3,2)$ for some $t\ge2$,  $h(2)=t+3$,
 $h(r)=(t+1)(r-3)+7$ and $TT$ and $BT$ do not share steps from columns $h(2)$ to $h(r)$, then $a_{i,t+3}\in BT$ for some $i\le 2$ when $r\ge5$.
 


  \item [(v)] If  $B[A]$ has a sequence $(2,4,2,3,2,3,\ldots)$ and $h(m)=2(m-1)+\lceil\frac{m}{2}\rceil+1$ for every $2\le m\le r$,  then $a_{i,4}\in BT$ for some $i\le 2$ when $r\ge4$. 

       \item [(vi)] If $r\ge6$  is even, 
       $B[A]$ has a sequence $(2,3,2,3,\ldots,2,4,2)$, $h(2)=4$, $h(r)=2(r-1)+\lceil\frac{r}{2}\rceil+1$  and $TT$ and $BT$ do not share steps from columns $h(2)$ to $h(r)$, then $a_{i,4}\in BT$ for some $i\le 2$. 
\end{itemize}
\end{lemma}
\begin{proof}
We prove (i) and (ii) for $B[A]$ with sequences  $(2,3,2,3\ldots)$ and  $(3,2,3,2\ldots)$, respectively, since the general case holds as a consequence.

  (i) By the sequence of $B[A]$, we observe that $h(m)=2(m-1)+\lceil\frac{m}{2}\rceil$ for $1\le m\le r$. Then, as $2r-h(r-1)+h(2)-3=4-\lceil\frac{r-1}{2}\rceil\le 2$ when $r\ge4$, we obtain by Lemma  \ref{lemmageneral1} (i) that  $a_{i,h(2)}\in BT$ for some $i\le2$. Since $a_{1,i}\in TT$ for $i\le4$ and $h(2)=3$, we conclude by the rules of Property \ref{prop:chessboard} that $a_{1,1},a_{1,2}\in BT$.
  If $r=3$, one can check that $a_{1,1}, a_{1,2}\in BT$, or  column $6$ is an interior element and $a_{1,1}, a_{2,1}\in BT$ (see Figure \ref{r3}).
\begin{figure}[htb]
\begin{center}
 \includegraphics[width=.2\textwidth]{fig_remarkr3.pdf}
 \caption{Case $r=3$ when column $6$ is an interior element and $a_{1,1}, a_{2,1}\in BT$.  The points represent the corners.} \label{r3}
 \end{center}
\end{figure}

 (ii) By the sequence of $B[A]$, we observe that  $h(m)=2(m-1)+\lceil\frac{m+1}{2}\rceil$ for $1\le m\le r$. Then, as $2r-h(r-1)+h(2)-3=5-\lceil\frac{r}{2}\rceil\le 3$, we obtain by Lemma  \ref{lemmageneral1} (i) that $a_{i,h(2)}\in BT$ for some  $i\le3$. Since $a_{1,i}\in TT$ for $i\le5$  and $h(2)=4$,  we conclude by the rules of Property \ref{prop:chessboard} that $a_{1,1},a_{1,2}\in BT$.

 (iii)   As  $2r-h(r-1)+h(2)-3=2$ when $r=4$ and $2r-h(r-1)+h(2)-3=2r-(t+1)(r-4)-7+t\le 7-r\le2$ when  $r\ge5$ and $t\ge2$, we obtain by Lemma  \ref{lemmageneral1} (i) that  $a_{i,h(2)}\in BT$ for some $i\le 2$. 

(iv) As $2r-h(r)+h(2)-1=2r-(t+1)(r-3)+t-5\le 6-r\le1$ when  $r\ge5$ and $t\ge2$, we obtain by Lemma  \ref{lemmageneral1} (ii) that  $a_{i,h(2)}\in BT$ for some $i\le 2$.


 (v)  As $2r-h(r-1)+h(2)-3=4-\lceil\frac{r-1}{2}\rceil\le2$ when $r\ge4$, we obtain by Lemma   \ref{lemmageneral1} (i) that  $a_{i,h(2)}\in BT$  for some $i\le 2$. 


 (vi)  As $2r-h(r)+h(2)-1=2r-2(r-1)-\frac{r}{2}+2=4-\frac{r}{2}\le1$ when $r\ge6$ is even, we obtain by Lemma   \ref{lemmageneral1} (ii) that  $a_{i,h(2)}\in BT$  for some $i\le 2$.
\end{proof}



From now on,  denote as $A^+_m$ and $A^-_m$ the matrices $A^+_{m,h(m)}$ and $A^-_{m,h(m)}$, respectively (see Figure \ref{cotageneral2}). We are now ready to tackle the problem for any $d\ge4$ and $t\ge2$.
 \begin{theorem}\label{cotageneral}
 $\bar{n}(d,t)<2d+(t-1)(d-2)+3$  for $d\ge4$ and $t\ge 2$. 
    \end{theorem}
\begin{proof}
Let $A=A_{r,h(r)}$  be a matrix  where $h(r)$ is defined as  
$h(2)=t+3$, $h(3)=t+6$, $h(m)=(t+1)(m-3)+7$ for $4\le m\le r$ and  $B[A]$ with sequence $(2,t+3,2,t+1,t+1,\ldots,t+1)$ for $t\ge2$ (see Figure \ref{cotageneral2}).

 \begin{figure}[htb]
\begin{center}
 \includegraphics[width=.6\textwidth]{fig_cotageneral2.pdf}
\caption{A matrix $A=A_{6,h(6)}=A_{6,19}$ and the submatrices $A^+_4$ and $A^-_4$. The chessboard  $B[A]$ has sequence $(2,t+3,2,t+1,t+1)$ for $t=3$.   The points represent the corners of $A$ associated to the function $h(r)$ of Theorem \ref{cotageneral}.} \label{cotageneral2}\end{center}
\end{figure}
 We shall show  by induction on $r$ that for every $r\ge2$ and for any  plain travel $PT$ in $A$, the corresponding $\mathcal{A}$ in which $PT$ is the Top Travel  has at least $t+1$ interior elements. In particular, as $h(r)=(t+1)(d-2)+7=2d+(t-1)(d-2)+3$ for $r\ge5$, we will prove the theorem for $d\ge4$ and $t\ge2$.

We observe that $\mathcal{A}$  has  $t+1$ interior elements when $r=2$ since $\mathcal{A}$ is a $2\times (t+3)$ matrix (Remark \ref{dim1}).
 For $r=3$ and $4$, the result follows by Theorems \ref{dimension2} and \ref{dimension3}, respectively, since the  chessboards  considered in these theorems coincide with  $B[A]$. Thus, assume that the theorem holds for $r-1$ and we show it for $r\ge 5$. Suppose that  the $m$--st corner is the last corner that $PT$ meets in $A$, for some  $1\le m\le r-1$. If  $PT$ always passes strictly below the $i$--st corner for  $i>m$, then there would be at least $t+2$ interior elements in $\mathcal{A}$ (from columns $h(r-1)$ to $h(r)$). Hence,  we may suppose that $PT$ always passes strictly above the $i$--st corner for  $i>m$. We have the following cases.

\emph{Case $m\le r-3.$}
First suppose that $m=1$. Then $a_{i,t+3}\in BT$ for some $i\le 2$  by Lemma \ref{lemmageneral2} (iii), concluding by the rules of Property \ref{prop:chessboard} that there are at least $t+1$ interior elements in $\mathcal{A}$. Now suppose that $2\le m\le r-3.$
As $\mathcal{A}^-_m$  has at least $4$ rows, applying  Lemma \ref{lemmageneral2} (i)  (when $m=3$) and   Lemma \ref{lemmageneral2} (ii) (when $m\neq 3$) on submatrix $\mathcal{A}^-_m$, we obtain that  $a_{m,h(m)},a_{m,h(m)+1}\in BT$. Thus, the theorem holds  by induction  hypothesis on $\mathcal{A}^+_m$ since $BT$  restricted in  $\mathcal{A}^+_m$ is also the Bottom travel of $\mathcal{A}^+_m$ and each interior element of $\mathcal{A}^+_m$ is an interior element of $\mathcal{A}$.

\emph{Case $m=r-2.$}
As $\mathcal{A}^-_m$  has $3$ rows, $a_{m,h(m)},a_{m,h(m)+1}\in BT$, or  column $h(r)$ is an interior element and $a_{m+1,h(m)}, a_{m,h(m)}\in BT$ by Lemma \ref{lemmageneral2} (i). If $a_{m,h(m)},a_{m,h(m)+1}\in BT$, the theorem holds by induction hypothesis on $\mathcal{A}^+_m$. If column $h(r)$ is an interior element and $a_{m+1,h(m)}, a_{m,h(m)}\in BT$, notice that each interior element of $\mathcal{A}^+_m$ is an interior element of $\mathcal{A}$, except for column $h(m)$. Thus, $\mathcal{A}$ has at least $t$ interior elements from columns $1$ to $h(m)$ by induction hypothesis on $\mathcal{A}^+_m$ and one interior element in  column $h(r)$.

\emph{Case $m=r-1.$}
First suppose that $BT$ arrives at the $k$-th corner for some  $2\le k\le r-1$. As each interior element of $\mathcal{A}^+_k$ and $\mathcal{A}^-_m$ is an interior element of $\mathcal{A}$, except for (maybe) columns $h(k)$ and $h(m)$,  $\mathcal{A}$ has at least $t$ interior elements from columns $1$ to $h(k)$ by induction hypothesis on $\mathcal{A}^+_k$ and at least $t-1\ge 1$ interior elements from columns $h(m)$ to $h(r)$ by Remark \ref{dim1} (since $\mathcal{A}^-_m$ is a $2\times (t+2)$ matrix), concluding the proof in this case. Similarly, the proof holds if $BT$ arrives at $a_{i,h(k)}$ for $2\le k\le r-2$ and $i\le k$.
        Now suppose that $BT$ passes always below the $i$--st corner, for every $i\ge2$. In particular, as $BT$ does not arrives at the $m$-th corner, every interior element of $\mathcal{A}^-_m$  is an interior element of $\mathcal{A}$, concluding by Remark \ref{dim1} that $\mathcal{A}$ has $t$ interior elements from columns $h(m)+1$ to $h(r)$. So, we may suppose  that $TT$ and $BT$ do not share steps from columns $1$ to $h(2)$, otherwise the theorem holds.  Also, if $a_{m,h(m)-1}\in PT$, then column $h(m)$ is an interior element and the theorem holds. So, we may suppose that $a_{m,h(m)-1}\not\in PT$. Hence, $a_{r,h(m)-2}\in BT$ by the rules of Property \ref{prop:chessboard}.
     Let $\mathcal{A}^{'}$ be the matrix obtained by turning the matrix $\mathcal{A}$ upside down. We observe that $BT$ and $PT$ are the Top and Bottom Travels of $\mathcal{A}^{'}$, respectively. Let define the $i$--st corners of $\mathcal{A}^{'}$ as $a_{r-i+1,h(r-i+1)}$ for $i\neq 2$ and define the
      $2$--st corner of $\mathcal{A}^{'}$ as $a_{m,h(m)-1}$.
      
     Notice that $BT$ always passes strictly above all corners of  $\mathcal{A}^{'}$ after the $1$--st corner of $\mathcal{A}^{'}$. Moreover, $B[A']$ has the same sequence and the same $2$--st corner as that considered in Lemma \ref{lemmageneral2} (iv). Hence, as $TT$ and $BT$ do not share steps from columns $h(1)$ to $h(m)-1$,  
     we know  by Lemma \ref{lemmageneral2} (iv) that $a_{i,h(m)-1}\in PT$ for some $i\ge r-1$, but this is a contradiction since  we had assumed that $a_{m,h(m)-1}\not\in PT$ and clearly $a_{r,h(m)-1}\not\in PT$, concluding the proof.
\end{proof}
Figure \ref{contraexample1} (a) shows that the chessboard considered in Theorem \ref{cotageneral} can not be used to prove  $\bar{n}(d,1)<2d+(t-1)(d-2)+3$  for $d=4$ and $t=1$. In fact, this example can be generalized in order to show that this chessboard can not be used to prove   $\bar{n}(d,t)<2d+3$ for $d\ge4$.

\begin{theorem}\label{tpequeno}
 $\bar{n}(d,1)<2d+\lceil\frac{d+1}{2}\rceil+1$  for $d\ge4$.  
 \end{theorem}
\begin{proof}
Let $A=A_{r,h(r)}$  be a matrix  where  $h(r)$ is defined as  $h(m)=2(m-1)+\lceil\frac{m}{2}\rceil+1$ for every $2\le m\le r$ and $B[A]$ has sequence $(2,4,2,3,2,3,\ldots)$. We shall show  by induction on $r$ that for every $r\ge2$ and for any  plain travel $PT$ in $A$, the corresponding $\mathcal{A}$ in which $PT$ is the Top Travel  has at least $2$ interior elements. In particular, as $h(r)=2d+\lceil\frac{d+1}{2}\rceil+1$ for $r\ge5$, we will prove the theorem for $d\ge4$.

We observe that $\mathcal{A}$  has at least  $2$ interior elements when $r=2$ since $\mathcal{A}$ is a $2\times4$ matrix (Remark \ref{dim1}). For $r=3$ and $4$, the result follows by Theorems \ref{dimension2} and \ref{dimension3}, respectively (applying them for $t=1$), since the  chessboards  considered in these theorems coincide with  $B[A]$. Thus, assume the theorem holds for $r-1$ and we show it for $r\ge 5$. Suppose that  the $m$--st corner is the last corner that $PT$ meets in $A$, for some  $1\le m\le r-1$. If  $PT$ always passes strictly below the $i$--st corner for  $i>m$, then there would be at least $3$ interior elements in $\mathcal{A}$ (from columns $h(r-1)$ to $h(r)$). Hence,  we may suppose that $PT$ always passes strictly above the $i$--st corner for  $i>m$. If $m=1$, then $a_{i,4}\in BT$ for some $i\le 2$ by Lemma \ref{lemmageneral2} (v), concluding by the rules of Property \ref{prop:chessboard} that there are at least $2$ interior elements in $\mathcal{A}$. We omit the proof of the cases $2\le m\le r-2$, since they are analogous to those in the proof of Theorem \ref{cotageneral}. Now, consider the case $m=r-1$.

If $r$ is odd,  $B[A]$ has a sequence $(2,4,2,3,2,3,\ldots,2,3)$ and one can verify that there are at least $2$ interior elements in $\mathcal{A}$ or  $a_{m,h(m)},a_{m,h(m)+1} \in BT$. In both cases the theorem holds. Now suppose that $r$ is even and then $B[A]$ has a sequence $(2,4,2,3,2,3,\ldots,3,2)$.
If $a_{m,h(m)},a_{m,h(m)+1} \in BT$,  the result follows by induction hypothesis on $\mathcal{A}^+_m$. Then, suppose from now that the above does not hold. Hence, each interior element of $\mathcal{A}^-_m$   is an interior element of $\mathcal{A}$ concluding  by Remark \ref{dim1} that  $\mathcal{A}$ has one interior element from columns $h(m)+1$ to $h(r)$ (since $\mathcal{A}^-_m$ is a $2\times 3$ matrix). First suppose that $BT$ arrives at the $k$-th corner for some  $2\le k\le r-1$. As each interior element of $\mathcal{A}^+_k$  is an interior element of $\mathcal{A}$, except for (maybe) column $h(k)$, $\mathcal{A}$ has at least one interior element from columns $1$ to $h(k)$ by induction hypothesis on $\mathcal{A}^+_k$ and since  $\mathcal{A}$ has one interior element from columns $h(m)+1$ to $h(r)$, the theorem holds in this case. Similarly, the proof holds if $BT$ arrives at $a_{i,h(k)}$ for $2\le k\le r-2$ and $i\le k$. Now suppose that $BT$ passes always below the $i$--st corner, for every $i\ge2$. If $TT$ and $BT$ share steps from columns $1$ to $h(2)$, then $\mathcal{A}$  has at least one interior element from columns $1$ to $h(2)$ and since $\mathcal{A}$ has one interior element from columns $h(m)+1$ to $h(r)$, the theorem holds. Then, we may suppose that $TT$ and $BT$ does not share steps from columns $1$ to $h(2)$.  Also,  if $a_{m,h(m)-1}\in PT$, then column $h(m)$ is an interior element and the theorem holds. So, we may suppose that $a_{m,h(m)-1}\not\in PT$. Hence, $a_{r,h(m)-2}\in BT$ by the rules of Property \ref{prop:chessboard}. Let $\mathcal{A}^{'}$ be the matrix obtained by turning the matrix $\mathcal{A}$ upside down. We observe that $BT$ and $PT$ are the Top and Bottom Travels of $\mathcal{A}^{'}$, respectively.

Let define the $i$--st corners of $\mathcal{A}^{'}$ as $a_{r-i+1,h(r-i+1)}$ for $i\neq 2$ and define the
      $2$--st corner of $\mathcal{A}^{'}$ as $a_{m,h(m)-1}$.    Notice that $BT$ always passes strictly above all corners of  $\mathcal{A}^{'}$ after the $1$--st corner of $\mathcal{A}^{'}$. Moreover, $B[A']$ has the same sequence and the same $2$--st corner as that considered in Lemma \ref{lemmageneral2} (vi). Hence, as $TT$ and $BT$ do not share steps from columns $h(1)$ to $h(m)-1$, we know  by Lemma \ref{lemmageneral2} (vi) that $a_{i,h(m)-1}\in PT$ for some $i\ge r-1$, but this is a contradiction since  we had assumed that $a_{m,h(m)-1}\not\in PT$ and clearly $a_{r,h(m)-1}\not\in PT$, concluding the proof.
\end{proof}

The chessboard considered in Theorem \ref{cotageneral} can not be extended to a chessboard with sequence $(2,t+3,2,3,2,3,\ldots)$ in order to prove $\bar{n}(d,t)<2d+\lceil\frac{d+1}{2}\rceil+t$. Figures \ref{contraexample1} (b) and (c) provide examples of this phenomena for $d=5, t=2$,  
and for $d=4, t=3$, respectively.
In fact, these examples can be generalized in order to
show that this chessboard can not be used to prove $\bar{n}(d,t)<2d+\lceil\frac{d+1}{2}\rceil+t$
for odd $d\ge5, t\ge2$ and for even $d\ge 4, t\ge3$.

The upper bound given in Theorem \ref{cotageneral} can be improved when $d$ is even.

 \begin{theorem}\label{dpar}
 $\bar{n}(d,t)<2d+(t-1)\frac{d}{2}+3$  for even $d\ge4$ and $t\ge 2$.
 \end{theorem}

This theorem can be proved by making one final tweak to the chessboard defined previously. The latter is a bit technical and requires some extra work in the same flavour as above. This will be done in the Annex.


\subsection{Proofs of the main results.}

\begin{proof}[Proof of Theorem  \ref{boundsforf_o}.] Recall that $n(d,t)= \bar{n}(d,t)$ and that $H_0(n(d,t),d)=n(d,t)-t$.


\begin{itemize}
\item $d=1, \ n\ge 2$. We clearly have that $H_0(n,1)=2$ since every convex set in dimension $1$ has as support only two vertices.

\item $d=2, \ n\ge 5$. By Corollary \ref{igualdadv}, we have $n(2,t)=5+t$ for any integer $t\ge 0$. So, by Remark \ref{relationf_0andn(d,t)}, we have $H_0(t+5,2)=5$ for any integer $t\ge 0$ or, equivalently, $H_0(n,2)=5$ for any integer $n\ge 5$.


\item $d=3, \ n\ge 7$. By Theorem \ref{dimension3}, we have $n(3,t)\le 7+t$ for any integer $t\ge 0$. So, by Remark \ref{relationf_0andn(d,t)}, we have $H_0(t+7,3)\le 7$ for any integer $t\ge 0$ or, equivalently, $H_0(n,3)\le 7$ for any integer $n\ge 7$.
\smallskip

\item $d\ge 2, \ n\le 2d+1$. By  Proposition \ref{easybounds}, $H_0(n,d)=n.$

\item $d\ge 4, \ n \ge 2d+\lceil\frac{d+1}{2}\rceil.$ By Proposition \ref{easybounds}, $H_0(n,d)< n.$

\item $d\ge 4, \ n\ge 2d+\lceil\frac{d+1}{2}\rceil+1.$ By Theorem \ref{tpequeno} $\bar{n}(d,1)< 2d+\lceil\frac{d+1}{2}\rceil+1$. Therefore, $H_0(n,d) < n-1.$

\item $d\ge 4,  \  2d+3+l(d-2) \leq n < 2d+3+(l+1)(d-2),$ $l\geq 1.$  By Theorem \ref{cotageneral}, $\bar{n}(d,t)<2d+(t-1)(d-2)+3$  for every $t\ge 2.$ Since $H_0(n(d,t),d)=\bar{n}(d,t)-t$ then, for a given $n,$ it would be enough to work out $t$ such that $2d+(t-2)(d-2)+3 \leq {n}<2d+(t-1)(d-2)+3,$ in order to conclude $H_0(n,d) < n-t.$

It is not hard to see that we may take $t=\lfloor\frac{n-2d-3}{d-2}\rfloor+1\ge2$ and it follows that $H_0(n,d)\le n-(\lfloor\frac{n-2d-3}{d-2}\rfloor+2)$ for every $n\ge3d+1$. Finally, this can be expressed as; if $2d+3+l(d-2) \leq n < 2d+3+(l+1)(d-2)$ for some $l\ge1$, then  $H_0(n,d) \le n-(l+2)$.


\end{itemize}


\end{proof}


\begin{proof}[Proof of Theorem \ref{boundsforf_d-1}] The bounds are obtained by combining Proposition \ref{easybounds}, Theorem \ref{boundsforf_o} and inequality \eqref{upperboundcyclicp}.
\end{proof}

\section{Arrangement of pseudo-hyperplanes}\label{sec:arrangements}

Recall that a  {\em projective} $d$-arrangement of $n$ (pseudo) hyperplanes $\mathcal{H}(d,n)$ is a finite collection of pseudo-hyperplanes in the projective space $\mathbb{P}^d$ such that no point belongs to every hyperplane of $\mathcal{H}(d,n)$. Any such arrangement, $\mathcal{H}$ decomposes $\mathbb{P}^d$  into a $d$--dimensional cell complex. A cell of dimension $d$ is usually called a \emph{tope} of the arrangement $\mathcal{H}$.

The  well-known  Topological Representation Theorem due to Folkman and Lawrence \cite{FOLKMAN1978199} states that loop-free oriented
matroids of rank $d+1$ on $n$ elements (up to isomorphism) are in one-to-one correspondence with arrangements of pseudo-hyperplanes in the projective space $\mathbb{P}^{r-1}$ (up to topological equivalence).

A $d$-arrangement is said to be \emph{simple} if no $d+1$ hyperplanes have a common point, i.e., the hyperplanes are in general position. It is known that simple $d$-arrangements of $n$ (pseudo) hyperplanes correspond to \emph{uniform} oriented matroids of rank $d+1$ on $n$ elements.

If we denote as $\mathcal{H}=\{h_i\}_{1\le i\le n}$ an arrangement of (pseudo)hyperplanes and $M_{\mathcal H}$ as its corresponding oriented matroid, where  $e_i$ is the element of $M_{\mathcal H}$ corresponding to (pseudo)hyperplane $h_i$, then, it is known that an acyclic reorientation of $M_{\mathcal A}$ having $\{e_{i_1},e_{i_2},\ldots,e_{i_l}\}$, with $l\le n$, as interior elements corresponds to a tope in ${\mathcal H}$ which is bordered precisely by the (pseudo)hyperplanes $h_j\not\in\{h_{i_1},h_{i_2},\ldots,h_{i_l}\}$.

The \emph{size} of a tope is the number of (pseudo)hyperplanes bordering it. The function $\bar n(d,t)$ can thus be defined in terms of hyperplane arrangements as follows

\begin{quote}
$\bar n(d,t):=$ the  largest integer $m$ such that any simple arrangement of $m$ (pseudo) hyperplanes in $\mathbb{P}^d$ contains a tope of size at least $m-t$.
\end{quote}

The latter is related to the following conjecture by Las Vergnas:

\begin{quote}\emph{Every arrangement of (pseudo) hyperplanes in $\mathbb{P}^d$ admits a tope of size $d+1$ (a simplex).}
\end{quote}

This conjecture is known to be true when the arrangements are hyperplanes i.e., for realizable oriented matroids \cite{Roudneff1988, Shannon1979}.

We are able to give a lower bound for $\bar{n}(d,t)$ when $d=2$.

\begin{proposition}\label{lowerboundvd=2}
Every simple arrangement of at least $5$ (pseudo) lines in $\mathbb{P}^2$ has a tope of size at least $5$.
\end{proposition}
\begin{proof}
The proof is by induction on the set of $n$ (pseudo) lines. By Equation \ref{eq:boundsmcmullengen}, any arrangement of $5$ (pseudo) lines in $\mathbb{P}^2$ has a tope of size $5$ and thus the proposition holds for $n=5$. We suppose the result true for $n'<n$ and will prove that any arrangement $H$ of $n\ge6$ (pseudo) lines in $\mathbb{P}^2$ has a tope of size at least $5$.  Let $l\in H$, then by induction $H-{l}$ has a tope $T$ of size at least $5$ in $\mathbb{P}^2$. If $l$ does not intersect $T$, then $T$ is a tope of $H$ of size at least $5$ in $\mathbb{P}^2$. Otherwise, $l$ divides $C$ into two topes, and since $H$ is simple then one of these two topes is of size at least $5$.
\end{proof}

\begin{corollary}\label{corolowerboundvd=2}
$5+t\le \bar{n}(2,t)$ for every  $t\ge 0$.
\end{corollary}

By combining this result with Theorem \ref{dimension2}, we obtain the following.

 \begin{corollary}\label{igualdadv}
$\bar{n}(2,t)=5+t$ for any $t\ge0$.
 \end{corollary}


\section{Pach and Szegedy's question}\label{sec:anapplication}

In order to investigate Question \ref{question:ps}, we may consider a more general problem.  Let $X$ be a finite set of points in $\mathbb R^d$. We say that $A, B$ is a {\em Radon partition} of $X$ if $X=A\cup B$, $A\cap B=\emptyset$ and $conv(A) \cap conv(B)\neq \emptyset$. Let $X=\{x_1,\dots,x_n\}\subset\mathbb R^d,$
$n\geq d+2$ be a set of points in general position. For a partition $X=A\cup B$ we define $r_{X}(A,B)$ as the number of $(d+2)$--size subsets $S \subset X$ such that $conv(A\cap S) \cap conv(B \cap S) \neq \emptyset$, that is, the partition $A, B$ induces a Radon partition of $S$. Let  $$r(X)= \max\limits_{ \{ (A, B) | A\cup B = X \}} r_{X}(A,B).$$ We define

$$r(d,n)=\min_{ X \subset \mathbb{R}^d, |X|=n} r(X).$$

\begin{theorem}\label{lem:radon}  Let $d,n\ge 1$ be integers. Then, $$r(d,n)=H_{d'-1}(n,d') \text{ where } d=d'-n+2.$$
\end{theorem}

In order to prove this theorem we need to take a geometric detour on the relationship between faces of convex polytopes, simplices embracing the origin and Radon partitions. There is an old tradition of using Gale transforms to study facets of convex polytopes \cite{GRUN2003}, by studying simplices embracing the origin (this equivalence was further extended by Larman \cite{LARMAN72} to studying Radon partitions of points in space).

Given a finite set of points, $X=\{x_{1}, \ldots,x_{n}\}$ such that the dimension of their affine span is $r$, the set
$D(X)=\{ \alpha=(\alpha_{1},\ldots,\alpha_{n}) | \; \sum_{i=1}^{n}\alpha_{i} x_{i}=0,\; \sum_{i=1}^{n}\alpha_{i}=0 \}\subset \mathbb{R}^{n}$
of its \emph{affine dependences} is of dimension $n-r-1.$ Let $\{a_{i}= (\alpha_{1, i},\ldots,\alpha_{n, i})\}_{i=1}^{n-r-1}$ be a basis of $D(X),$ then the set $\bar X =\{ \bar x_{j}= (\alpha_{j, 1}, \ldots \alpha_{j, n-r-1})\}_{j=1}^{n}$ is a \emph{Gale transform} of $X$.

It is emphasized that $\bar{X}$ is \emph{a} Gale transform of $X,$ rather than \emph{the} Gale transform of $X,$ because the resulting points depend on the specific choice of basis for $D(X).$ Still, different Gale transforms of the same set of points are linearly equivalent.

The \emph{Gale diagram} of $X$
is its normalized Gale transform, that is: the set of points $\hat{X}=\{\hat{x_i}= \frac{\bar{x}_i}{\lVert \bar{x}_i \rVert} \text{ if } \bar{x}_i\neq 0, \hat{x_i}=0 \text{ otherwise} \; | \; \bar{x}_i \in \bar{X}\}\in \mathbb{S}^{n-r-2}.$

We will state some of the properties of Gale transforms and diagrams (we refer the reader to \cite{GRUN2003} for proofs and a full introduction to Gale transforms)

Let ${X}=\{{x_{1}}, \ldots, {x_{n}}\}$ be a set of $n$ points in $\mathbb{R}^{d}$ and let $\hat{X}$ ($\bar X$) be its Gale diagram  (transform), then the following statements hold:

(a) The $n$ points of $X$ are in general position in $\mathbb{R}^{d}$ if and only if the n-tuple $\hat{X}$ ($\bar X$)
consists of $n$ points in linearly general position in $\mathbb{R}^{n-d-1}.$

(b) Faces of $conv(X)$ are in one to one correspondence with simplices of $\hat{X}$ ($\bar {X}$) that contain $0$ in their convex hull. More precisely, $Y \subset X$ is a face of $conv(X)$ iff $0 \in relint \: conv(\hat{X}\setminus \hat{Y})$ ($0 \in relint \: conv(\bar{X}\setminus \bar{Y})$).

(c) $X$ is projectively equivalent to a set of points $Y$ (by a permissible projective transformation) if and only if there is a non zero vector $\epsilon=(\epsilon_{1},\ldots, \epsilon_{n}) \in \{1,-1\}^{n}$ ($\lambda=(\lambda_{1},\ldots, \lambda_{n}) \in \mathbb{R}^{n}$) such that $\hat{y}_i=\epsilon_i \hat{x}_i$ ($\bar{y}_i=\lambda_{i}\bar{x}_i$).

Given a set of $n\geq d+2$ points in general position  $X=\{x_1,\dots,x_n\}\subset\mathbb R^d$ and a partition $A \cup B =X,$ where $A \cap B= \emptyset$ we will construct its \emph{affine projection} into the unit sphere as follows; $\tilde{X}= \{\tilde{x}_i= \mathbf{I}(x_i) \frac{(x_i; 1)}{\lVert (x_i; 1) \rVert} | x_i \in X \} \subset \mathbb{S}^{d},$ where $\mathbf{I}(x_i)=1$ when $x_i \in A$ and  $\mathbf{I}(x_i)=-1$ when $x_i \in B.$ By using basic linear algebra it can be easily be proved that

(d) $A, B$ is a Radon partition of $X$ if and only if $0 \in conv(\tilde{A}\cup \tilde{B}).$

We have gathered now all the tools necessary to prove Theorem \ref{lem:radon}.

\begin{proof}[Proof of Theorem  \ref{lem:radon}.]
By (d) , we know that if we consider the affine projection of $X$ into $\mathbb{S}^{d},$ $\tilde{X},$ we have that $conv(A\cap S) \cap conv(B \cap S) \neq \emptyset$  if and only if $0 \in conv( \tilde{S}).$ So, if we let let $\tilde{X}_\epsilon=\{\epsilon_1 \tilde{x}_1, \ldots, \epsilon_n \tilde{x}_n\}$ for $\epsilon=(\epsilon_1, \ldots, \epsilon_n) \in \{1, -1\}^n$  and  define $\rho(\tilde{X}_\epsilon)$  as the number of subsets $\tilde{S}\subset \tilde{X}_\epsilon$  such that $0 \in conv(\tilde{S})$ and $\rho(\tilde{X})= \max_{\epsilon \in \{1, -1\}^n} {\rho(\tilde{X}_\epsilon)},$ then we can find the value of $\rho(d,n)=\min_{ \{\tilde{X} \subset \mathbb{S}^d, |\tilde{X}|=n\}}\rho(\tilde{X})$. We thus have that $r(d,n)=\rho(d,n)$, we observe that $\tilde{X} \subset \mathbb{S}^{d} \subset \mathbb{R}^{d+1}$ while $X\subset\mathbb R^d.$

Now, recall that the set $\tilde{X} \subset \mathbb{S}^{d}$ can be considered to be the Gale diagram of a set of points in $X' \subset \mathbb R^{n-d-2}$  where each  $\tilde{X}_\epsilon=\{\epsilon_1 \tilde{x}_1, \ldots, \epsilon_n \tilde{x}_n\}$ corresponds to a permissible projective transformation of $X'.$ Therefore, each $(d+2)$--set $ \tilde{S} \subset \tilde{X}$ such that $0 \in conv( \tilde{S})$ is in one to one correspondence with a cofacet of $X'$ (i.e. the corresponding set $X'\setminus S'$ is a facet of $X').$
\end{proof}

As a consequence of Lemma \ref{lem:radon}, together with Corollary \ref{boundsforf_d-1}, we obtain.

{\scriptsize $$r(d,n)\left\{\begin{array}{ll}
=1 & \text{ if } n= d+2,\\
=2 & \text{ if } n= d+3,\\
=5 & \text{ if } n= d+4,\\
\le 10 & \text{ if } n= d+5,\\
\le f_{n-d-3}(C_{n-d-2}(n) & \text{ if }  n\ge 2d+3,\\
\le f_{n-d-3}(C_{n-d-2}(n-1)) & \text{ if }  n \leq \frac{5d+8}{3},\\
\le f_{n-d-3}(C_{n-d-2}(n-2)) & \text{ if } n \leq \frac{5d+6}{3},\\
\le  f_{n-d-3}(C_{n-d-2}(n-(l+2))),\ \  1 \leq l & \text{ if } d+4+ \frac{d-3}{l+2} <  n \leq d+4 +\frac{d-1}{l+1}.\\
\end{array}\right.$$}
Moreover,  $r(d,n)\ge 8$ when $n=d+5$.

The thorough reader may have noticed that we have not addressed yet the second part of Question \ref{question:ps}, that is,

\begin{quote}  is the partition of $X$ balanced when the maximum is attained ? \end{quote}

The following result answers this question negatively.

\begin{theorem} \label{thm:unbalanced}
Let $X\subset \mathbb{R}^d,$ be a set of points in general position, if $A, B$ is a partition such that its number of induced minimal Radon partitions is maximal, then the size of $A$ and $B$ can be as different as possible.
\end{theorem}

\begin{proof}
Let $A,B$ be a partition that attains the maximum number of induced minimal Radon partitions for a set $X,$ $r(X),$ and let $\tilde{X}_\epsilon$ be it's corresponding affine projection, and $X'$ be the point configuration whose Gale diagram is $\tilde{X}_\epsilon$, as defined before.

Note that $X$ will have the maximum number of induced partitions for a set of its size if and only if $X'$ is in the projective class of a neighbourly polytope. This will not be the case in general. Thus we argue that we can have some set, $X,$ that will be in the projective class of a set of points, $X',$ that cannot be made convex by any projective transformation.

In particular, if $X'$ cannot be made convex, there is a point $x'$ in the interior of $conv(X').$ By (b), the set $\tilde{X}_\epsilon \setminus \tilde{x'}$ is such that $0 \not \in conv(\tilde{X}_\epsilon \setminus \tilde{x'}),$ where $\tilde{x'}$  is the  point of $\tilde{X}_\epsilon$ corresponding to $x'.$ Hence, there is a hyperplane $H$ through the origin such that  $H^+ \cap \tilde{X}_\epsilon=\{ \tilde{x'}\}$ and $H^- \cap \tilde{X}_\epsilon=\tilde{X}_\epsilon \setminus \tilde{x'}.$

Now, observe that the affine projection of $X$ was arbitrarily constructed making the hyperplane $aff(X) \subset \mathbb{R}^{d+1}$ be parallel to the hyperplane $x_{d+1}=0.$ However, we can  "lift" the configuration $\tilde{X}_\epsilon \subset \mathbb{R}^{d+1}$ by choosing a hyperplane $H'$  which is parallel to $H$ by translating it in the direction of $H$'s unit normal vector to its "north pole" and then defining $Y=\{y=lin(\tilde{x}) \cap H' | \tilde{x} \in \tilde{X}_\epsilon\},$ where $lin(\tilde{x})$ is the line through the origin and $\tilde{x}.$ Furthermore, we can define a partition $A_Y, B_Y$ of the set $Y$ as follows $y=lin(\tilde{x}) \cap H' \in A_Y$ when $\tilde{x} \in H^+,$ $y \in B_Y$ otherwise. Here $|A_Y|=1$ and $|B_Y|=n-1.$

We claim that the number of induced minimal Radon partitions has to be the same as for $X, A$ and $B,$ i.e. $r(X)=r(Y).$ Recall that a subset $T$ of $Y$ is an induced Radon partition if and only if its corresponding set in $\tilde{X}_\epsilon$ contains the origin. So, no partition of $Y$ can lead to a selection $\epsilon' \in \{1, -1\}^n$ such that the number of simplices embracing the origin for $\tilde{X}_\epsilon'$ will be greater than that of $\tilde{X}_\epsilon,$ because it would contradict the maximality of the selection of $\epsilon.$

So here we have it. We've built a set $Y$ in $\mathbb{R}^d$ and a partition $A_Y, B_Y$ such that its number of induced minimal Radon partitions is maximal but $|A_Y|$ and $|B_Y|$ are as different as they can be.
\end{proof}

Let us highlight the following two facts.

\begin{fact}
The maximum number of minimal Radon partitions induced by a partition into two sets, $A, B$ of a set of points in general position  $X$ depends on the projective class of the set and it is independent of the balance of the cardinality of $A$ and $B.$
\end{fact}

The above follows as the set $X$ and $Y$ in the proof of Theorem \ref{thm:unbalanced} are projectively equivalent.

\begin{fact} If a set of $n$ points in general position $X  \subset \mathbb{R}^d$ is such that its affine projection is in the projective class of a neighbourly polytope then, there is a \emph{balanced} partition $A,B$ such that the number of induced Radon partitions is the maximum possible for a configuration of $n$ points.
\end{fact}

This can be easily argued as follows:

Let $\tilde{X},$ be the affine projection of $X$ and let  $\epsilon \in \{1, -1\}^n$ such that the set $\tilde{X}_\epsilon$ corresponds to the Gale diagram of a neighbourly polytope. Recall that a set of vertices is the face of a polytope if and only if the vertices corresponding to its complement in the Gale diagram contain the origin in its convex hull and that, by definition, every set of $\lfloor \frac{d'}{2}\rfloor$ points is a face of a $d'$--dimensional neighbourly polytope; hence, every plane through the origin $H$ is such that $|H^+ \cap \tilde{X}_\epsilon|>\lfloor \frac{d'}{2}\rfloor$ and $|H^- \cap \tilde{X}_\epsilon|>\lfloor \frac{d'}{2}\rfloor.$

In this case, the dimension of the neighbourly polytope associated to $\tilde{X}_\epsilon$  is $d'=n-d-2.$ If we now construct $A$ and $B$ as usual ($x \in A$ iff $\tilde{x}_\epsilon$ is in the north hemisphere, $x \in B$ otherwise),  the cardinality of both $A$ and $B$ are strictly greater than $\lfloor \frac{n-d-2}{2}\rfloor,$ thus the partition is somewhat balanced.

\section{Concluding remarks}\label{sec:concluding-rem}

Corollary \ref{igualdadv} states that $\bar{n}(2,t)=5+t$ for any $t\ge0$, in other words, any simple arrangement of $n\ge5$ (pseudo) lines in $\mathbb{P}^2$ contains a tope of size at least $5$. Moreover, for each $n\ge5$ there exists an example of a simple arrangement of $n$ hyperplanes with all its topes having size at most $5$.
The latter suggests the following


\begin{question}\label{conjeturav(d,t)=2d+t} Let $d\ge2$ and $t\ge 0$ be integers.
 Is it true that  $\bar{n}(d,t)=2d+1+t?$  In other words, is it true that any simple arrangement of $n\ge 2d+1$ (pseudo) hyperplanes in $\mathbb{P}^d$ contains a tope of size at least $2d+1$
 and conversely, for any $n\ge 2d+1$ there exists a  simple arrangement of $n$ (pseudo) hyperplanes in $\mathbb{P}^d$ with every tope of size at most $2d+1$?
\end{question}

Or, alternatively,

\begin{question}\label{conjeturac(d)} Let $d\ge2$ and $t\ge 0$ be integers.
 Is there a constant $c(d)\ge 1$ such that $\bar{n}(d,t)=2d+1+c(d)t ?$
\end{question}

In the case $d=3$, we know (by Theorem \ref{dimension3}) that $\bar{n}(3,t)\le t+7$ for any integer $t\ge 1$, i.e., for any $n\ge 7$ there exists a  simple arrangement of $n$ (pseudo) hyperplanes in $\mathbb{P}^3$ with every tope of size at most $7$.

\begin{conjecture}\label{questionv(3,t)=t+7}  $\bar{n}(3,t)= t+7$ for any integer $t\ge 1$. In other words,
any simple arrangement of at least $7$ (pseudo) hyperplanes in $\mathbb{P}^3$ always contains a tope of size at least $7$.
\end{conjecture}

\bibliographystyle{amsplain}

2018-10-08T02:11:01.000
1810
1810.02671
en
https://arxiv.org/abs/1810.02671
Let $X$ be a configuration of $n$ points in $\mathbb{R}^d$.What is the maximum number of vertices that $conv(T(X))$ can have among all the possible permissible projective transformations $T$?In this paper, we investigate this and connected questions. After presenting several upper bounds, we study a closely related problem (via Gale transforms) concerning the number of minimal Radon partitions of a set of points. We then present some bounds for this number that enable us to partially answer a question due to Pach and Szegedy. We also discuss another related problem concerning the size of topes in arrangements of hyperplanes.
Combinatorics (math.CO)
On the number of vertices of projective polytopes
Qwen/Qwen-72B
1. YES
2. YES