# Hausdorff dimension of unions of $k$-planes

Shengwen Gan  Department of Mathematics
Massachusetts Institute of Technology
Cambridge, MA 02142-4307, USA<EMAIL_ADDRESS>
###### Abstract.

We prove a conjecture of Héra on the dimension of unions of $k$-planes. Let
$0<k\leq d<n$ be integers, and $\beta\in[0,k+1)$. If $\mathcal{V}\subset
A(k,n)$, with $\textup{dim}(\mathcal{V})=(k+1)(d-k)+\beta$, then
$\textup{dim}(\bigcup_{V\in\mathcal{V}}V)\geq d+\min\\{1,\beta\\}$. The proof
combines a recent idea of Zahl and the Brascamp-Lieb inequality.

###### Key words and phrases:

radial projection, exceptional estimate

###### 2020 Mathematics Subject Classification:

28A75, 28A78

##  1\. Introduction

In [3], Héra made the following conjecture (see Conjecture 1.16 in [3]). We
slightly change the notation and state it in the following equivalent way.

######  Conjecture 1.

Let $0<k\leq d<n$ be integers and $\beta\in[0,k+1]$. Let $\mathcal{V}\subset
A(k,n)$ be a set of $k$-planes in $\mathbb{R}^{n}$, with
$\dim(\mathcal{V})=(k+1)(d-k)+\beta$. Here, $A(k,n)$ denotes the affine
Grassmannian in $\mathbb{R}^{n}$ and $\dim(\mathcal{V})$ means the Hausdorff
dimension of $\mathcal{V}$ as a subset of the Riemannian manifold $A(k,n)$.
Then,

(1) $\dim(\bigcup_{V\in\mathcal{V}}V)\geq d+\min\\{1,\beta\\}.$

There are many works related to Conjecture 1. See for example [3], [4], [6],
[7] and [8]. We refer to [8] for a detailed introduction on this problem.

###  1.1. Sharp examples

We first give some examples to show (1) is sharp, i.e., we will find
$\mathcal{V}\subset A(k,n)$ with $\dim(\mathcal{V})=(k+1)(d-k)+\beta$, so that

$\dim(\bigcup_{V\in\mathcal{V}}V)\leq d+\min\\{1,\beta\\}.$

Our examples $V\in\mathcal{V}$ will lie in
$\mathbb{R}^{d+1}(\subset\mathbb{R}^{n})$.

  * •

When $\beta\in[1,k+1]$, let $\mathcal{V}$ be a
$((k+1)(d-k)+\beta)$-dimensional subset of $A(k,d+1)$. This is allowable since
$\dim(A(k,d+1))=(k+1)(d+1-k)\geq(k+1)(d-k)+\beta$. Since every
$V\in\mathcal{V}$ is contained in $\mathbb{R}^{d+1}$, we have
$\dim(\bigcup_{V\in\mathcal{V}}V)\leq\dim(\mathbb{R}^{d+1})=d+1$.

  * •

When $\beta\in[0,1]$, we choose $I\subset\mathbb{R}$ to be a
$\beta$-dimensional set. Let

$\mathcal{V}=\cup_{a\in I}A(k,\mathbb{R}^{d}+(0,\dots,0,a)).$

Here, $A(k,\mathbb{R}^{d}+(0,\dots,0,a))$ is the set of $k$-planes that are
contained in the space $\mathbb{R}^{d}+(0,\dots,0,a)$. We see that
$\dim(\mathcal{V})=\dim I+\dim A(k,d)=(k+1)(d-k)+\beta$, and
$\dim(\bigcup_{V\in\mathcal{V}}V)=\dim(\mathbb{R}^{d}\times I)=d+\beta$.

###  1.2. Some notations

We introduce some notations that are needed for the later discussions.

Let $G(k,n)$ be the set of $k$-dimensional subspaces in $\mathbb{R}^{n}$. For
every $k$-plane $V$, we can uniquely write it as

$V=\textup{dir}(V)+x_{V},$

where $\textup{dir}(V)\in G(k,n)$ and $x_{V}\in V^{\perp}$. $\textup{dir}(V)$
refers to the direction of $V$, as can be seen that
$\textup{dir}(V)=\textup{dir}(V^{\prime})\Leftrightarrow V\parallel
V^{\prime}$.

In this paper, we use $A(k,n)$ to denote the set of $k$-planes $V$ such that
$x_{V}\in B^{n}(0,1/2)$. ($B^{n}(0,1/2)$ is the ball of radius $1/2$ centered
at the origin in $\mathbb{R}^{n}$.)

$A(k,n)=\\{V:V\textup{~{}is~{}a~{}}k\textup{~{}dimensional~{}plane~{}},x_{V}\in
B^{n}(0,1/2)\\}.$

Usually $A(k,n)$ denotes all the $k$-planes in other references, but for our
purpose we only care about those $V$ that lie near the origin.

Next, we discuss the metrics on $G(k,n)$ and $A(k,n)$. For $V_{1},V_{2}\in
G(k,n)$, we define

$d(V_{1},V_{2})=\|\pi_{V_{1}}-\pi_{V_{2}}\|.$

Here, $\pi_{V_{1}}:\mathbb{R}^{n}\rightarrow V_{1}$ is the orthogonal
projection. We have another characterization for this metric. Define
$\rho(V_{1},V_{2})$ to be the smallest number $\rho$ such that $B^{n}(0,1)\cap
V_{1}\subset N_{\rho}(V_{2})$. We have the comparability of $d(\cdot,\cdot)$
and $\rho(\cdot,\cdot)$.

######  Lemma 1.

There exists a constant $C>0$ (depending on $k,n$) such that

$\rho(V_{1},V_{2})\leq d(V_{1},V_{2})\leq C\rho(V_{1},V_{2}).$

###### Proof.

Suppose $B^{n}(0,1)\cap V_{1}\subset N_{\rho}(V_{2})$, then for any
$v\in\mathbb{R}^{n}$, we have

$|\pi_{V_{1}}(v)-\pi_{V_{2}}(v)|\lesssim\rho|v|,$

which implies $d(V_{1},V_{2})\lesssim\rho$. On the other hand, if for any
$|v|\leq 1$ we have

$|\pi_{V_{1}}(v)-\pi_{V_{2}}(v)|\leq d|v|,$

then we obtain that $\pi_{V_{1}}(v)\subset N_{d}(V_{2})$. Letting $v$ ranging
over $B^{n}(0,1)\cap V_{1}$, we get $B^{n}(0,1)\cap V_{1}\subset
N_{d}(V_{2})$, which means $\rho(V_{1},V_{2})\leq d$. ∎

We can also define the metric on $A(k,n)$ given by

(2)
$d(V,V^{\prime})=d(\textup{dir}(V),\textup{dir}(V^{\prime}))+|x_{V}-x_{V^{\prime}}|.$

Here, we still use $d$ to denote the metric on $A(k,n)$ and it will not make
any confusion.

Similarly, for $V,V^{\prime}\in A(k,n)$ we can define $\rho(V,V^{\prime})$ to
be the smallest number $\rho$ such that $B^{n}(0,1)\cap V\subset
N_{\rho}(V^{\prime})$. We also have the following lemma. We left the proof to
the interested readers.

######  Lemma 2.

There exists a constant $C>0$ (depending on $k,n$) such that for
$V,V^{\prime}\in A(k,n)$,

$C^{-1}d(V,V^{\prime})\leq\rho(V,V^{\prime})\leq Cd(V,V^{\prime}).$

######  Definition 3.

For $V\in A(k,n)$ and $0<r<1$, we define

$V_{r}:=N_{r}(V)\cap B^{n}(0,1).$

We see that $V_{r}$ is morally a slab of dimensions
$\underbrace{r\times\dots\times
r}_{k\textup{~{}times}}\times\underbrace{1\times\dots\times
1}_{n-k\textup{~{}times}}$. We usually call $V_{r}$ a $k$-dimensional
$r$-slab. When $k$ is already clear, we simply call $V_{r}$ an $r$-plank. If
$W$ is a convex set such that $C^{-1}W\subset V_{r}\subset CW$, then we also
call $W$ an $r$-plank. Here, the constant $C$ will be a fixed large constant.

######  Definition 4.

For two $r$-plank $V_{r}$ and $V^{\prime}_{r}$. We say they are comparable if
$C^{-1}V_{r}\subset V^{\prime}_{r}\subset CV_{r}$. We say they are essentially
distinct if they are not comparable.

In this paper, we will also consider the balls and $\delta$-neighborhood on
$A(k,n)$. Recall that we use $B_{r}(x)$ to denote the ball in $\mathbb{R}^{n}$
of radius $r$ centered at $x$. To distinguish the ambient space, we will use
letter $Q$ to denote the balls in $A(k,n)$. For $V\in A(k,n)$, we use
$Q_{r}(V)$ to denote the ball in $A(k,n)$ of radius $r$ centered at $V$. More
precisely,

$Q_{r}(V_{0}):=\\{V\in A(k,n):d(V,V_{0})\leq r\\}.$

For a subset $X\subset A(k,n)$, we use the fancy letter $\mathcal{N}$ to
denote the neighborhood in $A(k,n)$:

$\mathcal{N}_{r}(X):=\\{V\in A(k,n):d(V,X)\leq r\\}.$

Here, $d(V,X)=\inf_{V^{\prime}\in X}d(V,V^{\prime})$.

Next, we briefly recall how to define the Hausdorff dimension for subsets of a
metric space. Let $(M,d)$ be a metric space. For $X\subset M$, we denote the
$s$-dimensional Hausdorff measure of $X$ under the metric $d$ to be
$\mathcal{H}^{s}(X;d)$. We see that if $d^{\prime}$ is another metric on $M$
such that $d(\cdot,\cdot)\sim d^{\prime}(\cdot,\cdot)$, then
$\mathcal{H}^{s}(X;d)\sim\mathcal{H}^{s}(X;d^{\prime})$. It make sense to
define the Hausdorff dimension of $X$ which is independent of the choice of
comparable metrics:

$\dim X:=\sup\\{s:\mathcal{H}^{s}(X;d)>0\\}.$

Throughout the paper we will work with the metric space $M=A(k,n)$ and the
metric $d$ defined as in (2). For any $X\subset A(k,n)$, we will simply denote
the $s$-dimensional Hausdorff measure of $X$ under the metric $d$ to be
$\mathcal{H}^{s}(X)$. Similarly, we use $\mathcal{H}^{s}_{\infty}(X)$ to
denote the Hausdorff content.

###  1.3. Strategy of proof

Our proof will follow the idea of Zahl [8]. The main goal is to prove a Kakeya
maximal estimate for $k$-planes, and then as a corollary we can prove
Conjecture 1. To handle with the $k$-planes rather than lines, we need to use
the Brascamp-Lieb inequality, which can be viewed as a generalized version of
the $k$-linear Kakeya estimate. We state our Kakeya maximal estimate for
$k$-planes. This can be viewed as a counterpart of Theorem 1.2 in [8].

######  Theorem 5.

Let $0<k\leq d<n$ be integers and $\beta\in[0,1]$. Let $\mathcal{V}=\\{V\\}$
be a subset of $A(k,n)$. Suppose that for all balls $Q_{r}\subset A(k,n)$ of
radius $r\in[\delta,1]$, we have

(3) $\\#\\{V\in\mathcal{V}:V\in Q_{r}\\}\leq(r/\delta)^{(k+1)(d-k)+\beta}.$

Then

(4) $\|\sum_{V\in\mathcal{V}}1_{V_{\delta}}\|_{L^{p}(B^{n}(0,1))}\leq
C_{\varepsilon}\delta^{-\frac{k(d-k)}{p^{\prime}}-\varepsilon}\big{(}\sum_{V\in\mathcal{V}}|V_{\delta}|\big{)}^{1/p}.$

Here,

$p=\min\left\\{\frac{d-k+\beta+1}{d-k+\beta},\frac{d+\beta}{d+\beta-(d-k+2)^{-1}}\right\\}$

is a number strictly bigger than $1$.

######  Remark 6.

For our range of $p$, the factor $\delta^{-\frac{k(d-k)}{p^{\prime}}}$ (up to
the $\varepsilon$ loss) on the right hand side of (4) is sharp. Otherwise, it
would give a better lower bound in (1) which is impossible. The author is able
to prove a sharp estimate for $p$ close to $1$. An interesting question would
be to find the sharp factor $\delta^{-C_{p}}$ for all $p\geq 1$.

The main idea in the proof of Theorem 5 is the Broad-Narrow method, which
dates back to [1]. Let us look at the left hand side of (4). We first
partition the integration domain $B^{n}(0,1)$ into $\delta$-balls. For each
such $\delta$-ball $B_{\delta}$, consider all the $V_{\delta}$ that intersect
$B_{\delta}$. We can morally view these $V_{\delta}$ as a subset of $G(k,n)$.
Here is the dichotomy: If there are not too “many” $V_{\delta}$ intersecting
$B_{\delta}$, then we say we are in the narrow case and it can be dealt with
by the induction. If there are “many” $V_{\delta}$ intersecting $B_{\delta}$,
then most of these $V_{\delta}$ are transverse to each other and we say we are
in the broad case; the broad case is dealt with by the Brascamp-Lieb
inequality. We will quantify the “many” in the next section.

In Section 2, we prove theorem 5. In Section 3, we prove that Theorem 5
implies Conjecture 1.

Acknowledgement. The author would like to thank Josh Zahl for helpful
discussions.

##  2\. Proof of Theorem 5

In this section we will use the Broad-Narrow method developed by Bourgain and
Guth [1]. To estimate the left hand side of (4), we will decompose the
integral into broad part and narrow part. The broad part will be handled by
the Brascamp-Lied inequality, and the narrow part will be handled by the
induction.

###  2.1. Brascamp-Lieb inequality

The version of Brascamp-Lieb inequality we are going to use is due to
Maldague. See Theorem 2 in [5].

######  Theorem 7 (Maldague).

Consider in $\mathbb{R}^{n}$. Let $W_{j}\subset G(n-k,n)$ for $j=1,\dots,J$.
Fix $p\in[1,\infty)$. Define

(5) $\textup{BL}(\\{W_{j}\\}_{j=1}^{J},p):=\sup_{L\leq\mathbb{R}^{n}}(\dim
L-\frac{p}{J}\sum_{j=1}^{J}\dim\pi_{W_{j}}(L)).$

Here, $L\leq\mathbb{R}^{n}$ means $L$ is a subspace of $\mathbb{R}^{n}$, and
$\pi_{W_{j}}:\mathbb{R}^{n}\rightarrow W_{j}$ is the orthogonal projection.

There exists $\nu>0$ depending on $\\{W_{j}\\}_{j=1}^{J}$, so that the
following is true. For any $\mathcal{V}_{j}=\\{V_{j}\\}\subset A(k,n)\
(j=1,\dots,J)$ being sets of $k$-planes, such that each
$V_{j}\in\mathcal{V}_{j}$ has its $k$ longest directions orthogonal to some
$W\in Q_{\nu}(W_{j})$, we have

(6)
$\int_{[-1,1]^{n}}\prod_{j=1}^{J}\bigg{(}\sum_{V_{j}\in\mathcal{V}_{j}}1_{V_{j,\delta}}\bigg{)}^{\frac{p}{J}}\lesssim\delta^{n-\varepsilon}\delta^{-\textup{BL}(\\{W_{j}\\}_{j=1}^{J},p)}\prod_{j=1}^{J}\bigg{(}\\#\mathcal{V}_{j}\bigg{)}^{\frac{p}{J}}.$

By a compactness argument, we deduce the following result.

######  Theorem 8.

Consider in $\mathbb{R}^{n}$. Let $\mathcal{W}_{j}\subset G(n-k,n)$ be a
compact set for $j=1,\dots,J$. Fix $p\in[1,\infty)$. Define

(7)
$\textup{BL}(\\{\mathcal{W}_{j}\\}_{j=1}^{J},p):=\sup_{W_{1}\in\mathcal{W}_{1},\dots,W_{J}\in\mathcal{W}_{J}}\textup{BL}(\\{W_{j}\\}_{j=1}^{J},p).$

Then for any $\mathcal{V}_{j}=\\{V_{j}\\}\subset A(k,n)\ (j=1,\dots,J)$ being
sets of $k$-planes, such that each $V_{j}\in\mathcal{V}_{j}$ has its $k$
longest directions orthogonal to some $W\in\mathcal{W}_{j}$, we have

(8)
$\int_{[-1,1]^{n}}\prod_{j=1}^{J}\bigg{(}\sum_{V_{j}\in\mathcal{V}_{j}}1_{V_{j,\delta}}\bigg{)}^{\frac{p}{J}}\leq
C(\\{\mathcal{W}_{j}\\},p,\varepsilon)\cdot\delta^{n-\varepsilon}\delta^{-\textup{BL}((\mathcal{W}_{j})_{j=1}^{J},p)}\prod_{j=1}^{J}\bigg{(}\\#\mathcal{V}_{j}\bigg{)}^{\frac{p}{J}}.$

###  2.2. Broad-narrow reduction

We discuss the broad-narrow reduction in this subsection. There are some
important submanifolds of $G(k,n)$ which resemble the great $(d-1)$-sphere
$S^{d-1}$ in $S^{n-1}\simeq G(1,n)$. For any $d$-dimensional subspace
$\Pi\subset\mathbb{R}^{n}$, let $G(k,\Pi)$ be the set of $k$-dimensional
subspaces that are contained in $\Pi$. We see that $\dim G(k,\Pi)=k(d-k)$.

Choose $\mathcal{D}\subset G(k,n)$ to be a maximal $\delta$-separated subset.
We first modify the directions of the $k$-planes in $\mathcal{V}$ so that they
have directions in $\mathcal{D}$. For each $V\in\mathcal{V}$, we can find
another $V^{\prime}$ so that $\textup{dir}(V^{\prime})=D$ and
$V_{\delta}\subset V^{\prime}_{10\delta}$. We denote the new set of planes
$\\{V^{\prime}\\}$ obtained in this way by $\mathcal{V}^{\prime}$, then

(9)
$\|\sum_{V\in\mathcal{V}}1_{V_{\delta}}\|_{L^{p}(B^{n}(0,1))}^{p}\leq\|\sum_{V^{\prime}\in\mathcal{V}^{\prime}}1_{V^{\prime}_{10\delta}}\|_{L^{p}(B^{n}(0,1))}^{p}.$

We cover $B(0,1)$ by finitely overlapping $\delta$-balls $\\{B_{\delta}\\}$.
We bound the right hand side of (9) as

$\|\sum_{V\in\mathcal{V}^{\prime}}1_{V_{10\delta}}\|_{L^{p}(B^{n}(0,1))}^{p}\leq\sum_{B_{\delta}}\|\sum_{V\in\mathcal{V}^{\prime}}1_{V_{10\delta}}\|_{L^{p}(B_{\delta})}^{p}.$

Here, Since each plank has thickness $\delta$, we just estimate the quantity
above as

$\lesssim\sum_{B_{\delta}}\\#\\{V\in\mathcal{V}^{\prime}:V_{10\delta}\cap
B_{\delta}\neq\emptyset\\}^{p}\delta^{n}.$

Fix a $B_{\delta}$, and let

$\mathcal{V}^{\prime}(B_{\delta}):=\\{V\in\mathcal{V}^{\prime}:V_{10\delta}\cap
B_{\delta}\neq\emptyset\\}.$

Our goal is to find an upper bound of $\\#\mathcal{V}^{\prime}(B_{\delta})$.
Since the planes in $\mathcal{V}^{\prime}(B_{\delta})$ are $\delta$-separated
and intersect $B_{11\delta}$, for any direction in $\mathcal{D}$ there are
$\lesssim 1$ planes in $\mathcal{V}^{\prime}(B_{\delta})$ that are in that
direction. We can choose a subset
$\mathcal{V}(B_{\delta})\subset\mathcal{V}^{\prime}(B_{\delta})$, so that any
two planes in $\mathcal{V}(B_{\delta})$ have different directions and

$\\#\mathcal{V}(B_{\delta})\gtrsim\\#\mathcal{V}^{\prime}(B_{\delta}).$

Therefore, we bound the left hand side of (9) by

$\lesssim\sum_{B_{\delta}}\\#\mathcal{V}(B_{\delta})^{p}\delta^{n}.$

Since the planes in $\mathcal{V}(B_{\delta})$ morally pass through
$B_{\delta}$ and have $\delta$-separated directions, we can view
$\mathcal{V}(B_{\delta})$ as a $\delta$-separated subset of $G(k,n)$.

Fix a $B_{\delta}$, there is a dichotomy to estimate
$\\#\mathcal{V}(B_{\delta})$. The first scenario is when there exists a
$d$-dimensional subspace $\Pi\in G(d,n)$ so that most of the elements
$V\in\mathcal{V}(B_{\delta})$ lie close to $G(k,\Pi)$ (if we view $V$ as a
point in $G(k,n)$), or equivalently most of the elements
$V\in\mathcal{V}(B_{\delta})$ lie in a small neighborhood of
$\Pi(\subset\mathbb{R}^{n})$ (if we view $V$ as a $k$-plane in
$\mathbb{R}^{n}$). The second scenario is that we can find several “quite
transverse” patches $\mathcal{U}_{1},\dots,\mathcal{U}_{J}\subset G(k,n)$ so
that
$\\#(\mathcal{U}_{j}\cap\mathcal{V}(B_{\delta}))\gtrsim\\#\mathcal{V}(B_{\delta})$
for $j=1,\dots,J$. The transverse condition on the patches allows us to use
Theorem 8. We call the first scenario narrow case, and the second scenario
broad case. We make our heuristic rigorous as follows.

Fix a large number $K>>1$ which is to be determined later. We cover $G(k,n)$
by $\mathcal{Q}_{K^{-n}}=\\{Q_{K^{-n}}\\}$ which are balls of radius $K^{-n}$
with bounded overlaps:

$G(k,n)=\bigcup Q_{K^{-n}}.$

Note that $\\#\mathcal{Q}_{K^{-n}}\lesssim(K^{n})^{\dim G(k,n)}\leq
K^{n^{3}}$. We define the significant balls

$\mathcal{Q}^{\prime}=\\{Q_{K^{-n}}:\\#(Q_{K^{-n}}\cap\mathcal{V}(B_{\delta}))\geq\frac{1}{K^{n^{4}}}\\#\mathcal{V}(B_{\delta})\\}.$

We have

$\\#\mathcal{V}(B_{\delta})\leq\frac{1}{2}\sum_{Q_{K^{-n}}\in\mathcal{Q}^{\prime}}\\#(Q_{K^{-n}}\cap\mathcal{V}(B_{\delta})).$

Next by pigeonhole principle, there is a subset of $\mathcal{Q}^{\prime}$
denoted by $\mathcal{Q}$, such that the balls in $\mathcal{Q}$ are
$100K^{-n}$-separated, $\\#(Q_{K^{-n}}\cap\mathcal{V}(B_{\delta}))$ are all
comparable for $Q_{K^{-n}}\in\mathcal{Q}$, and

$\\#\mathcal{V}(B_{\delta})\lesssim\log
K\sum_{Q_{K^{-n}}\in\mathcal{Q}}\\#(Q_{K^{-n}}\cap\mathcal{V}(B_{\delta})).$

There is the dichotomy:

The first scenario: We say it is in the narrow case when there exists $\Pi\in
G(d,n)$ so that half of balls in $\mathcal{Q}$ is contained in
$\mathcal{N}_{CK^{-1}}(G(k,\Pi))$. Here, we view $G(k,\Pi)$ as a subset of
$G(k,n)$ and $\mathcal{N}_{CK^{-1}}(G(k,\Pi))$ is the $CK^{-1}$-neighborhood
of $G(k,\Pi)$ in $G(k,n)$.

The second scenario: We say it is in the broad case when there exists

$\mathcal{U}_{k},\dots,\mathcal{U}_{d+1}\in\mathcal{Q},$

so that there does not exists a $\Pi\in G(d,n)$ such that all of these
$\mathcal{U}_{j}$ intersect $\mathcal{N}_{100K^{-n}}(G(k,\Pi))$. In other
words, for any $\Pi\in G(d,n)$, there exists a $\mathcal{U}_{j}$ that does not
intersect $\mathcal{N}_{100K^{-n}}(G(k,\Pi))$. We remark that the subscript of
$\mathcal{U}_{j}$ ranges from $k$ to $d+1$ but not from $1$ to $d-k+2$, just
to make the discussion below more convenient.

We want to show that if we are not in the first scenario, then we are in the
second scenario. We let $\mathcal{G}$ be the set of centers of the balls in
$\mathcal{Q}$, i.e.,

$\mathcal{Q}=\\{Q_{K^{-n}}(U):U\in\mathcal{G}\\}.$

We just need to show there exists $U_{k},\dots,U_{d+1}\in\mathcal{G}$ so that
there does not exists a $\Pi\in G(d,n)$ such that these $U_{j}$ are contained
in $\mathcal{N}_{200K^{-n}}(G(k,\Pi))$.

This is done in the following way. We first choose a $U_{k}\in\mathcal{G}$ and
choose $v_{1},\dots,v_{k}$ to be the orthonormal basis of $U_{1}$. Next, we
will inductively construct $\mathcal{U}_{j}$ for $k<j\leq d+1$ and a unit
vector $v_{j}\in U_{j}$ so that the $j$-dimensional rectangle spanned by
$v_{1},\dots,v_{j}$ has volume bigger than $K^{-j}$. Suppose we have
constructed $\mathcal{U}_{1},\dots,\mathcal{U}_{j-1}$ and
$v_{1},\dots,v_{j-1}$ with $\textup{Vol}_{j-1}(v_{1},\dots,v_{j-1})\geq
K^{j-1}$. Denote the $(j-1)$-dimensional plane
$\textup{span}\\{v_{1},\dots,v_{j-1}\\}$ by $\Pi_{j-1}$. For any
$U\in\mathcal{G}$, consider its relative position with $\Pi_{j-1}$. The key
observation is that: If any unit vector $v\in U$ is contained in the
$K^{-1}$-neighborhood of $\Pi_{j-1}$, then $U$, as an element in $G(k,n)$, is
contained in $\mathcal{N}_{CK^{-1}}(G(k,\Pi_{j-1}))$. The proof is as follows.
If any unit vector $v\in U$ is contained in the $K^{-1}$-neighborhood of
$\Pi_{j-1}$, then if we view $U$ and $\Pi_{j-1}$ as subsets of
$\mathbb{R}^{n}$, we see that $B(0,1)\cap U$ is contained in the
$K^{-1}$-neighborhood of $\Pi_{j-1}$. If we denote the orthogonal projection
of $U$ to $\Pi_{j-1}$ by $U^{\prime}$, then $B(0,1)\cap U$ is contained in the
$K^{-1}$-neighborhood of $U^{\prime}$. By Lemma 2, $d(U,U^{\prime})\lesssim
K^{-1}$. Since $U^{\prime}\in G(k,\Pi_{j-1})$, we have
$d(U,G(k,\Pi_{j-1}))\lesssim K^{-1}$. In other words, all the
$\mathcal{U}\in\mathcal{Q}$ are contained in
$\mathcal{N}_{CK^{-1}}(G(k,\Pi_{j-1}))$, meaning that we are in the first
scenario.

Let us summarize the result. Let $\mathcal{Q}_{K^{-1}}=\\{Q_{K^{-1}}\\}$ be a
covering of $G(k,n)$ by $K^{-1}$-balls. If we are in the first scenario (broad
case), then there exists $\Pi\in G(d,n)$ such that

$\\#\mathcal{V}(B_{\delta})\lesssim\log
K\sum_{Q_{K^{-1}}\subset\mathcal{N}_{CK^{-1}}(G(k,\Pi))}\\#(Q_{K^{-1}}\cap\mathcal{V}(B_{\delta})).$

Since $G(k,\Pi)$ is a $k(d-k)$-dimensional submanifold of $G(k,n)$, we have

$\\#\\{Q_{K^{-1}}\subset\mathcal{N}_{CK^{-1}}(G(k,\Pi))\\}\lesssim
K^{k(d-k)}.$

Therefore, we have

(10) $\\#\mathcal{V}(B_{\delta})^{p}\lesssim K^{k(d-k)(p-1)}(\log
K)^{p}\sum_{Q_{K^{-1}}\in\mathcal{Q}_{K^{-1}}}\\#(Q_{K^{-1}}\cap\mathcal{V}(B_{\delta}))^{p}.$

We discuss the bound we have in the second scenario. Let
$\mathcal{Q}_{K^{-n}}$ be a set of $K^{-n}$-cubes that form a partition of
$G(k,n)$. Define the following transverse $(d-k+2)$-tuples

(11)
$\displaystyle\textup{Trans}^{d-k+2}:=\\{(\mathcal{U}_{k},\dots,\mathcal{U}_{d+1})\in\mathcal{Q}_{K^{-n}}^{d-k+2}:\mathcal{U}_{k},\dots,\mathcal{U}_{d+1}\textup{~{}do~{}not~{}simultaneously}$
$\displaystyle\textup{~{}interset~{}}\mathcal{N}_{100K^{-n}}(G(k,\Pi))\textup{~{}for~{}any~{}}\Pi\in
G(d,n)\\}.$

Then if we are in the second scenario, we have

(12) $\\#\mathcal{V}(B_{\delta})\lesssim
K^{O(n^{10})}\sum_{(\mathcal{U}_{k},\dots,\mathcal{U}_{d+1})\in\textup{Trans}^{d-k+2}}\prod_{j=k}^{d+1}(\\#\mathcal{U}_{j}\cap\mathcal{V}(B_{\delta}))^{\frac{1}{d-k+2}}.$

Combining the broad case and narrow case, we obtain the following estimate.

(13) $\displaystyle\\#\mathcal{V}(B_{\delta})^{p}\lesssim K^{k(d-k)(p-1)}(\log
K)^{p}\sum_{Q_{K^{-1}}\in\mathcal{Q}_{K^{-1}}}\\#(Q_{K^{-1}}\cap\mathcal{V}(B_{\delta}))^{p}$
(14)
$\displaystyle+K^{pK^{n^{3}}}\sum_{(\mathcal{U}_{k},\dots,\mathcal{U}_{d+1})\in\textup{Trans}^{d-k+2}}\prod_{j=k}^{d+1}(\\#\mathcal{U}_{j}\cap\mathcal{V}(B_{\delta}))^{\frac{p}{d-k+2}}.$

######  Remark 9.

(14) is obtained by using triangle inequality which results in a huge constant
$K^{pK^{n^{3}}}$ depending on $K$. This constant comes from
$\\#\\{(\mathcal{U}_{k},\dots,\mathcal{U}_{d+1})\in\textup{Trans}^{d-k+2}\\}$.
However, it is allowable since it does not depend on $\delta$.

Summing over $B_{\delta}$ and noting that each $V_{\delta}$ is roughly
constant on any ball of radius $\delta$, we obtain

(15) $\displaystyle\|\sum_{V\in\mathcal{V}}1_{V_{\delta}}\|_{p}^{p}\lesssim
K^{k(d-k)(p-1)}(\log
K)^{p}\sum_{Q_{K^{-1}}\in\mathcal{Q}_{K^{-1}}}\|\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}}}1_{V_{20\delta}}\|_{p}^{p}$ (16)
$\displaystyle+C_{K}\sum_{(\mathcal{U}_{k},\dots,\mathcal{U}_{d+1})\in\textup{Trans}^{d-k+2}}\int_{[-1,1]^{n}}\prod_{j=k}^{d+1}(\sum_{V\in\mathcal{V},\textup{dir}(V)\in\mathcal{U}_{j}}1_{V_{20\delta}})^{\frac{p}{d-k+2}}.$

To ease the notation, we may replace $V_{20\delta}$ on the right hand side by
$V_{\delta}$. This may cost a lose of some constant factor, which is
allowable. Therefore, we can assume we have

(17) $\displaystyle\|\sum_{V\in\mathcal{V}}1_{V_{\delta}}\|_{p}^{p}\lesssim
K^{k(d-k)(p-1)}(\log
K)^{p}\sum_{Q_{K^{-1}}\in\mathcal{Q}_{K^{-1}}}\|\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}}}1_{V_{\delta}}\|_{p}^{p}$ (18)
$\displaystyle+C_{K}\sum_{(\mathcal{U}_{k},\dots,\mathcal{U}_{d+1})\in\textup{Trans}^{d-k+2}}\int_{[-1,1]^{n}}\prod_{j=k}^{d+1}(\sum_{V\in\mathcal{V},\textup{dir}(V)\in\mathcal{U}_{j}}1_{V_{\delta}})^{\frac{p}{d-k+2}}=:\textup{I}+\textup{II}.$

Next, we will estimate I and II separately. We first look at II. Let
$J=d-k+2$. For each $\mathcal{U}_{j}$ ($k\leq j\leq d+1$), let
$\mathcal{W}_{j}=\\{W^{\perp}:W\in\mathcal{U}_{j}\\}$. We see that
$\mathcal{W}_{j}\subset G(n-k,n)$. For simplicity, we denote the Brascamp-Lieb
constant (see (7) and (5)) by

(19) $\textup{BL}:=\textup{BL}((\mathcal{W}_{j})_{j=1}^{J},p).$

By Theorem 8, we have

(20)
$\int_{[-1,1]^{n}}\prod_{j=k}^{d+1}(\sum_{V\in\mathcal{V},\textup{dir}(V)\in\mathcal{U}_{j}}1_{V_{\delta}})^{\frac{p}{d-k+2}}\lesssim\delta^{n-\varepsilon^{2}}\delta^{-\textup{BL}}\prod_{j=1}^{J}\bigg{(}\\#\mathcal{U}_{j}\cap\mathcal{V}\bigg{)}^{\frac{p}{J}}\leq\delta^{n-\varepsilon^{2}-\textup{BL}}(\\#\mathcal{V})^{p}.$

Here, the implicit constant depends on $\varepsilon$ and
$\\{\mathcal{W}_{j}\\}$. $\\{\mathcal{W}_{j}\\}$ further depends on the
covering $\mathcal{Q}_{K^{-n}}$. Since this covering is at the scale $K^{-n}$,
we can simply denote this implicit constant by $C_{K,\varepsilon}$. Also, we
choose $\delta^{-\varepsilon^{2}}$ instead of $\delta^{-\varepsilon}$ is to
close the induction later.

Therefore,

$\textup{II}\leq
C_{K,\varepsilon}\delta^{n-\varepsilon^{2}-\textup{BL}}(\\#\mathcal{V})^{p}.$

Here, $C_{K}$ may be another constant different from that in (18). We claim
that

(21)
$\delta^{n-\textup{BL}}(\\#\mathcal{V})^{p}\lesssim\delta^{-k(d-k)(p-1)}\sum_{V\in\mathcal{V}}|V_{\delta}|.$

To prove this inequality, we first note that $|V_{\delta}|\sim\delta^{n-k}$
and by (3) that $\\#\mathcal{V}\leq\delta^{-(k+1)(d-k)+\beta}$. Therefore,
(21) is equivalent to

$\delta^{n-\textup{BL}}\delta^{-\big{(}(k+1)(d-k)+\beta\big{)}(p-1)}\lesssim\delta^{-k(d-k)(p-1)}\delta^{n-k}.$

It suffices to prove

(22) $\textup{BL}\leq d+\beta-(d-k+\beta)p.$

Recall the definition of BL in (19). We may assume

$\textup{BL}=\sup_{L\leq\mathbb{R}^{n}}\bigg{(}\dim
L-\frac{p}{J}\sum_{j=k}^{d+1}\dim\pi_{W_{j}}(L)\bigg{)},$

where $W_{j}\in\mathcal{W}_{j}$. We remind the reader that
$\\{W_{j}\\}_{j=k}^{d+1}$ satisfy an important property: any $\Pi\in G(d,n)$
does not contain all the $W_{j}^{\perp}$. We will also use the following
result.

######  Lemma 10.

Let $W,L\leq\mathbb{R}^{n}$ be two subspaces and $\dim L+\dim W\geq n$. Then,

$\dim\pi_{W}(L)\geq\dim W+\dim L-n.$

The equality holds if and only if $L\supset W^{\perp}$. If $L\not\supset
W^{\perp}$, then

$\dim\pi_{W}(L)\geq\dim W+\dim L-n+1.$

###### Proof.

We just look at the linear map $\pi_{W}|_{L}:L\rightarrow\pi_{W}(L)$. We have
$\dim(\pi_{W}(L))=\dim(L)-\dim\textup{Ker}(\pi_{W}|_{L})$. We note that
$\dim\textup{Ker}(\pi_{W}|_{L})\leq\dim\textup{Ker}(\pi_{W})=n-\dim W$, and
$\dim\textup{Ker}(\pi_{W}|_{L})=\dim\textup{Ker}(\pi_{W})$ if and only if
$L\supset W^{\perp}$. ∎

We return to the proof of (22). We denote $l=\dim L$ and consider three cases.

  * •

$l\geq d+1$: $\dim L-\frac{p}{J}\sum_{j=k}^{d+1}\dim\pi_{W_{j}}(L)\leq
l-p(n-k+l-n)=l-p(l-k)\leq d+\beta-(d-k+\beta)p$, since $p>1$.

  * •

$k\leq l\leq d$: Since $L$ cannot contain all the $W_{j}^{\perp}$, by Lemma 10
we have

$\sum_{j=k}^{d+1}\dim\pi_{W_{j}}(L)\geq J(l-k)+1.$

Therefore, $\dim L-\frac{p}{J}\sum_{j=k}^{d+1}\dim\pi_{W_{j}}(L)\leq
l-p(l-k)-\frac{p}{J}\leq d+\beta-(d-k+\beta)p$. The last inequality is
equivalent to $(d+\beta-l-J^{-1})p\leq d+\beta-1$. This is true if either
$d+\beta-l-J^{-1}\leq 0$, or $p\leq\frac{d+\beta-l}{d+\beta-l-J^{-1}}$.

  * •

$l\leq k-1$: We simply use $\dim
L-\frac{p}{J}\sum_{j=k}^{d+1}\dim\pi_{W_{j}}(L)\leq\dim L\leq k-1\leq
d+\beta-(d-k+\beta)p$, where the last inequality is equivalent to

$p\leq\frac{d+1-k+\beta}{d-k+\beta}.$

We have finished the proof of claim (21). We obtain that

(23) $\textup{II}\leq
C_{K,\varepsilon}\delta^{-\varepsilon^{2}-k(d-k)(p-1)}\sum_{V\in\mathcal{V}}|V_{\delta}|.$

We turn to the term I which is the right hand side of (17). For a fixed
$Q_{K^{-1}}\in\mathcal{Q}_{K^{-1}}$, we choose $V^{\circ}\in G(k,n)$ to be the
center of $Q_{K^{-1}}$. Let $V^{\circ}_{K^{-1}}$ denote
$N_{K^{-1}}(V^{\circ})\cap B^{n}(0,1)$ which is a $K^{-1}$-slab in
$\mathbb{R}^{n}$, centered at the origin. For any $V\in Q_{K^{-1}}$, we have
$\textup{dir}(V)\cap B^{n}(0,1)\subset CV_{K^{-1}}^{\circ}$. Therefore,
$V_{\delta}$ is contained in a translation of $CV^{\circ}_{K^{-1}}$.

To estimate $\|\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}}}1_{V_{\delta}}\|_{L^{p}(B^{n}(0,1))}^{p}$, we will first partition
the integration domain. We cover $B^{n}(0,1)$ by finitely overlapping slabs
denoted by $\mathcal{T}=\\{\tau\\}$. Here each $\tau$ is a translation of
$CV^{\circ}_{K^{-1}}$, and $\\#\mathcal{T}\sim K^{n-k}$. Also, $\mathcal{T}$
is chosen so that for any $V\in Q_{K^{-1}}$, $V_{\delta}$ is contained in some
$\tau$. If $V_{\delta}$ is contained in $\tau$, than we associate $V_{\delta}$
to $\tau$ and denote by $V_{\delta}\subset\tau$. If there are multiple
choices, we just associate $V_{\delta}$ to one $\tau$. We have

(24) $\|\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}}}1_{V_{\delta}}\|_{L^{p}(B^{n}(0,1))}^{p}=\|\sum_{\tau}\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}},V_{\delta}\subset\tau}1_{V_{\delta}}\|_{L^{p}(B^{n}(0,1))}^{p}.$

We note that $\mathrm{supp}\left(\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}},V_{\delta}\subset\tau}1_{V_{\delta}}\right)\subset\tau$ and
$\mathcal{T}=\\{\tau\\}$ are finitely overlapping, so the equation above is
bounded by

(25) $\lesssim\sum_{\tau}\|\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}},V_{\delta}\subset\tau}1_{V_{\delta}}\|_{L^{p}(\tau)}^{p}.$

Next, we will do the rescaling for $\tau$. We first translate $\tau$ to the
origin, and do the $K$-dilation in the short directions of $\tau$ so that
$\tau$ roughly becomes $B^{n}(0,1)$. We denote this rescaling by
$\Phi_{\tau}$. After the rescaling, we see that every $V_{\delta}\subset\tau$
becomes a $\delta K\times\dots\times\delta K\times 1\times\dots\times 1$-slab
contained in $B^{n}(0,1)$. We can just assume it is $V^{\prime}_{\delta K}$,
where $V^{\prime}=\Phi_{\tau}(V)$. We denote
$\mathcal{V}^{\prime}(\tau):=\\{\Phi_{\tau}V:V_{\delta}\subset\tau\\}$. We
have

(26) $\|\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}},V_{\delta}\subset\tau}1_{V_{\delta}}\|_{L^{p}(\tau)}^{p}\sim
K^{-(n-k)}\|\sum_{V^{\prime}\in\mathcal{V}^{\prime}(\tau)}1_{V^{\prime}_{\delta
K}}\|_{L^{p}(B^{n}(0,1))}^{p}$

Next, we check the spacing condition (3) for $\mathcal{V}^{\prime}(\tau)$. We
want to prove that for any ball $Q_{r}\subset A(k,n)$ of radius $r$ ($\delta
K\leq r\leq 1$), we have

$\\#\\{V^{\prime}\in\mathcal{V}^{\prime}(\tau):V^{\prime}\in
Q_{r}\\}\lesssim(r/\delta K)^{(k+1)(d-k)+\beta}.$

Suppose $W^{\prime}\in A(k,n)$ is the center of $Q_{r}$. Then, $V^{\prime}\in
Q_{r}$ implies $V^{\prime}_{\delta K}\subset W^{\prime}_{Cr}$ by Lemma 2. Let
$W=\Phi_{\tau}^{-1}W^{\prime}$. If we rescale back, i.e., we apply
$\Phi_{\tau}^{-1}$, then $W^{\prime}_{Cr}$ becomes $W_{CrK^{-1}}$ which is a
$CrK^{-1}$-slab. The condition $V^{\prime}_{\delta K}\subset W^{\prime}_{Cr}$
becomes $V_{\delta}\subset W_{CrK^{-1}}$. Again by Lemma 2, this condition
implies $V\in Q_{C^{2}rK^{-1}}$ where $Q_{C^{2}rK^{-1}}\subset A(k,n)$ is a
ball centered at $W$. In summary, We proved that

$\\#\\{V^{\prime}\in\mathcal{V}^{\prime}(\tau):V^{\prime}\in
Q_{r}\\}\leq\\#\\{V\in\mathcal{V}:V\in Q_{C^{2}rK^{-1}}\\}.$

By (3), it is $\lesssim(r/\delta K)^{(k+1)(d-k)+\beta}$.

###  2.3. Induction on scales

We are ready to prove (4). We will induct on $\delta$. Of course, (4) is true
for small $\delta$ if we choose $C_{\varepsilon}$ in (4) sufficiently large.
Suppose (4) is true for numbers $\leq\frac{1}{2}\delta$. We will use induction
hypothesis for the scale $\delta K$ to bound (26). However,
$\mathcal{V}^{\prime}(\tau)$ satisfies

(27) $\\#\\{V^{\prime}\in\mathcal{V}^{\prime}(\tau):V^{\prime}\in Q_{r}\\}\leq
C\cdot(r/\delta K)^{(k+1)(d-k)+\beta},$

where there is an additional constant $C$ compared with (3). We hope to
partition $\mathcal{V}^{\prime}(\tau)$ into subsets so that each subset
satisfies the inequality above with $C=1$. This is done by the following
lemma.

######  Lemma 11.

Let $A\subset[0,1]^{m}$ be a finite set that satisfies

$\\#(A\cap Q_{r})\leq M(r/\delta)^{s},$

for any $Q_{r}$ being a ball of radius $r$ in $[0,1]^{m}$ for $\delta\leq
r\leq 1$. Then we can partition $A$ into $\lesssim 10^{5m}M^{2}$ subsets
$A=\sqcup A^{\prime}$ such that each $A^{\prime}$ satisfies

$\\#(A^{\prime}\cap Q_{r})\leq(r/\delta)^{s},$

for any $Q_{r}$ being a ball of radius $r$ for $\delta\leq r\leq 1$.

###### Proof.

For convenience, we assume $\delta$ is a dyadic number. For any dyadic number
$r\in[\delta,1]$, let $\mathcal{D}_{r}=\\{D_{r}\\}$ be lattice cubes of length
$r$ that form a partition of $[0,1]^{m}$. Note that every ball of radius
$r_{0}$ is contained in $4^{m}$ dyadic cubes of length $2^{r}$, where $r(\leq
r_{0})$ is dyadic. We just need to find a partition $A=\sqcup
A^{\prime\prime}$ such that for each $A^{\prime\prime}$,

$\\#(A^{\prime\prime}\cap D_{r})\leq\max\\{1,10^{-m}(r/\delta)^{s}\\}.$

We first partition $A$ into $\lesssim 10^{m}M$ subsets $\sqcup A^{\prime}$ so
that $\\#(A^{\prime}\cap D_{r})\leq 1$ for $r\leq 10^{\frac{m}{s}}\delta$. It
remains to partition each $A^{\prime}$ further into subsets $A^{\prime}=\sqcup
A^{\prime\prime}$ so that

$\\#(A^{\prime\prime}\cap D_{r})\leq
10^{-m}(r/\delta)^{s},\textup{~{}for~{}}r>10^{\frac{m}{s}}\delta.$

Fix a $A^{\prime}$ in the first stage of partition. We will construct a
sequence of graphs $G_{r}=(V_{r},E_{r})$ indexed by the dyadic numbers
$r\in[\delta,1]$, so that their vertex sets are $V_{r}=A^{\prime}$ and their
edge sets satisfy $E_{r}\subset E_{r^{\prime}}$ if $r<r^{\prime}$. Also, each
$G_{r}$ is a disjoint union of cliques of order $\leq 10^{3m}M$ and the number
of cliques of $G_{r}$ in any dyadic cube $D_{r}$ is $\leq
10^{-m}(r/\delta)^{s}$. Here, a clique is a complete graph, and the order of a
clique is the number of points in the clique.

For $r\leq 10^{\frac{m}{s}}\delta$, we just let $E_{r}$ be empty. Suppose we
have constructed for $r/2$, so $E_{r/2}$ is a disjoint union of cliques with
order $\leq 10^{3m}M$. We are going to construct $E_{r}$. Fix a $D_{r}$.
Consider the cliques of $E_{r/2}$ that lie in $D_{r}$. If there are two
cliques, both of which have order $\leq\frac{1}{2}10^{3m}M$, we merge them to
get a clique of order $\leq 10^{3m}M$. We continue the process until there is
at most one clique whose order is $\leq\frac{1}{2}10^{3m}M$. We do this
argument for each $D_{r}$, and we obtain $E_{r}$. We need to check that for
each $D_{r}$, there are $\leq 10^{-m}(r/\delta)^{s}$ cliques. First of all,
$\\#(A^{\prime}\cap D_{r})\leq M(r/\delta)^{s}$. On the other hand,
$\\#(A^{\prime}\cap
D_{r})\geq(\\#(\textup{cliques~{}in~{}}D_{r})-1)\cdot\frac{1}{2}10^{3m}M$.
Therefore, $\\#(\textup{cliques~{}in~{}}D_{r})\leq 10^{-m}(r/\delta)^{s}$. We
repeat the algorithm and finally obtain $G_{1}=(A^{\prime},E_{1})$.

Since each clique in $G_{1}$ has order $\leq 10^{3m}M$, we can partition
$A^{\prime}$ into $\leq 10^{3m}M$ sets $A^{\prime}=\sqcup A^{\prime\prime}$,
so that for each $A^{\prime\prime}$ there does not exists two points in
$A^{\prime\prime}$ that lie in the same clique. Now, we have

$\\#(A^{\prime\prime}\cap D_{r})\leq\\#(\textup{cliques~{}in~{}}D_{r})\leq
10^{-m}(r/\delta)^{s}.$

This finishes the proof.

∎

By the lemma, we can partition
$\mathcal{V}^{\prime}(\tau)=\bigsqcup_{j}\mathcal{V}^{\prime}_{j}(\tau)$ into
$O(1)$ subsets, so that (27) holds for $\mathcal{V}^{\prime}_{j}(\tau)$ with
$C=1$. Applying the induction hypothesis (4) and triangle inequality, we
obtain

$\|\sum_{V^{\prime}\in\mathcal{V}^{\prime}(\tau)}1_{V^{\prime}_{\delta
K}}\|_{L^{p}(B^{n}(0,1))}^{p}\leq CC_{\varepsilon}(\delta
K)^{-k(d-k)(p-1)-\varepsilon
p}(\sum_{V^{\prime}\in\mathcal{V}^{\prime}(\tau)}|V^{\prime}_{\delta K}|).$

Summing over $\tau\in\mathcal{T}$, we can bound the left hand side of (24) as

$\displaystyle\|\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}}}1_{V_{\delta}}\|_{L^{p}(B^{n}(0,1))}^{p}$ $\displaystyle\leq$
$\displaystyle CK^{-(n-k)}C_{\varepsilon}(\delta K)^{-k(d-k)(p-1)-\varepsilon
p}\sum_{V^{\prime}\in\mathcal{V}^{\prime}(\tau)}|V^{\prime}_{\delta K}|$
$\displaystyle\lesssim$ $\displaystyle CC_{\varepsilon}(\delta
K)^{-k(d-k)(p-1)-\varepsilon p}\sum_{V\in\mathcal{V},\textup{dir}(V)\in
Q_{K^{-1}}}|V_{\delta}|$

(The constant $C$ changes from line to line, but is independent of $K$ and
$\delta$.)

Summing over $Q_{K^{-1}}\in\mathcal{Q}_{K^{-1}}$, we obtain

$\textup{I}\leq C(\log K)^{p}K^{-\varepsilon
p}C_{\varepsilon}\delta^{-(k(d-k)(p-1)-\varepsilon
p}\sum_{V\in\mathcal{V}}|V_{\delta}|.$

Combining with (23), we can bound the left hand side of (17) by

$\displaystyle\|\sum_{V\in\mathcal{V}}1_{V_{\delta}}\|_{p}^{p}\lesssim C(\log
K)^{p}K^{-\varepsilon p}C_{\varepsilon}\delta^{-k(d-k)(p-1)-\varepsilon
p}\sum_{V\in\mathcal{V}}|V_{\delta}|$
$\displaystyle+C_{K,\varepsilon}\delta^{-\varepsilon^{2}-k(d-k)(p-1)}\sum_{V\in\mathcal{V}}|V_{\delta}|.$

To close the induction, it suffices to make

(28) $C(\log K)^{p}K^{-\varepsilon p}\leq 1/2$

and

(29) $C_{K,\varepsilon}\delta^{-\varepsilon^{2}}\leq 1/2\delta^{-\varepsilon
p}C_{\varepsilon}.$

We first choose $K$ sufficiently large so that (28) holds. Then we choose
$C_{\varepsilon}$ large enough so that (29) holds.

##  3\. Proof of Conjecture 1

It is shown in [8, Section 3] that Theorem 5 implies Conjecture 1 in the case
$k=1$. Actually, for all the $k$, the implication is the same. Here, we give a
sketch of proof on why Theorem 5 implies Conjecture 1. We skip the technical
details on the measurability and focus on how the numerology works for general
$k$.

###### A sketch of proof: Theorem 5 implies Conjecture 1.

We just need to consider the case when $\beta\in(0,1]$. If $\beta>1$, we just
replace $\beta$ by $1$ and throw away some $k$-planes in $\mathcal{V}$ to make
$\dim(\mathcal{V})=(k+1)(d-k)+1$. If $\beta=0$, we just replace $\beta$ by $1$
and $d$ by $d-1$. Next, note that it suffices to prove a variant of (1), where
the right hand side is replaced by $d+\beta-\varepsilon$ for arbitrary
$\varepsilon>0$.

Fix such an $\varepsilon$. Let $X=\bigcup_{V\in\mathcal{V}}V$. We will first
localize $X$ inside $B^{n}(0,1)$. Define

$\mathcal{V}^{N}:=\\{V\in\mathcal{V}:\textup{dist}(0,V)<N/2\\}.$

Note that $\mathcal{V}^{N}$ ($N=1,2,\cdots$) is an ascending sequence that
converges to $\mathcal{V}$. Therefore, there exists $N$ such that

$\dim(\mathcal{V}^{N})\geq\dim(\mathcal{V})-\varepsilon/2.$

Note that after the rescaling $x\mapsto x/N$, the Hausdorff dimensions of
$\mathcal{V},\mathcal{V}^{N}$ and $X$ do not change. We use $\mathcal{V}_{1}$
to denote the $\mathcal{V}^{N}$ after the rescaling. By abuse of notation, we
still keep the notation for $\mathcal{V},X$ after the rescaling. We have

$\mathcal{V}_{1}=\\{V\in\mathcal{V}:\textup{dist}(0,V)<1/2\\}\subset A(k,n),$

and $\dim(\mathcal{V}_{1})\geq\dim(\mathcal{V})-\varepsilon/2$. By Frostman’s
lemma, there is a probability measure $\mu$ supported on $\mathcal{V}_{1}$,
such that for any $Q_{r}\subset A(k,n)$ being a ball of radius $r$ we have

(30) $\mu(Q_{r})\leq C_{0}r^{(k+1)(d-k)+\beta-\varepsilon}.$

We also define the localized version of $X$:

$X_{1}:=\bigcup_{V\in\mathcal{V}_{1}}V\cap B^{n}(0,1).$

We remark that for any $V\in\mathcal{V}_{1}$,

$|V\cap B^{n}(0,1)|\gtrsim 1.$

Our goal is to show

(31) $\dim(X_{1})\geq d+\beta-O(\varepsilon).$

Let $k_{0}$ be a large integer that will be chosen later. Cover $X_{1}$ by a
union $\bigcup_{k=k_{0}}^{\infty}\bigcup_{B\in\mathcal{B}_{k}}B$, where
$\mathcal{B}_{k}$ is a collection of balls of radius $2^{-k}$, and

(32) $\sum_{k}2^{-k(\dim X_{1}+\varepsilon)}\\#\mathcal{B}_{k}=:C_{1}<\infty.$

For each $V\in\mathcal{V}_{1}$, there is an index $k=k(V)\geq k_{0}$, so that

(33) $|V\cap\bigcup_{B\in\mathcal{B}_{k}}B|\gtrsim\frac{1}{k^{2}}.$

For each index $k$, define

$\mathcal{V}^{(k)}=\\{V\in\mathcal{V}_{1}:k(V)=k\\}.$

Then

$\sum_{k\geq k_{0}}\mu(\mathcal{V}^{(k)})=1,$

so there exists an index $k_{1}\geq k_{0}$ with
$\mu(\mathcal{V}^{(k_{1})})\geq\frac{1}{k_{1}^{2}}$. From now on, we just
define $\delta=2^{-k_{1}}$ and
$E_{\delta}=\bigcup_{B\in\mathcal{B}_{k_{1}}}B.$

From (32), we see that

(34) $|E_{\delta}|=\\#\mathcal{B}_{k_{1}}2^{-k_{1}}\leq
C_{1}\delta^{n-\varepsilon-\dim X_{1}}.$

Noting that $\mu$ is a $\big{(}(k+1)(d-k)-\varepsilon\big{)}$-dimensional
Frostman measure (see (30)), by [2, Lemma 8], there exists a subset
$\mathcal{V}_{2}\subset\mathcal{V}^{(k_{1})}$ that satisfies
$\\#\mathcal{V}_{2}\gtrsim\frac{1}{k_{1}^{2}}\delta^{\varepsilon-(k+1)(d-k)-\beta}$,
and

$\\#\\{V\in\mathcal{V}_{3}:V\in
Q_{r}\\}\lesssim\delta^{-\varepsilon}(r/\delta)^{(k+1)(d-k)+\beta}$

for any $Q_{r}\subset A(k,n)$ being a ball of radius $r$ ($\delta\leq r\leq
1$).

In what follows, we will write $A\lessapprox B$ to mean
$A\lesssim|\log\delta|^{O(1)}B$.

By Lemma 11, we can find $\mathcal{V}_{3}\subset\mathcal{V}_{2}$ so that
$\\#\mathcal{V}_{3}\gtrsim\delta^{O(\varepsilon)-\big{(}(k+1)(d-k)+\beta\big{)}}$,
and $\mathcal{V}_{3}$ satisfies

$\\#\\{V\in\mathcal{V}_{3}:V\in Q_{r}\\}\leq(r/\delta)^{(k+1)(d-k)+\beta}.$

From (33), we see that for any $V\in\mathcal{V}_{3}$,

(35) $|V_{\delta}\cap E_{\delta}|\gtrapprox 1\sim|V_{\delta}|.$

Now, we can apply Theorem 5 to $\mathcal{V}_{3}$. By (4) and Hölder’s
inequality, we have

$\big{(}\int_{E_{\delta}}\sum_{V\in\mathcal{V}_{3}}1_{V_{\delta}}\big{)}\big{|}E_{\delta}\big{|}^{-1/p^{\prime}}\leq\|\sum_{V\in\mathcal{V}_{3}}1_{V_{\delta}}\|_{p}\leq
C_{\varepsilon}\delta^{-\frac{k(d-k)}{p^{\prime}}-\varepsilon}\big{(}\sum_{V\in\mathcal{V}_{3}}|V_{\delta}|\big{)}^{1/p}.$

Noting (35), this implies

$|E_{\delta}|\gtrsim\delta^{k(d-k)+p^{\prime}\varepsilon}\big{(}\sum_{V\in\mathcal{V}_{3}}|V_{\delta}|\big{)}.$

Combined with
$\sum_{V\in\mathcal{V}_{3}}|V_{\delta}|=\\#\mathcal{V}_{3}\delta^{n-k}\gtrsim\delta^{O(\varepsilon)-(k+1)(d-k)-\beta}\delta^{n-k}$
and (34), we obtain that

$\dim X_{1}\geq d+\beta-O(\varepsilon)$

as $\delta$ goes to $0$. ∎

## References

  * [1] J. Bourgain and L. Guth.  Bounds on oscillatory integral operators based on multilinear estimates.  Geom. Funct. Anal., 21:1239–1295, 2011.
  * [2] P. Dote and S. Gan.  Exceptional set estimates for radial projections in $\mathbb{R}^{n}$.  arXiv preprint arXiv:2208.03597, 2023.
  * [3] K. Héra.  Hausdorff dimension of Furstenberg-type sets associated to families of affine subspaces.  Ann. Acad. Sci. Fenn., 44:903–923, 2019.
  * [4] K. Héra, T. Keleti, and A. Máthé.  Hausdorff dimension of unions of affine subspaces and of Furstenberg-type sets.  J. Fractal Geom., 6(3):263–284, 2019.
  * [5] D. Maldague.  Regularized Brascamp-Lieb inequalities and an application.  Q. J. Math., 73(1):311–331, 2022.
  * [6] D. M. Oberlin.  Exceptional sets of projections, unions of k-planes, and associated transforms.  Israel J. Math., 202:331–342, 2011.
  * [7] R. Oberlin.  Unions of lines in.  Mathematika, 62(3):738–752, 2016.
  * [8] J. Zahl.  Unions of lines in $\mathbb{R}^{n}$.  arXiv preprint arXiv:2208.02913, 2022.


# Multicolor, multipartite Ramsey numbers for quadrilateral

Janusz Dybizbański
Institute of Informatics, Faculty of Mathematics, Physics and Informatics,
University of Gdańsk, Wita Stwosza 57, Gdańsk, Poland
<EMAIL_ADDRESS>
Yaser Rowshan
Institute for Advanced Studies in Basic Sciences (IASBS),
Department of Mathematics, Zanjan 45137-66731, Iran
<EMAIL_ADDRESS><EMAIL_ADDRESS>

###### Abstract

The $p$-partite Ramsey number for quadrilateral, denoted by $r_{p}(C_{4},k)$,
is the least positive integer $n$ such that any coloring of the edges of a
complete $p$-partite graph with $n$ vertices in each partition with $k$ colors
will result in a monochromatic copy of $C_{4}$. In this paper, we present an
upper bound for $r_{p}(C_{4},k)$ and the exact values of $r_{p}(C_{4},2)$ for
all $p\geq 2$. In tripartite case we show that
$r_{3}(C_{4},k)\leq\lfloor(k+1)^{2}/2\rfloor-1$ and the exact value of 4-color
tripartite Ramsey number $r_{3}(C_{4},4)=11$.

##  1 Introduction

In this paper all graphs considered are undirected, finite and contain neither
loops nor multiple edges. Let $G$ be such a graph. The vertex set of $G$ is
denoted by $V(G)$, the edge set of $G$ by $E(G)$, and the number of edges in
$G$ by $e(G)$. Let $\deg(v)$ be the degree of vertex $v$ and $\deg_{i}(v)$
denote the number of the edges incident to $v$ colored with color $i$. The
open neighborhood in color $i$ of vertex $v$ is $N_{i}(v)=\\{u\in
V(G)|\\{u,v\\}\in E(G)\textrm{ and \\{u,v\\} is colored with color $i$}\\}$.
For vertex $v\in V(G)$ and $U\subset V(G)$ let $\deg_{i}(v,U)$ be the number
of edges in color $i$ between $v$ and vertices from $U$. Define $G[S]$ to be
the subgraph of $G$ induced by a set of vertices $S\subset V(G)$ and $G^{i}$
to be the graph containing the edges of $G$ in color $i$. Let $C_{n}$ be the
cycle on $n$ vertices, $K_{n}$ be the complete graph on $n$ vertices, and
$K_{n}^{p}$ be the complete $p$-partite graph with every partition of size
$n$.

For given graph $G$ and $k\geq 2$, the _multicolor Ramsey number_ $R_{k}(G)$
is the smallest integer $n$ such that if we arbitrarily color with $k$ colors
the edges of the complete graph $K_{n}$, then it contains a monochromatic copy
of $G$ in one of the colors. In this paper we consider Ramsey number for
quadrilateral ($G=C_{4}$). In 1972 Chvátal and Harary [4] determined
$R_{2}(C_{4})=6$. Bialostocki and Schönheim [2] proved $R_{3}(C_{4})=11$.
Lower bound for $R_{4}(C_{4})=18$ was determined by Exoo [7] and upper bound
by Sun Yongqi et al. [13]. Lazebnik and Woldar [11] showed the best known
bounds for $5$-color Ramsey number for quadrilateral $27\leq R_{5}(C_{4})\leq
29$. More bounds and general results for Ramsey number we can found in
regularly updated survey by Radziszowski [12].

The _$p$ -partite Ramsey number_ for quadrilateral, denoted by
$r_{p}(C_{4},k)$, is the least positive integer $n$ such that any coloring of
the edges of $K_{n}^{p}$ with $k$ colors will result in a monochromatic copy
of $C_{4}$ in one of the colors.

The study of bipartite Ramsey numbers ($p=2$) was initiated by Beineke and
Schwenk in 1976, and continued by others, in particular Exoo [6], Hattingh and
Henning [9], Goddard, Henning, and Oellermann [8], and Lazebnik and Mubayi
[10]. The exact values of $r_{2}(C_{4},k)$ are known for $k\leq 4$. Beineke
and Schwenk [1] proved that $r_{2}(C_{4},2)=5$, Exoo [6] found the value
$r_{2}(C_{4},3)=11$ and, independently, Steinbach and Posthoff [14] and
Dybizbański, Dzido and Radziszowski [5] showed that $r_{2}(C_{4},4)=19$. We
also know that for every integer $k\geq 5$, $k^{2}+1\leq r_{2}(C_{4},k)\leq
k^{2}+k-2$ [5].

In tripartite case ($p=3$) exact value of Ramsey numbers $r_{3}(C_{4},k)$ is
known for $k\leq 3$. In 2014 Buada, Samana and Longani [3] prove that
$r_{3}(C_{4},3)=7$. In the same paper one can find a proof that
$r_{3}(C_{4},2)=3$.

In this paper we show upper bound for $r_{p}(C_{4},k)$ (Theorem 1), exact
values of $r_{p}(C_{4},2)$ for all $p\geq 2$ (Theorem 4). In tripartite case
we show that $r_{3}(C_{4},k)\leq\lfloor(k+1)^{2}/2\rfloor-1$ (Theorem 7) and
determine the exact value of 4-color tripartite Ramsey number
$r_{3}(C_{4},4)=11$ (Theorem 8).

##  2 Upper bound

The well known version of Cauchy-Schwarz theorem says that if
$a_{1},...,a_{n}$ is a sequence of non-negative real numbers and
$M=\sum_{i=1}^{n}a_{i}$, then $\sum_{i=1}^{n}a_{i}^{2}\geq M^{2}/n$. Moreover,
$\sum_{i=1}^{n}a_{i}^{2}=M^{2}/n$ if and only if $a_{i}=M/n$ for every $i$. We
will use another (integer) version of this theorem.

######  Theorem 1.

Let $a_{1},...,a_{n}$ be a sequence of non-negative integers and
$M=\sum_{i=1}^{n}a_{i}$, then

$\sum_{i=1}^{n}\binom{a_{i}}{2}\geq r\binom{a+1}{2}+(M-r)\binom{a}{2},$

where $a$ and $r$ are integers such that $M=an+r$ and $0\leq r<n$. Moreover,
the minimum is reachable if and only if $|a_{i}-a_{j}|\leq 1$ for every $1\leq
i<j\leq n$.

Note that: (1) $\sum_{i=1}^{n}\binom{a_{i}}{2}$ has the minimum value if and
only if $\sum_{i=1}^{n}a_{i}^{2}$ has the minimum value. (2) If
$a_{j}-a_{i}>1$ for some $i\neq j$ then setting $a_{j}^{\prime}=a_{j}-1$ and
$a_{i}^{\prime}=a_{i}+1$ we obtain the sequence with smaller
$\sum_{i=1}^{n}a_{i}^{2}$.

######  Theorem 2.

Let $p,k\geq 2$ and $n\geq 1$ be integers,
$w=\left\lceil\frac{2\Big{\lceil}\frac{n^{2}p(p-1)}{2k}\Big{\rceil}}{p}\right\rceil$,
and $a$ and $r$ are integers such that $w=a(p-1)n+r$ and $0\leq r<(p-1)n$. If

$r\binom{a+1}{2}+((p-1)n-r)\binom{a}{2}>\binom{n}{2}$ (1)

then $r_{p}(C_{4},k)\leq n$.

###### Proof.

Let $G=(V_{1}\cup...\cup V_{p},E)$ be $p$-partite graph of order $pn$. For
every $1\leq i\leq p$, $V_{i}$ is an independent set and $|V_{i}|=n$. By the
pigeonhole principle, there exist $i$ ($1\leq i\leq p$), such that

$\sum_{v\in V_{i}}\deg(v)\geq\Big{\lceil}\frac{2|E|}{p}\Big{\rceil}$ (2)

Complete $p$-partite graph $K_{n}^{p}$ has $n^{2}p(p-1)/2$ edges and in every
$k$-edge-coloring there exists a color, say $b$ (blue), containing at least

$\left\lceil\frac{n^{2}p(p-1)}{2k}\right\rceil$

edges.

Moreover, by (2), there exists a partition $j$, say $j=1$, such that

$\sum_{v\in
V_{1}}\deg_{b}(v)\geq\left\lceil\frac{2\left\lceil\frac{n^{2}p(p-1)}{2k}\right\rceil}{p}\right\rceil=w$

Let $U=V\setminus
V_{1}=\cup_{l=2}^{p}{V_{l}}=\\{u_{1},u_{2},...,u_{(p-1)n}\\}$. For every $i$,
$1\leq i\leq(p-1)n$, $N_{b}(u_{i})\cap V_{1}$ is the vertex set of blue
neighbors of $u_{i}$ in $V_{1}$. Denote by $a_{i}=|N_{b}(u_{i})\cap
V_{1}|=\deg_{b}(u_{1},V_{1})$. Vertex $u_{i}$ has $a_{i}$ blue neighbors in
$V_{1}$ and $\binom{a_{i}}{2}$ pairs of blue neighbors in $V_{1}$. If
$\sum_{i=1}^{(p-1)n}\binom{a_{i}}{2}>\binom{n}{2}$ then, by pigeonhole
principle, there exists two vertices $u_{i}$ and $u_{j}$ with a common pair of
blue neighbors, say $y_{1},y_{2}$ in $V_{1}$, and there is blue cycle
$(u_{i},y_{1},u_{j},y_{2})$ in the graph. Since
$\sum_{i=1}^{(p-1)n}a_{i}=\sum_{u\in U}\deg_{b}(u,V_{1})=\sum_{v\in
V_{1}}\deg_{b}(v)\geq w$, by Theorem 1,

$\sum_{i=1}^{(p-1)n}\binom{a_{i}}{2}\geq
r\binom{a+1}{2}+(a(p-1)n)\binom{a}{2}$ $\geq
r\binom{a+1}{2}+((p-1)n-r)\binom{a}{2}.$

Thus, if $r\binom{a+1}{2}+((p-1)n-r)\binom{a}{2}>\binom{n}{2}$ then every
$k$-edge-coloring of $K_{n}^{p}$ contains a monochromatic cycle $C_{4}$. ∎

For every $p,k\geq 2$ inequality (1) is satisfied if $n$ is big enough (for
example $n=k^{2}$, for $p\geq 3$). For $p=3$ and $k=4$, $n=11$ is the smallest
integer satisfy (1), so $r_{3}(C_{4},4)\leq 11$. In a similar way we can bound
other numbers. Table 1 presents examples of upper bounds for $k$-color,
$p$-partite Ramsey numbers $r_{p}(C_{4},k)$ which can be obtained from Theorem
1 (for $2\leq p\leq 6$ and $2\leq k\leq 10$). In the bipartite case, we obtain
results that are equal to the exact value for $k\leq 4$ and one worse than the
best known bound ($k^{2}+k+1$ [5]) for $k\geq 5$.

$k$ $\backslash$ $p$ | bipartite | tripartite |  $4$-partite |  $5$-partite |  $6$-partite
---|---|---|---|---|---
2 colors | 5 | 3 | 3 | 3 | 3
3 | 11 | 7 | 5 | 4 | 4
4 | 19 | 11 | 9 | 7 | 6
5 | 29 | 17 | 12 | 11 | 9
6 | 41 | 23 | 17 | 14 | 13
7 | 55 | 31 | 23 | 18 | 16
8 | 71 | 39 | 28 | 23 | 20
9 | 89 | 49 | 35 | 29 | 24
10 | 109 | 59 | 43 | 34 | 29
Table 1: Upper bounds for $r_{p}(C_{4},k)$

##  3 Two colors multipartite Ramsey numbers

######  Lemma 3.

For positive integer $p$,

$p\geq R_{k}(C_{4})\text{ if and only if }r_{p}(C_{4},k)=1.$

###### Proof.

If $p\geq R_{k}(C_{4})$ then every $k$-edge-coloring of $K_{p}=K_{1}^{p}$
contains a monochromatic $C_{4}$ so $r_{p}(C_{4},k)=1$.
If $1\leq p<R_{k}(C_{4})$, then there exist a $k$-edge-coloring of
$K_{1}^{p}=K_{p}$ without monochromatic $C_{4}$ so $r_{p}(C_{4},k)>1$. ∎

Since $K_{n}^{p-1}$ is a subgraph of $K_{n}^{p}$ and the latter is a subgraph
of $K_{n+1}^{p}$, the following two monotonic properties hold:

  * •

If $k_{1}>k_{2}$ then $r_{p}(C_{4},k_{1})\geq r_{p}(C_{4},k_{2}).$

  * •

If $p_{1}>p_{2}$ then $r_{p_{1}}(C_{4},k)\leq r_{p_{2}}(C_{4},k).$

######  Theorem 4.

Two-color multipartite Ramsey number for quadrilateral

$r_{p}(C_{4},2)=\begin{cases}5&\text{ for }p=2,\\\ 3&\text{ for }p=3,\\\
2&\text{ for }p=4\text{ or }5,\\\ 1&\text{ for }p\geq 6.\end{cases}$

###### Proof.

Beineke and Schwenk in [1] show that $r_{2}(C_{4},2)=5$. Buada et al. [3] show
that $r_{3}(C_{4},2)=3$. Since $R_{2}(C_{4})=6$ [4], then by Lemma 3, we have
$r_{p}(C_{4},2)=1$, for $p\geq 6$, and (by Lemma 3 and monotonic)
$r_{4}(C_{4},2)\geq r_{5}(C_{4},2)>1$.

To finish the proof, we shall show that every $2$-edge-coloring of $K_{2}^{4}$
with partition sets
$X_{1}=\\{x_{1},x_{2}\\},X_{2}=\\{w_{1},w_{2}\\},X_{3}=\\{y_{1},y_{2}\\}$, and
$X_{4}=\\{z_{1},z_{2}\\}$, contains monochromatic $C_{4}$. Consider any $2$\-
edges coloring of
$G=K_{2}^{4}=(\\{x_{1},x_{2},w_{1},w_{2},y_{1},y_{2},z_{1},z_{2}\\},E(G))$ say
$(G^{r}=(V(G),E_{r}),G^{b}=(V(G),E_{b}))$, where

$E_{r}\cup
E_{b}=E(G)=\binom{V(G)}{2}\setminus\\{\\{x_{1},x_{2}\\},\\{w_{1},w_{2}\\},\\{y_{1},y_{2}\\},\\{z_{1},z_{2}\\}\\}.$

Now, we have the following claims:

######  Claim 5.

If there exists a vertex of $V(G)$, say $x_{1}\in X_{1}$, and a color, say
red, such that $\deg_{r}(x)\geq 4$ then the coloring contains monochromatic
$C_{4}$.

###### Proof.

Considering vertex $x_{2}$. As we aim to avoid $C_{4}$ then at least 3 edges
from $x_{2}$ to $N_{r}(x_{1})$ must be colored blue (denoted as color $b$).
Consider three vertices $\\{v_{1},v_{2},$ $v_{3}\\}\subset N_{r}(x_{1})\cap
N_{b}(x_{2})$.
a) If those vertices are in different partition then consider the triangle
$\\{v_{1},v_{2},v_{3}\\}$. Two of the edges of this triangle must have the
same color. These two edges create monochromatic $C_{4}$ with $x_{1}$ (if they
are red) or $x_{2}$ (if blue).
b) Suppose that two of those vertices are in the same partition. Without loss
of generality we can assume that
$\\{v_{1},v_{2},v_{3}\\}=\\{y_{1},y_{2},z_{1}\\}$. Consider vertex $w_{1}$ and
colors of the edges $\\{w_{1},y_{1}\\}$, $\\{w_{1},y_{2}\\}$ and
$\\{w_{1},z_{1}\\}$. Two of these edges must have the same color, creating a
monochromatic $C_{4}$ with $x_{1}$ or $x_{2}$. ∎

In the sequel we assume that every vertex in each color has degree 3.

######  Claim 6.

If there exists a vertex of $V(G)$, say $x_{1}\in X_{1}$, and a color say $b$,
such that $X_{i}\subseteq N_{b}(x_{1})$ for one $i\in\\{2,3,4\\}$, then the
coloring contains monochromatic $C_{4}$.

###### Proof.

Without loss of generality let $N_{b}(x_{1})=\\{w_{1},w_{2},y_{1}\\}$,
therefore $N_{r}(x_{1})=\\{y_{2},z_{1},z_{2}\\}$. Now considering $x_{2}$, one
can check that $\\{w_{1},w_{2}\\}\subseteq N_{r}(x_{2})$ and
$\\{z_{1},z_{2}\\}\subseteq N_{b}(x_{2})$. Otherwise, by contrary assume that
$x_{2}z_{1}\in E_{r}$ (for other case the proof is same), hence as
$\deg_{b}(z_{1})=\deg_{r}(z_{1})=3$, and $x_{i}z_{1}\in E_{r}$, then one can
say that $x_{1}$, $z_{1}$ and two vertices from $N_{b}(x_{1})\cap
N_{b}(z_{1})$ create blue $C_{4}$. If $x_{2}y_{1}\in E_{b}$ then as
$\deg_{r}(y_{1})=\deg_{b}(y_{1})=3$, and $x_{i}y_{1}\in E_{b}$ one can say
that either $x_{1}$, $y_{1}$ and two vertices from $N_{r}(x_{1})\cap
N_{r}(y_{1})$ create red $C_{4}$ or $x_{2}$, $y_{1}$ and two vertices from
$N_{r}(x_{2})\cap N_{r}(y_{1})$ create red $C_{4}$. So assume that
$N_{r}(x_{1})=N_{b}(x_{2})$ and $N_{r}(x_{2})=N_{b}(x_{1})$. For one $i=1,2$,
$y_{2}z_{i}\in E_{b}$, otherwise $C_{4}\subseteq G^{r}$. Without loss of
generality let $y_{2}z_{1}\in E_{b}$. Therefore as $\deg_{r}(z_{1})=3$, and
$x_{2}z_{1},y_{2}z_{1}\in E_{b}$ one can say that $x_{2}$, $z_{1}$ and two
vertices from $N_{r}(x_{2})\cap N_{r}(z_{1})$ create red $C_{4}$. Hence claim
holds. ∎

Now by Claim 6, without loss of generality we may suppose that
$N_{b}(x_{1})=\\{w_{1},y_{1},z_{1}\\}$. Assume that $|N_{b}(x_{1})\cap
N_{b}(x_{2})|\neq 0$, and without loss of generality let $w_{1}\in
N_{b}(x_{2})$. Hence by Claim 6, $x_{1}w_{2},x_{2}w_{2}\in E_{r}$. Now, as
$\deg_{r}(w_{1})=3$ and $w_{1}x_{i}\in E_{b}$, either $x_{1}$, $w_{1}$ and two
vertices from $N_{r}(x_{1})\cap N_{r}(w_{1})$ create red $C_{4}$ or $x_{2}$,
$w_{1}$ and two vertices from $N_{r}(x_{2})\cap N_{r}(w_{1})$ create red
$C_{4}$. So, let $N_{b}(x_{2})=N_{r}(x_{1})$ and $N_{r}(x_{2})=N_{b}(x_{1})$.
Consider $w_{1}$ and without loss of generality assume that $w_{1}z_{1}\in
E_{b}$. Therefore by Claim 6 we have $w_{1}z_{2},w_{2}z_{1}\in E_{r}$ and
$w_{2}z_{2}\in E_{b}$. If either $w_{1}y_{1}\in E_{b}$ or $y_{1}z_{1}\in
E_{b}$ then one can check that $C_{4}\subseteq
G^{b}[\\{x_{1},w_{1},y_{1},z_{1}\\}]$. So we may suppose that $w_{1}y_{1}$,
$y_{1}z_{1}\in E_{r}$, in this case we have $C_{4}\subseteq
G^{r}[\\{x_{2},w_{1},y_{1},z_{1}\\}]$, hence the proof is complete. ∎

##  4 Tripartite Ramsey numbers

######  Theorem 7.

For every integer $k\geq 2$,

$r_{3}(C_{4},k)\leq\begin{cases}\frac{(k+1)^{2}-1}{2}-1&\text{for even }k,\\\
\frac{(k+1)^{2}}{2}-1&\text{for odd }k.\end{cases}$

###### Proof.

For $k=2$ we know (from [3]) that $r_{3}(C_{4},2)=3=\frac{(2+1)^{2}-1}{2}-1$.
For even $k>2$, we use Theorem 1. Note that, for $n=\frac{(k+1)^{2}-1}{2}-1$

  * •

$\Big{\lceil}\frac{n^{2}p(p-1)}{2k}\Big{\rceil}=\frac{3}{4}k^{3}+3k^{2}-5$

  * •

$w=\frac{1}{2}k^{3}+2k^{2}-3$,

  * •

$a=\frac{k}{2}$,

  * •

$r=k^{2}+k-3$,

and inequality $r\binom{a+1}{2}+((p-1)n-r)\binom{a}{2}>\binom{n}{2}$ can be
simplified to $k>2$, so $r_{p}(C_{4},k)\leq n$ for even $k\geq 2$.

For odd $k>1$ note that, for $n=\frac{(k+1)^{2}}{2}-1$

  * •

$\Big{\lceil}\frac{n^{2}p(p-1)}{2k}\Big{\rceil}=\frac{3}{4}k^{3}+3k^{2}+\frac{3}{2}k-\frac{9}{4}-\frac{1}{4}((k-1)\mod
4)$

  * •

$w=\frac{k^{3}}{2}+2k^{2}+k-\frac{3}{2}$,

  * •

$a=\frac{k+1}{2}$,

  * •

$r=\frac{k^{2}+k-2}{2}$,

and inequality $r\binom{a+1}{2}+((p-1)n-r)\binom{a}{2}>\binom{n}{2}$ can be
simplified to $k(k+2)>3$ so $r_{p}(C_{4},k)\leq n$ for odd $k\geq 3$. ∎

From [3] we know exact values $r_{3}(C_{4},2)=3$ and $r_{3}(C_{4},3)=7$. The
next Theorem shows that the upper bound presented in Theorem 7 is sharp for
$k=4$.

######  Theorem 8.

$r_{3}(C_{4},4)=11$.

###### Proof.

From Theorem 7 we have $r_{3}(C_{4},4)\leq 11$. For the lower bound we present
adjacency matrix of $4$-coloring of $K_{10}^{3}$ (Fig. 1). The entry in the
$i$-th row and $j$-th column of the matrix refer to the color of edge $(i,j)$.
Value $0$ means that there is no edge and values greater than $0$ are colors.

The matrix in Figure 1 is written in partitioned form as

$\begin{bmatrix}0&0&M_{1,2}&M_{1,3}&M_{1,4}&M_{1,5}\\\
0&0&M_{2,2}&M_{2,3}&M_{2,4}&M_{2,5}\\\
M_{1,2}^{T}&M_{2,2}^{T}&0&0&M_{3,4}&M_{3,5}\\\
M_{1,3}^{T}&M_{2,3}^{T}&0&0&M_{4,4}&M_{4,5}\\\
M_{1,4}^{T}&M_{2,4}^{T}&M_{3,4}^{T}&M_{4,4}^{T}&0&0\\\
M_{1,5}^{T}&M_{2,5}^{T}&M_{3,5}^{T}&M_{4,5}^{T}&0&0\\\ \end{bmatrix},$

where each block $M_{i,j}$ in this partitioned matrix is $5\times 5$ matrix of
the form:

$\begin{bmatrix}a&b&c&d&e\\\ e&a&b&c&d\\\ d&e&a&b&c\\\ c&d&e&a&b\\\
b&c&d&e&a\\\ \end{bmatrix},$

∎

X 0 0 0 0 | 0 0 0 0 0 | 1 4 2 3 2 | 2 1 3 4 4 | 1 3 2 2 3 | 4 1 1 4 3
---|---|---|---|---|---
0 X 0 0 0 | 0 0 0 0 0 | 2 1 4 2 3 | 4 2 1 3 4 | 3 1 3 2 2 | 3 4 1 1 4
0 0 X 0 0 | 0 0 0 0 0 | 3 2 1 4 2 | 4 4 2 1 3 | 2 3 1 3 2 | 4 3 4 1 1
0 0 0 X 0 | 0 0 0 0 0 | 2 3 2 1 4 | 3 4 4 2 1 | 2 2 3 1 3 | 1 4 3 4 1
0 0 0 0 X | 0 0 0 0 0 | 4 2 3 2 1 | 1 3 4 4 2 | 3 2 2 3 1 | 1 1 4 3 4
0 0 0 0 0 | X 0 0 0 0 | 3 2 3 1 4 | 3 1 1 2 4 | 4 4 1 2 1 | 3 2 4 2 3
0 0 0 0 0 | 0 X 0 0 0 | 4 3 2 3 1 | 4 3 1 1 2 | 1 4 4 1 2 | 3 3 2 4 2
0 0 0 0 0 | 0 0 X 0 0 | 1 4 3 2 3 | 2 4 3 1 1 | 2 1 4 4 1 | 2 3 3 2 4
0 0 0 0 0 | 0 0 0 X 0 | 3 1 4 3 2 | 1 2 4 3 1 | 1 2 1 4 4 | 4 2 3 3 2
0 0 0 0 0 | 0 0 0 0 X | 2 3 1 4 3 | 1 1 2 4 3 | 4 1 2 1 4 | 2 4 2 3 3
1 2 3 2 4 | 3 4 1 3 2 | X 0 0 0 0 | 0 0 0 0 0 | 3 3 4 1 1 | 4 4 1 2 2
4 1 2 3 2 | 2 3 4 1 3 | 0 X 0 0 0 | 0 0 0 0 0 | 1 3 3 4 1 | 2 4 4 1 2
2 4 1 2 3 | 3 2 3 4 1 | 0 0 X 0 0 | 0 0 0 0 0 | 1 1 3 3 4 | 2 2 4 4 1
3 2 4 1 2 | 1 3 2 3 4 | 0 0 0 X 0 | 0 0 0 0 0 | 4 1 1 3 3 | 1 2 2 4 4
2 3 2 4 1 | 4 1 3 2 3 | 0 0 0 0 X | 0 0 0 0 0 | 3 4 1 1 3 | 4 1 2 2 4
2 4 4 3 1 | 3 4 2 1 1 | 0 0 0 0 0 | X 0 0 0 0 | 2 4 2 4 3 | 1 3 1 3 2
1 2 4 4 3 | 1 3 4 2 1 | 0 0 0 0 0 | 0 X 0 0 0 | 3 2 4 2 4 | 2 1 3 1 3
3 1 2 4 4 | 1 1 3 4 2 | 0 0 0 0 0 | 0 0 X 0 0 | 4 3 2 4 2 | 3 2 1 3 1
4 3 1 2 4 | 2 1 1 3 4 | 0 0 0 0 0 | 0 0 0 X 0 | 2 4 3 2 4 | 1 3 2 1 3
4 4 3 1 2 | 4 2 1 1 3 | 0 0 0 0 0 | 0 0 0 0 X | 4 2 4 3 2 | 3 1 3 2 1
1 3 2 2 3 | 4 1 2 1 4 | 3 1 1 4 3 | 2 3 4 2 4 | X 0 0 0 0 | 0 0 0 0 0
3 1 3 2 2 | 4 4 1 2 1 | 3 3 1 1 4 | 4 2 3 4 2 | 0 X 0 0 0 | 0 0 0 0 0
2 3 1 3 2 | 1 4 4 1 2 | 4 3 3 1 1 | 2 4 2 3 4 | 0 0 X 0 0 | 0 0 0 0 0
2 2 3 1 3 | 2 1 4 4 1 | 1 4 3 3 1 | 4 2 4 2 3 | 0 0 0 X 0 | 0 0 0 0 0
3 2 2 3 1 | 1 2 1 4 4 | 1 1 4 3 3 | 3 4 2 4 2 | 0 0 0 0 X | 0 0 0 0 0
4 3 4 1 1 | 3 3 2 4 2 | 4 2 2 1 4 | 1 2 3 1 3 | 0 0 0 0 0 | X 0 0 0 0
1 4 3 4 1 | 2 3 3 2 4 | 4 4 2 2 1 | 3 1 2 3 1 | 0 0 0 0 0 | 0 X 0 0 0
1 1 4 3 4 | 4 2 3 3 2 | 1 4 4 2 2 | 1 3 1 2 3 | 0 0 0 0 0 | 0 0 X 0 0
4 1 1 4 3 | 2 4 2 3 3 | 2 1 4 4 2 | 3 1 3 1 2 | 0 0 0 0 0 | 0 0 0 X 0
3 4 1 1 4 | 3 2 4 2 3 | 2 2 1 4 4 | 2 3 1 3 1 | 0 0 0 0 0 | 0 0 0 0 X
Figure 1: Matrix of $4$-edge-coloring of $K_{10}^{3}$ without monochromatic
$C_{4}$.

## Acknowledgements

I would like to thank Andrzej Szepietowski for comments on a preliminary
version of this paper.

## References

  * [1] L. W. Beineke and A. J. Schwenk, On a Bipartite Form of the Ramsey Problem, Proceedings of the Fifth British Combinatorial Conference 1975, Congressus Numerantium, XV (1976) 17–22.
  * [2] A. Bialostocki and J. Schönheim, On Some Turán and Ramsey Numbers for C4, Graph Theory and Combinatorics (ed. B. Bollobás), Academic Press, London, (1984) 29–33.
  * [3] S. Buada, D. Samana, and V. Longani, The Tripartite Ramsey Numbers $r_{t}(C_{4};2)$ and $r_{t}(C_{4};3)$, Italian Journal Of Pure And Applied Mathematics 33 (2014) 383–400
  * [4] V. Chvátal and F. Harary, Generalized Ramsey Theory for Graphs, II. Small Diagonal Numbers, Proceedings of the American Mathematical Society, 32 (1972) 389–394.
  * [5] J. Dybizbański, T. Dzido and S. Radziszowski, On Some Zarankiewicz Numbers and Bipartite Ramsey Numbers for Quadrilateral, Ars Combinatoria, CXIX (2015) 275–287.
  * [6] G. Exoo, A Bipartite Ramsey Number, Graphs and Combinatorics, 7 (1991) 395–396.
  * [7] G. Exoo, Constructing Ramsey Graphs with a Computer, Congressus Numerantium, 59 (1987) 31–36.
  * [8] W. Goddard, M. A. Henning, and O. R. Oellermann, Bipartite Ramsey Numbers and Zarankiewicz Numbers, Discrete Mathematics, 219 (2000) 85–95.
  * [9] J. H. Hattingh and M. A. Henning, Bipartite Ramsey Theory, Utilitas Mathematica, 53 (1998) 217–230.
  * [10] F. Lazebnik and D. Mubayi, New Lower Bounds for Ramsey Numbers of Graphs and Hypergraphs, Advances in Applied Mathematics, 28 (2002) 544–559.
  * [11] F. Lazebnik and A. Woldar, New Lower Bounds on the Multicolor Ramsey Numbers $r_{k}(C_{4})$, Journal of Combinatorial Theory, Series B, 79 (2000) 172–176.
  * [12] S. P. Radziszowski, Small Ramsey Numbers, Electronic Journal of Combinatorics, Dynamic Survey DS1, revision #16 (2021), http://www.combinatorics.org.
  * [13] Sun Yongqi, Yang Yuansheng, Lin Xiaohui, Zheng Wenping, The Value of the Ramsey Number $R_{4}(C_{4})$, Utilitas Mathematica, 73 (2007) 33–44.
  * [14] B. Steinbach and Ch. Posthoff, Extremely Complex 4-Colored Rectangle-Free Grids: Solution of Open Multiple-Valued Problems, Proceedings of the IEEE 42nd International Symposium on Multiple-Valued Logic, Victoria, British Columbia, Canada, (2012) 37–44.