# Estimates for more Brascamp-Lieb forms in $L^{p}$-spaces with power weights

R.M. Brown111 Russell Brown is partially supported by a grant from the Simons
Foundation (#422756).
Department of Mathematics
University of Kentucky
Lexington, KY 40506-0027, USA  K.A. Ott222Katharine Ott is partially supported
by a grant from the Simons Foundation (#526904).
Department of Mathematics
Bates College
Lewiston, ME 04240-6048, USA

###### Abstract

We consider a class of Brascamp-Lieb forms and give conditions which guarantee
the boundedness of these form on $L^{p}$-spaces with weights that are a power
of the distance to the origin. These conditions are close to necessary and
sufficient.

##  1 Introduction

The goal of this paper is to give conditions which guarantee the boundedness
of certain Brascamp-Lieb forms on weighted $L^{p}$-spaces. To describe the
forms we study, we let

$E=\\{v_{1},\dots,v_{N}\\}\subset\mathbf{R}^{m}\setminus\\{0\\}$

be a finite collection of non-zero vectors which does not contain a pair of
collinear vectors. We fix $k\geq 1$ and for
$v=(v^{1},\dots,v^{m})\in\mathbf{R}^{m}$ and
$x=(x^{1},\dots,x^{m})\in\mathbf{R}^{mk}$, we define $v\cdot
x\in\mathbf{R}^{k}$ by $v\cdot x=\sum_{i=1}^{m}v^{i}x^{i}.$ If
$f_{1}\dots,f_{N}$ are non-negative, measurable functions on $\mathbf{R}^{k}$,
the form we will study is

$\displaystyle\Lambda(f_{1},\dots,f_{N})=\int_{\mathbf{R}^{km}}\prod_{i=1}^{N}f_{i}(v_{i}\cdot
x)\,dx.$ (1.1)

We will use $L^{p}_{\alpha}(\mathbf{R}^{k})$ to denote the weighted
$L^{p}$-space with the norm

$\|f\|_{L_{\alpha}^{p}(\mathbf{R}^{k})}=\||\cdot|^{\alpha}f\|_{L^{p}(\mathbf{R}^{k})}.$

Going forward, all norms will be over $\mathbf{R}^{k}$. Our goal, which is
only partially achieved, is to characterize the set of indices
$(1/p_{j},\lambda_{j})_{j=1}^{N}$ for which we have the estimate

$\displaystyle\Lambda(f_{1},\dots,f_{N})\leq
C\prod_{j=1}^{N}\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}}.$ (1.2)

The constant $C$ may depend on the set of vectors $E$, the dimension $k$, and
the indices $(1/p_{j},\lambda_{j})_{j=1}^{N}$. We will focus most of our
attention on the case where $E=\\{v_{1},\dots v_{N}\\}\subset\mathbf{R}^{m}$
has the property that any subset $K\subset E$ with cardinality $\\#K=m$ is a
basis for $\mathbf{R}^{m}$. We call such a set $E$ generic.

We will establish the following theorem, which gives conditions on the indices
$(1/p_{j},\lambda_{j})_{j=1}^{N}$ that guarantee that the bound (1.2) holds.

######  Theorem 1.3.

Let $E=\\{v_{1},\dots,v_{N}\\}$ be a generic set in $\mathbf{R}^{m}$. Suppose
that $(1/p_{j},\lambda_{j})_{j=1}^{N}\in((0,1)\times\mathbf{R})^{N}$ and that
the following list of conditions are true:

$\displaystyle\sum_{j=1}^{N}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})=m,$ (1.4)
$\displaystyle\sum_{v_{j}\notin
V}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})>m-\dim(V)\quad\mbox{for all non-
zero, proper subspaces $V$ of $\mathbf{R}^{m}$},$ (1.5)
$\displaystyle\sum_{v_{j}\notin V}\lambda_{j}\geq 0\quad\mbox{for $V$ a
subspace of $\mathbf{R}^{m}$},$ (1.6)
$\displaystyle\sum_{j=1}^{N}\frac{1}{p_{j}}\geq 1.$ (1.7)

Then estimate (1.2) holds.

The next result gives necessary conditions which are close to the sufficient
conditions in the previous theorem. The set of indices
$(1/p_{j},\lambda_{j})_{j=1}^{N}$ which satisfy our necessary conditions in
Theorem 1.8 below form a polytope in the hyperplane defined by equation (1.4).
The above result, Theorem 1.3, tells us that the estimate (1.2) holds on the
interior of this polytope. The estimate may hold on part of the boundary, but
we do not investigate results on the boundary here.

######  Theorem 1.8.

Let $E=\\{v_{1},\dots,v_{N}\\}\subset\mathbf{R}^{m}$ be a set of vectors and
assume that no pair of vectors from $E$ are collinear. If (1.2) holds, then
the indices $(1/p_{j},\lambda_{j})_{j=1}^{N}\in([0,1]\times\mathbf{R})^{N}$
satisfy (1.4), (1.7), (1.6), and

$\displaystyle\sum_{v_{j}\notin V}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})\geq
m-\dim(V)\quad\mbox{for all subspaces }\,V\subset\mathbf{R}^{m}.$ (1.9)

There is a great deal of work on Brascamp-Lieb forms dating back to the
original work of Brascamp, Lieb, and Luttinger [5]. Two papers that give
recent developments and include more of the history are by Bennett, Carbery,
Christ and Tao [3] and Carlen, Lieb and Loss [9].

A good place to start our story is a paper of Barthe [1, Proposition 3] who
gives a necessary and sufficient condition on the indices
$(1/p_{1},\dots,1/p_{N})$ for which we have estimate (1.2) in the case when
exponents for the weights, $\lambda_{j}$, are all zero. In fact, he shows that
the set of indices $(1/p_{1},\dots,1/p_{N})$ is the matroid polytope for the
set of vectors $E=\\{v_{1},\dots,v_{N}\\}$ (though he does not use this
terminology). His condition was generalized by Bennett et al. and we make
fundamental use of these results in our work. Barthe’s work is not restricted
to forms constructed using generic sets of vectors and it is an interesting
problem to characterize the set of weighted spaces for which we have (1.2)
without the assumption that the set of vectors $E$ is a generic set.

A key point in our proof of Theorem 1.3 is an extension of results for
Brascamp-Lieb forms from Lebesgue spaces to Lorentz spaces by a real
interpolation argument. This idea dates back at least to O’Neil [21] who
studies Young’s inequality in Lorentz spaces and gives an application to
fractional integration. It reappears in several places including Christ [10].
Our work will rely on results of Bez, Lee, Nakamura and Sawano [4] who study
Brascamp-Lieb forms on Lorentz spaces.

Our interest in Brascamp-Lieb forms arose from the study of a scattering map
for a first order system in the plane. This map originated in work of Beals
and Coifman [2] and Fokas and Ablowitz [11] who observed that the scattering
map transforms solutions of the Davey-Stewartson equations to solutions of a
linear evolution equation. In the work of the first author [6], we expand the
scattering map in a series of multi-linear expressions and use estimates for
certain Brascamp-Lieb forms to establish that the series is convergent in a
neighborhood of zero in $L^{2}$. In his dissertation [19, 20], Z. Nie gave a
proof of this result that relied on multi-linear interpolation. The works of
Perry (with an appendix by M. Christ) [22] and Brown, Ott and Perry (with an
appendix by N. Serpico) [8] give estimates for the map on weighted Sobolev
spaces. The recent work of Nachman, Regev, and Tataru [18] establishes that
the map is continuous on all of $L^{2}$, but does not rely on our approach
using Brascamp-Lieb forms.

Motivated by this body of work and especially the results of Brown, Ott, and
Perry, we became interested in the question of characterizing the complete set
of $L^{p}$-spaces with power weights for which we have the bound (1.2). A
first step in this direction appears in our work with Lee [7] where we
consider forms constructed using generic sets of vectors in $\mathbf{R}^{2}$.
Our results in [7] are close to optimal in the sense that we find a closed
polytope containing the set of indices $(1/p_{j},\lambda_{j})_{j=1}^{N}$ for
which we have (1.2), and we show that in the interior of this polytope we have
estimate (1.2). In the current paper, we extend these methods from
$\mathbf{R}^{2}$ to handle forms based on generic sets of vectors in
$\mathbf{R}^{m}$ with $m>2$. The polytope we find lies in a hyperplane in
$\mathbf{R}^{2N}$ and by interior we mean the interior in the relative
topology for this hyperplane.

The methods developed over the arc of our works can be used to establish the
estimate (1.2) for certain indices when the set of vectors do not satisfy the
generic condition. In fact, going back to the results of Brown, Ott, and Perry
[8], the form studied there is defined using non-generic sets of vectors and
we were successful in finding estimates for the form. However, when
considering arbitrary sets of vectors $E\subset\mathbf{R}^{m}$, our methods
are only successful if we have the additional condition that $E$ is a generic
set. To be more precise about this limitation, in the last section of this
paper we give an example of a form where there are points in the interior of
the polytope defined by Theorem 1.3 for which a straightforward extension of
our argument used in the generic case fails to establish (1.2).

Using duality, the estimates for Brascamp-Lieb forms (at least for the range
of indices $p$ that we consider) are equivalent to estimates for multi-linear
operators. A good place to start this part of the story is a theorem of Stein
and Weiss [23], which gives optimal results for the action of the Riesz
potential of order $\beta$ on spaces $L^{p}_{\alpha}$. Using duality, we can
see that estimates for this operator are equivalent to weighted estimates for
the form

$\int_{\mathbf{R}^{2k}}\frac{f(x)g(y)}{|x-y|^{k-\beta}}\,dxdy.$

In our earlier work [7] we showed how to obtain the Stein-Weiss result from
the case $m=2$ of our Theorem on multilinear forms defined using generic sets
of vectors in $\mathbf{R}^{2}$. Work of Grafakos [12] considers an $n$-linear
fractional integration operator in the unweighted case. Grafakos’s operator
may be related to a form constructed using a set of generic vectors in
$\mathbf{R}^{2}$. Grafakos and Kalton [13, Section 5] consider a multi-linear
form involving a set of vectors that is not generic.

Kenig and Stein [15] consider a multilinear fractional integral and give
results when their operator maps into an $L^{p}$-space with $p<1$. This is a
result that cannot be obtained by using duality and appealing to estimates for
forms. There are a number of authors who have considered weighted estimates
for bilinear fractional integrals. The author Komori-Furuya [16] has studied
these operators on the spaces $L^{p}_{\alpha}$ we consider here. Moen [17]
gives conditions on general weights which guarantee boundedness of a bilinear
fractional integral. In comparison, our work considers less general weights,
but gives results that are close to optimal. An interesting open problem is to
find conditions on weights that allow us to establish the finiteness of
Brascamp-Lieb forms for more general classes of weighted spaces.

The outline of this paper is as follows. In section 2 we prove the conditions
which guarantee the finiteness of the form and (1.2). Section 3 is devoted to
the proofs of the necessary conditions and section 4 gives several examples
illustrating our results and the limitations of our methods.

We thank our colleague, C.W. Lee for suggesting that we study Brascamp-Lieb
forms constructed using generic sets of vectors.

##  2 Sufficient conditions

In this section, we give the proof that the conditions in Theorem 1.3 are
sufficient to imply the estimate (1.2). The proof will proceed in four steps
of increasing complexity. First, we prove the theorem in the case when
$\lambda_{j}=0$ for all $j$ and $k=1$. Next, we remove the restriction on $k$.
The third step is to prove the result under the assumption that all
$\lambda_{j}\geq 0$. The final step is to show that when $\lambda_{j}<0$ for
at least one index $j$ we may reduce to the case where all $\lambda_{j}\geq
0$.

Before beginning the proof, we recall a few facts about the Lorentz spaces,
$L^{p,r}$, where $1\leq p<\infty$ and $1\leq r\leq\infty$. A definition of
these spaces may be found in Stein and Weiss [24, p. 191]. This family of
spaces include the familiar $L^{p}$-spaces as $L^{p}=L^{p,p}$ and arise as
real interpolation spaces of the $L^{p}$-spaces. An observation of Calderón is
that the spaces $L^{p,r}$ may be normed if $1<p<\infty$ and $1\leq
r\leq\infty$ (and of course when $p=r=\infty$,
$L^{\infty,\infty}=L^{\infty}$). Imitating the definition of $L^{p}_{\alpha}$,
we define weighted Lorentz spaces $L^{p,r}_{\alpha}$ as the collection of
functions $f$ for which $|\cdot|^{\alpha}f$ lies in $L^{p,r}$.

We recall the extension of Hölder’s inequality to Lorentz spaces due to O’Neil
[21, Theorem 3.4]. Suppose $p\in(1,\infty)$, $p_{1},p_{2}\in(1,\infty)$,
$1/p=1/p_{1}+1/p_{2}$, $r,r_{1},r_{2}\in[1,\infty]$, and $1/r\leq
1/r_{1}+1/r_{2}$. Then there is a finite constant $C$ such that

$\|f_{1}f_{2}\|_{L^{p,r}}\leq
C\|f_{1}\|_{L^{p_{1},r_{1}}}\|f_{2}\|_{L^{p_{2},r_{2}}}.$ (2.1)

One useful observation is that for $0<\lambda<k$, the function
$|x|^{-\lambda}$ lies in the space $L^{\lambda/k,\infty}(\mathbf{R}^{k})$ and
in fact if $0<\lambda-\alpha<k$ we have

$|x|^{-\lambda}\in L^{k/(\lambda-\alpha),\infty}_{\alpha}(\mathbf{R}^{k}).$
(2.2)

We begin with the case when $k=1$ and $\lambda_{j}=0$ for all $j$. Under this
restriction, provided that (1.4) and (1.5) hold, the theorem of Bennett,
Carbery, Christ, and Tao [3, Theorem 2.1] implies that (1.2) holds. Next,
Proposition 2.1 from our previous work [7] shows that the boundedness of the
form for $k>1$ follows from the case where $k=1$. From here, a result of Bez
et al. [4, Theorem 1] allows us to conclude that we have an estimate for the
form in Lorentz spaces. In particular, if the indices
$(1/p_{j},0)_{j=1}^{N}\in(0,1)^{N}\times\\{0\\}^{N}$ satisfy (1.4), (1.5) and
the indices $(1/r_{1},\dots,1/r_{N})$ satisfy $\sum_{j=1}^{N}1/r_{j}\geq 1$,
then we have

$\Lambda(f_{1},\dots,f_{N})\leq C\prod_{j=1}^{N}\|f_{j}\|_{L^{p_{j},r_{j}}}.$
(2.3)

The result of Bez et al. depends on a multi-linear interpolation argument
which may be found in work of M. Christ [10] or S. Janson [14].

Next, suppose that $\lambda_{j}\geq 0$ for all $j$. Set

$\frac{1}{r_{j}}=\frac{1}{p_{j}}+\frac{\lambda_{j}}{k},$

and observe that for the one-dimensional space $\mathbf{R}v_{j}$ we have

$\big{\\{}v_{i}:v_{i}\notin\mathbf{R}v_{j}\big{\\}}=\big{\\{}v_{1},\dots,v_{N}\big{\\}}\setminus\\{v_{j}\\}.$

In this case, the conditions (1.4) and (1.5) imply

$\frac{1}{p_{j}}+\frac{\lambda_{j}}{k}=m-\sum_{i\neq
j}(\frac{1}{p_{i}}+\frac{\lambda_{i}}{k})<m-(m-1)=1.$ (2.4)

Also from the assumptions that $1/p_{j}\in(0,1)$ and $\lambda_{j}\geq 0$ for
all $j$, it immediately follows that
$\frac{1}{p_{j}}+\frac{\lambda_{j}}{k}>0$. Finally, employing (2.3), the
generalized Hölder inequality (2.1) and the observation (2.2) (with
$\alpha=0$) we have

$\displaystyle\Lambda(f_{1},\dots,f_{N})$ $\displaystyle\leq
C\prod_{j=1}^{N}\|f_{j}\|_{L^{r_{j},p_{j}}}$ $\displaystyle\leq
C\prod_{j=1}^{N}\|f_{j}|\cdot|^{\lambda_{j}}\|_{L^{p_{j},p_{j}}}\||\cdot|^{-\lambda_{j}}\|_{L^{k/\lambda_{j},\infty}}=C\prod_{j=1}^{N}\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}}$

which gives (1.2) in the case that all $\lambda_{j}\geq 0$.

The next step is to prove estimate (1.2) when $\lambda_{j}<0$ for some $j$. We
will proceed by induction on the number of indices $j$ for which
$\lambda_{j}<0$. The following technical Lemma gives most of the details of
the induction step.

######  Lemma 2.5.

Given a family $({1}/{p_{j}},\lambda_{j})_{j=1}^{N}$ satisfying (1.4–1.7), and
$1/p_{j}\in(0,1)$, with at least one $j$ with $\lambda_{j}<0$, let $j_{0}$ be
an index so that $\lambda_{j_{0}}=\min\\{\lambda_{j}:j=1,\dots,N\\}$. We may
find a finite family $\\{\beta^{(\alpha)}\\}_{\alpha\in\zeta}$ so that
$({1}/{p_{j}},\beta_{j}^{(\alpha)})_{j=1}^{N}$ satisfy (1.4–1.7). The vectors
of exponents $\beta^{(\alpha)}$ are indexed by a family of multi-indices
$\zeta\subset\\{0,1,\dots,N\\}^{\ell-m+1}$ where $\ell$ is the number of
positive entries in $\lambda$. Moreover, $({1}/{p_{j}},\beta_{j}^{(\alpha)})$
satisfy

$\displaystyle\beta_{j_{0}}^{(\alpha)}=0\quad\mbox{for all }\,\alpha\in\zeta,$
(2.6) $\displaystyle\beta_{j}^{(\alpha)}=\lambda_{j}\quad\mbox{if
}\,\lambda_{j}<0\mbox{ and }j\neq j_{0},$ (2.7) $\displaystyle
0\leq\beta^{(\alpha)}_{j}\leq\lambda_{j}\quad\mbox{if }\,\lambda_{j}\geq 0.$
(2.8)

Also, we have

$\displaystyle\Lambda(f_{1},\dots,f_{N})\leq
C\sum_{\alpha\in\zeta}\Lambda(|\cdot|^{\lambda_{1}-\beta_{1}^{(\alpha)}}f_{1},\dots,|\cdot|^{\lambda_{N}-\beta_{N}^{(\alpha)}}f_{N}).$
(2.9)

If we grant the Lemma, then the proof by induction is quite easy. We have
already established the base case when all the exponents $\lambda_{j}$ are
non-negative. To proceed by induction, we assume that we have Theorem 1.3 when
$J$ of the exponents $\lambda_{j}$ are negative. If $\lambda$ is a vector of
exponents with $J+1$ negative entries and so that
$(1/p_{j},\lambda_{j})_{j=1}^{N}$ satisfy the conditions of Theorem 1.3, then
using the family $\\{\beta^{(\alpha)}:\alpha\in\zeta\\}$ from Lemma 2.5, we
have

$\displaystyle\Lambda(f_{1},\dots,f_{N})$
$\displaystyle\leq\sum_{\alpha\in\zeta}\Lambda(|\cdot|^{\lambda_{1}-\beta_{1}^{(\alpha)}}f_{1},\dots,|\cdot|^{\lambda_{N}-\beta_{N}^{(\alpha)}}f_{N})$
$\displaystyle\leq
C\sum_{\alpha\in\zeta}\prod_{j=1}^{N}\||\cdot|^{\lambda_{j}-\beta_{j}^{(\alpha)}}f_{j}\|_{L^{p_{j}}_{\beta_{j}^{(\alpha)}}}=C\prod_{j=1}^{N}\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}}.$

Thus, establishing Lemma 2.5 will complete the proof of Theorem 1.3. To prove
Lemma 2.5, we will make use of the following lemmata which give alternative
characterizations of (1.5) and (1.6) in the case of generic sets of vectors.

######  Lemma 2.10.

Let $E=\\{v_{1},\dots,v_{N}\\}$ be a generic set in $\mathbf{R}^{m}$ and let
$(1/p_{j},\lambda_{j})_{j=1}^{N}\in(0,1)^{N}\times\mathbf{R}^{N}$. The
following conditions on these indices are equivalent:

$\displaystyle\sum_{v_{j}\notin W}\lambda_{j}\geq 0\quad$
$\displaystyle\mbox{for all proper subspaces $W\subset\mathbf{R}^{m}$},$
(2.11) $\displaystyle\sum_{v_{j}\notin K}\lambda_{j}\geq 0\quad$
$\displaystyle\mbox{for all }K\subset E\,\mbox{such that }\,\\#K\leq m-1.$
(2.12)

###### Proof.

First we show that (2.12) implies (2.11). Given $W$ a proper subspace of
$\mathbf{R}^{m}$, set $K=\\{v_{\ell}:v_{\ell}\in W\\}$. Then $\\#K\leq\dim
W\leq m-1$ and from (2.12) we obtain (2.11)

$\sum_{v_{i}\notin W}\lambda_{i}=\sum_{v_{i}\notin K}\lambda_{i}\geq 0.$

For the other implication, assume that (2.11) holds. Given $K$, set
$W=\mathop{\rm span}\nolimits(K)$ which will be a proper subspace of
$\mathbf{R}^{m}$ since $\\#K\leq m-1$. Thanks to our assumption that the set
$E=\\{v_{1},\dots,v_{N}\\}$ is generic and that $\\#K\leq m-1$, it follows
that $W\cap E=K$. Then it follows that

$\sum_{v_{i}\notin K}\lambda_{i}=\sum_{v_{i}\notin W}\lambda_{i}\geq 0.$

∎

In our next Lemma, we need to avoid the cases when $K$ is empty or all of $E$
and we will have equality in (2.15).

######  Lemma 2.13.

Let $E=\\{v_{1},\dots,v_{N}\\}$ be a generic set in $\mathbf{R}^{m}$ and
suppose $(1/p_{j},\lambda_{j})_{j=1}^{N}\in(0,1)^{N}\times\mathbf{R}^{N}$ Then
the following two statements are equivalent:

$\displaystyle\sum_{v_{j}\notin
V}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})>m-\dim(V)\quad\mbox{for all
subspaces $V$ with $1\leq\dim(V)\leq m-1$}$ (2.14)
$\displaystyle\sum_{v_{j}\notin
K}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})>m-\\#K\quad\mbox{for all }\,K\subset
E\,\mbox{with }1\leq\\#K\leq m-1.$ (2.15)

###### Proof.

First, to prove that (2.14) implies (2.15), let $K\subset E$ with
$1\leq\\#K\leq m-1$. Let $V=\mathop{\rm span}\nolimits(K)$ and use the
assumption that $E$ is a generic set to conclude $\dim(V)=\\#K$ and
$\\{v_{j}:v_{j}\notin V\\}=E\setminus K$ Thus

$\displaystyle\sum_{v_{j}\notin
K}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})=\sum_{v_{j}\notin
V}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})>m-\dim(V)=m-\\#K.$

Now suppose that we have (2.15) and let $V\subset\mathbf{R}^{m}$ be a proper
subspace. Set $K=\\{v_{j}:v_{j}\in V\\}$. By the generic condition,
$\\#K\leq\dim(V)$ which implies that $m-\dim(V)\leq m-\\#K$. Thus in the case
that $\\#K\geq 1$, (2.14) follows from (2.15). If $\\#K=0$ and $\dim V\geq 1$,
we may use (2.15) for the set $K=\\{v_{1}\\}$ and find that there is at least
one $j$ for which $1/p_{j_{0}}+\lambda_{j_{0}}/k\geq 0$. Then

$\sum_{j=1}^{N}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})\geq\sum_{j\neq
j_{0}}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})>m-1\geq m-\dim V.$

Thus (2.14) follows from (2.15). ∎

###### Proof of Lemma 2.5.

For convenience, we assume that the vectors $v_{j}$ are labeled so that the
exponents $\lambda$ are in decreasing order and $\ell$ is the last index for
which $\lambda_{\ell}>0$:

$\lambda_{1}\geq\dots\geq\lambda_{\ell}>0\geq\lambda_{\ell+1}\geq\dots\geq\lambda_{N}.$

With this re-indexing our goal is find a family $\\{\beta^{(\alpha)}\\}$ with
$\beta^{(\alpha)}_{N}=0$. To begin, we use (2.12) with
$K=\\{v_{1},\dots,v_{m-1}\\}$ to obtain that

$\displaystyle\lambda_{N}+\sum_{i=m}^{\ell}\lambda_{i}\geq\sum_{i=m}^{N}\lambda_{i}\geq
0.$ (2.16)

Thus it follows that

$\displaystyle|\lambda_{N}|\leq\sum_{i=m}^{\ell}\lambda_{i}.$ (2.17)

Now we will proceed by giving a construction involving at most $\ell-m+1$
steps to produce the family $\\{\beta^{(\alpha)}\\}\subset\mathbf{R}^{N}$. The
vectors $\beta^{(\alpha)}$ will be indexed by multi-indices
$\alpha\in\\{0,1,\dots,N\\}^{\ell-m+1}$.

To begin, we set $\beta^{(0)}=\lambda$ and then set

$\gamma_{0}=\min(\lambda_{1},\dots,\lambda_{m},|\lambda_{N}|)=\min(\lambda_{m},|\lambda_{N}|).$

Now define

$\displaystyle\beta^{(j_{1},0)}$
$\displaystyle=(\lambda_{1},\dots,\lambda_{j_{1}}-\gamma_{0},\dots,\lambda_{m+1},\dots,\lambda_{N}+\gamma_{0})$
$\displaystyle=\lambda-\gamma_{0}e_{j_{1}}+\gamma_{0}e_{N},$

and set $\zeta_{1}=\\{\beta^{(j_{1},0)}:j_{1}=1,\dots,m\\}.$ It is clear that
for each $\alpha\in\zeta_{1}$, $({1}/{p_{j}},\beta_{j}^{(\alpha)})_{j=1}^{N}$
satisfies (1.4) and (1.7). It remains to show that (1.5) and (1.6) hold.

We will use Lemma 2.10 to show that $\beta^{(j_{1},0)}$ satisfies (1.6). Thus
let $K\subset E$ be a set with $\\#K\leq m-1$ and consider the four cases
according to whether or not $v_{j_{1}}$ and $v_{N}$ lie in $K$. If both
$v_{j_{1}},v_{N}$ lie in $K$, or both lie in $E\setminus K$, then

$\displaystyle\sum_{v_{j}\notin K}\beta_{j}^{(j_{1},0)}=\sum_{v_{j}\notin
K}\lambda_{j}\geq 0.$

If $v_{N}\notin K$ and $v_{j_{1}}\in K$, then

$\displaystyle\sum_{v_{j}\notin
K}\beta_{j}^{(j_{1},0)}=\gamma_{0}+\sum_{v_{j}\notin
K}\lambda_{j}\geq\gamma_{0}+0\geq 0.$

Finally, the most interesting case is when $v_{N}\in K$ and $v_{j_{1}}\notin
K$. In this scenario,

$\displaystyle\sum_{v_{j}\notin
K}\beta_{j}^{(j_{1},0)}=\lambda_{j_{1}}-\gamma_{0}-\lambda_{N}+\sum_{v_{j}\notin((K\setminus\\{v_{N}\\})\cup\\{v_{j_{1}}\\})}\lambda_{j}\geq
0.$

The inequality above holds since $\lambda_{j_{1}}-\gamma_{0}\geq 0$ and
$-\lambda_{N}\geq 0$.

Thus we have verified that (1.6) holds for $\beta^{(j_{1},0)}$, and now we
proceed with a similar argument using Lemma 2.13 to show that (1.5) is also
true. For this, again we consider four cases.

The cases $\\{v_{j_{1}},v_{N}\\}\subset K$ and $\\{v_{j_{1}},v_{N}\\}\subset
K^{c}$ are straightforward since in these cases we have:

$\displaystyle\sum_{v_{j}\notin
K}(\frac{1}{p_{j}}+\frac{\beta_{j}^{(j_{1},0)}}{k})=\sum_{v_{j}\notin
K}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})\geq m-\\#K.$

In the third case, $v_{j_{1}}\in K,v_{N}\notin K$, and

$\sum_{v_{j}\notin
K}(\frac{1}{p_{j}}+\frac{\beta_{j}^{(j_{1},0)}}{k})=\frac{\gamma_{0}}{k}+\sum_{v_{j}\notin
K}(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k})>\gamma_{0}+m-\\#K.$

Finally, if $v_{j_{1}}\notin K$ and $v_{N}\in K$,

$\sum_{v_{j}\notin
K}(\frac{1}{p_{j}}+\frac{\beta_{j}^{(j_{1},0)}}{k})=m-\sum_{v_{j}\in
K}(\frac{1}{p_{j}}+\frac{\beta_{j}^{(j_{1},0)}}{k})>m-\\#K.$

The last inequality above follows if we can prove the claim that

$\displaystyle\frac{1}{p_{j}}+\frac{\beta_{j}^{(j_{1},0)}}{k}<1\quad\mbox{for
}\,v_{j}\in K.$ (2.18)

To see that (2.18) holds, consider two cases: $v_{j}\in
K\setminus\\{v_{N}\\}$, and $v_{j}=v_{N}$. In the first case,

$\displaystyle\frac{1}{p_{j}}+\frac{\beta_{j}^{(j_{1},0)}}{k}$
$\displaystyle\leq\frac{1}{p_{j}}+\frac{\lambda_{j}}{k}$
$\displaystyle=\sum_{i=1}^{N}(\frac{1}{p_{i}}+\frac{\lambda_{i}}{k})-\sum_{i\neq
j}(\frac{1}{p_{i}}+\frac{\lambda_{i}}{k})$ $\displaystyle<m-(m-1)=1.$

The last line above follows from (1.4) and (1.5). In the second case, when
$j=N$,

$\displaystyle\frac{1}{p_{N}}+\frac{\beta_{N}^{(j_{1},0)}}{k}\leq\frac{1}{p_{N}}<1,$

since $\beta_{N}^{(j_{1},0)}\leq 0$ and we assume that ${1}/{p_{N}}<1$.

Having verified (1.5) for each $\beta^{(j_{1},0)}\in\zeta_{1}$, we move on to
the task of establishing the inequality (2.9). Using our assumption that the
set $E=\\{v_{1},\dots,v_{N}\\}$ is generic, we have that
$\\{v_{1},\dots,v_{m}\\}$ is a basis for $\mathbf{R}^{m}$. Therefore we can
express $v_{N}=\sum_{j=1}^{m}\alpha_{j}v_{j}$. Since $\gamma_{0}>0$, we have

$|x\cdot v_{N}|^{\gamma_{0}}\leq C\sum_{j=1}^{m}|x\cdot v_{j}|^{\gamma_{0}}.$

Inserting this inequality into the form gives

$\displaystyle\Lambda(f_{1},\dots,f_{N})$
$\displaystyle=\Lambda(f_{1},\dots,\frac{|x\cdot v_{N}|^{\gamma_{0}}}{|x\cdot
v_{N}|^{\gamma_{0}}}f_{N})$ (2.19) $\displaystyle\leq
C\sum_{j=1}^{m}\Lambda(f_{1},\dots,|x\cdot
v_{j}|^{\gamma_{0}}f_{j},\dots,|x\cdot v_{N}|^{-\gamma_{0}}f_{N})$
$\displaystyle=C\sum_{j=1}^{m}\Lambda(|x\cdot
v_{1}|^{\lambda_{1}-\beta_{1}^{(j,0)}}f_{1},\dots,|x\cdot
v_{N}|^{\lambda_{N}-\beta_{N}^{(j,0)}}f_{N}).$

This is the estimate (2.9).

We should also note that for each $\beta^{(j_{1},0)}\in\zeta_{1}$, we have
$\beta_{N}^{(j_{1},0)}=\min(0,\lambda_{N}+\lambda_{m})$. If
$\beta_{N}^{(j_{1},0)}=0$, we are done. Otherwise, we repeat the construction
as follows: For each $\beta^{(j_{1},0)}\in\zeta_{1}$, define
$\beta^{(j_{1},j_{2},0)}$, with $j_{2}\in\\{1,\dots,m\\}\setminus\\{j_{1}\\}$
by setting

$\displaystyle\beta^{(j_{1},j_{2},0)}=\beta^{(j_{1},0)}-\gamma_{1}e_{j_{2}}+\gamma_{1}e_{N},$

where $\gamma_{1}=\min(\lambda_{m+1},|\lambda_{N}+\gamma_{0}|)$. Arguing as
above, we have $(\frac{1}{p_{j}},\beta^{(j_{1},j_{2},0)})$ satisfies (1.4),
(1.5), (1.6), and (1.7). Moreover,

$\beta_{N}^{(j_{1},j_{2},0)}=\min(0,\lambda_{m}+\lambda_{m+1}+\lambda_{N}).$

Set
$\zeta_{2}=\big{\\{}\beta^{(j_{1},j_{2},0)}:j_{1}\in\\{1,\dots,m\\},j_{2}\in\\{1,\dots,m+1\\}\setminus\\{j_{1}\\}\big{\\}}$.
Continuing in this manner, (2.17) guarantees that we have
$\beta_{N}^{(\alpha)}=0$ for all $\beta^{(\alpha)}\in\zeta_{i}$ for some
$i\leq\ell-m+1$. This completes the proof of the Lemma 2.5. ∎

##  3 Necessary Conditions

In this section we prove Theorem 1.8. It is worth noting that the results in
this section do not require the condition that the set of vectors $E$ be
generic. We begin with a simple, technical Lemma.

######  Lemma 3.1.

If $V$ and $W$ are vector subspaces of $\mathbf{R}^{m}$ with $V\subset W$ and
$\\{v_{1},\dots,v_{\ell}\\}\subset W\setminus V$, then there exists $w\in
W\cap V^{\perp}$ so that $w\cdot v_{j}\neq 0,j=1,\dots,\ell$.

Before giving the proof, we introduce some additional notation. In the
argument below, it will be useful to consider $\mathbf{R}^{mk}$ as a tensor
product, $\mathbf{R}^{m}\otimes\mathbf{R}^{k}$. Thus, if
$x=(x^{1},\dots,x^{m})\in\mathbf{R}^{mk}$ with each $x^{j}\in\mathbf{R}^{k}$,
we can write $x=\sum_{j=1}^{m}e_{j}\otimes x^{j}$ with $e_{j}$ denoting the
unit vector in the direction of the $j$th coordinate axis. From this it is
clear that $\mathbf{R}^{m}\otimes\mathbf{R}^{k}$ is spanned by elements of the
form $y\otimes z$ with $y\in\mathbf{R}^{m}$ and $z\in\mathbf{R}^{k}$. With
this notation, our map $v\cdot x$ can be defined on products by
$v\cdot(y\otimes z)=(v\cdot y)z$ and then we use linearity to extend the
definition to all of $\mathbf{R}^{m}\otimes\mathbf{R}^{k}$.

###### Proof.

We inductively define $w_{\alpha}$ for $\alpha=1,\dots,\ell$ so that

$\displaystyle w_{\alpha}\cdot v_{i}\neq 0,\quad
i=i,\dots,\alpha\,\,\,\mbox{and }\,w_{\alpha}\in W\cap V^{\perp}.$

At the conclusion, we will set $w=w_{\ell}$.

To begin, let $w_{1}=v_{1}^{\perp}$, the projection of $v_{1}$ onto
$V^{\perp}$. Next, given $w_{\alpha}$, if $w_{\alpha}\cdot v_{\alpha+1}\neq 0$
then set $w_{\alpha+1}=w_{\alpha}$. If, on the other hand, $w_{\alpha}\cdot
v_{\alpha+1}=0$, set $w_{\alpha+1}=cw_{\alpha}+v_{\alpha+1}^{\perp}$. Here, we
choose $c$ so that $|v_{j}\cdot w_{\alpha+1}|\geq 1$, $j=1,\dots,\alpha$. For
example, one can choose

$\displaystyle c=\frac{1+\max\\{|v_{\alpha+1}^{\perp}\cdot
v_{j}|:j=1,\dots,\alpha\\}}{\min\\{|w_{\alpha}\cdot
v_{j}|:j=1,\dots,\alpha\\}}.$

This completes the construction. ∎

###### Proof of Theorem 1.8.

We begin by applying Lemma 3.1 to the pair of subspaces
$\\{0\\}\subset\mathbf{R}^{m}$ to find
$w_{1}\in\\{0\\}^{\perp}=\mathbf{R}^{m}$ and satisfying

$w_{1}\cdot v_{j}\neq 0,\qquad j=1,\dots,N.$

Next, for $w\in\mathbf{R}^{m}$, $u\in\mathbf{R}^{k}$, we define $w\otimes
u=(w^{1}u,w^{2}u,\dots,w^{m}u)\in\mathbf{R}^{mk}$. Assume $|u|=1$ and then set

$\displaystyle S_{R}=B^{mk}(Rw_{1}\otimes u,\epsilon R),$

where the superscript on $B$ is included to make clear that we have a ball in
$\mathbf{R}^{mk}$. We can choose $\epsilon>0$ small so that

$\displaystyle c_{1}R\leq|v_{j}\cdot x|\leq c_{2}R,\qquad x\in S_{R},\
j=1,\dots,N.$

This follows since

$\displaystyle|v_{j}\cdot Rw_{1}\otimes u-v_{j}\cdot x|\leq|v_{j}|\epsilon R$

and

$\displaystyle|v_{j}\cdot Rw_{1}\otimes u|=R|v_{j}\cdot w_{1}||u|=R|v_{j}\cdot
w_{1}|.$

If we let

$\displaystyle f_{j}(y)=\chi_{[c_{1},c_{2}]}\left(\frac{|y|}{R}\right),\quad
y\in\mathbf{R}^{k},$

then $f_{j}(v_{j}\cdot x)=1$ if $x\in S_{R}$ and
$\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}}\approx R^{k/p_{j}+\lambda_{j}}$. Thus if
(1.2) holds with the indices $(1/p_{j},\lambda_{j})_{j=1}^{N}$, we have

$cR^{mk}\leq\int_{\mathbf{R}^{mk}}\prod_{j=1}^{N}f_{j}(v_{j}\cdot x)\,dx\leq
C\prod_{j=1}^{N}R^{k/p_{j}+\lambda_{j}}.$

Since this holds for all $R\in(0,\infty)$, we can conclude

$\displaystyle
m=\sum_{j=1}^{N}\left(\frac{1}{p_{j}}+\frac{\lambda_{j}}{k}\right),$

and so (1.4) is proved.

We turn to the proof of (1.9). To this end, let $V\subset\mathbf{R}^{m}$ be a
subspace. To begin we apply Lemma 3.1 to the pair of subspaces $\\{0\\}\subset
V$ to find $w_{1}\in V$ for which

$w_{1}\cdot v_{j}\neq 0,\quad v_{j}\in V.$

If $\\{v_{j}:v_{j}\notin V\\}$ is a nonempty set, then we find $w_{2}\in
V^{\perp}$ so that

$\displaystyle w_{2}\cdot v_{j}\neq 0,\quad v_{j}\notin V.$

This time around, we set

$\displaystyle S_{R}=B^{mk}(w_{1}\otimes
u,\epsilon)\cap(V\otimes\mathbf{R}^{k})+B^{mk}(Rw_{2}\otimes u,\epsilon
R)\cap(V^{\perp}\otimes\mathbf{R}^{k}).$

Here, $V\otimes\mathbf{R}^{k}=\\{x:x=v\otimes y,v\in V,y\in\mathbf{R}^{k}\\}$
and $u\in\mathbf{R}^{k}$ is a unit vector. Then we have

$\displaystyle|S_{R}|\approx R^{k\dim(V^{\perp})}.$

If we choose $\epsilon>0$ small and $R_{0}$ large, we can find $c_{1},c_{2}$
so that

$\displaystyle c_{1}\leq|v_{j}\cdot x|\leq c_{2},\quad v_{j}\in V,x\in S_{R},$

and

$\displaystyle Rc_{1}\leq|v_{j}\cdot x|\leq c_{2}R,\quad v_{j}\notin
V,\,R>R_{0},\,x\in S_{R}.$

Thus, with $f_{j}$ defined as

$\displaystyle f_{j}(y)=\begin{cases}\chi_{[c_{1},c_{2}]}(|y|),&v_{j}\in
V,\\\\[10.0pt] \chi_{[c_{1},c_{2}]}(|y|/R),&v_{j}\notin V,\end{cases}$

then it follows that $f_{j}(v_{j}\cdot x)=1$ if $x\in S_{R}$ and $R>R_{0}$. In
total, the boundedness of the form implies

$\displaystyle R^{k\dim(V^{\perp})}$ $\displaystyle\leq
C\int_{S_{R}}\prod_{j=1}^{N}f_{j}(v_{j}\cdot x)\,dx$ $\displaystyle\leq
C\prod_{j=1}^{N}\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}}$ $\displaystyle\leq
C\prod_{v_{j}\notin V}R^{k/p_{j}+\lambda_{j}}.$

Since this inequality holds for all $R>R_{0}$, we can conclude that

$\displaystyle\sum_{v_{j}\notin
V}\frac{k}{p_{j}}+\lambda_{j}\geq\dim(V^{\perp}).$

Finally, we establish (1.6), the inequality for the $\lambda_{j}$’s. Again,
fix a subspace $V\subset\mathbf{R}^{m}$. Choose $w_{1},w_{2}$ as before:
$w_{1}\in V$ so that $w_{1}\cdot v_{j}\neq 0$ for all $v_{j}\in V$, and
$w_{2}\in V^{\perp}$ so that $w_{2}\cdot v_{j}\neq 0$ for all $v_{j}\notin V$.
Set

$\displaystyle w_{N}=(w_{1}+Nw_{2})\otimes u,$

and then define

$\displaystyle S_{N}=B^{mk}(w_{N},\epsilon).$

Here, $u\in\mathbf{R}^{k}$ is a unit vector as usual. For $\epsilon>0$ small,
we have

$\displaystyle c_{1}\leq|v_{j}x|\leq c_{2},\quad x\in S_{N},\,v_{j}\in V,$

and if $N$ is large, say $N>N_{0}$,

$\displaystyle|v_{j}\cdot x-v_{j}\cdot w_{N}\otimes u|\leq c\epsilon,\quad
x\in S_{N}.$

This time around, set

$\displaystyle f_{j}(y)=\begin{cases}\chi_{[c_{1},c_{2}]}(|y|),&v_{j}\in
V,\\\\[10.0pt] \chi_{B(v_{j}\cdot w_{N}u,c\epsilon)}(|y|),&v_{j}\notin
V.\end{cases}$

Then it follows that

$\displaystyle\prod_{j=1}^{N}f_{j}(v_{j}\cdot x)=1,\quad\mbox{if }\,x\in
S_{N},\,N>N_{0},$

and $\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}}\approx 1$ if $v_{j}\in V$ and
$\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}}\approx N^{\lambda_{j}}$ if $v_{j}\notin
V$.

Thus for $N\geq N_{0}$, the boundedness of the form implies

$C\leq\int_{\mathbf{R}^{mk}}\prod_{j=1}^{N}f_{j}(v_{j}\cdot
x)\,dx\leq\prod_{j=1}^{N}\|f_{k}\|_{L^{p_{j}}_{\lambda_{j}}}\\\
\approx\prod_{v_{j}\notin V}N^{\lambda_{j}}.$

Since this inequality holds for all $N>N_{0}$, we have $\sum_{v_{j}\notin
V}\lambda_{j}\geq 0$ as desired.

Our last step is to establish that the condition (1.7) must hold if we have
(1.2). Towards this end, we define

$f_{j}(t)=\sum_{\ell=1}^{\infty}a_{j,\ell}2^{-\ell(k/p_{j}+\lambda_{j})}\chi_{[2^{\ell},2^{\ell+1})}(|t|),\quad
t\in\mathbf{R}^{k},$

where we assume each $a_{j,\ell}\geq 0$. With this choice, we have

$\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}}\leq
C\left(\sum_{\ell=1}^{\infty}a_{j,\ell}^{p_{j}}\right)^{1/p_{j}}.$

We will set $a_{j,\ell}=\ell^{-(1+\epsilon)/p_{j}}$ where $\epsilon>0$. With
this choice, we have $f_{j}\in L^{p_{j}}_{\lambda_{j}}.$

Next, we use Lemma 3.1 to find $w\in\mathbf{R}^{m}$ so that

$v_{j}\cdot w\neq 0,\quad v_{j}\in E.$ (3.2)

As before we choose a unit vector $u\in\mathbf{R}^{k}$ and set
$S_{\ell}=B^{mk}(2^{\ell}w\otimes u,2^{\ell}\epsilon)$. Thanks to (3.2) and
our choice of $a_{j,\ell}$, we may find $\ell_{0}$ so that

$f_{j}(v_{j}\cdot x)\geq
c\ell^{-(1+\epsilon)/p_{j}}2^{-\ell(k/p_{j}+\lambda_{j})},\qquad\ell\geq\ell_{0},\,x\in
S_{\ell}.$ (3.3)

Using (3.3) and that $|S_{\ell}|\approx 2^{k\ell m}$, we have

$\sum_{\ell\geq\ell_{0}}2^{klm}\prod_{j=1}^{N}\ell^{-(1+\epsilon)/p_{j}}2^{-\ell(k/p_{j}+\lambda_{j})}\leq\sum_{\ell=\ell_{0}}^{\infty}\int_{S_{\ell}}\prod_{j=1}^{N}f_{j}(v_{j}\cdot
x)\,dx\leq C\prod_{j=1}^{N}\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}},$

where the last inequality follows since we assume the estimate (1.2). Using
our observation about $\|f_{j}\|_{L^{p_{j}}_{\lambda_{j}}}$, we may conclude

$\sum_{\ell=\ell_{0}}^{\infty}\ell^{-(1+\epsilon)\sum_{j=1}^{N}1/p_{j}}\leq
C(\sum_{\ell=1}^{\infty}\ell^{-(1+\epsilon)})^{\sum_{j=1}^{N}1/p_{j}}.$

In particular, we have that the sum
$\sum_{\ell=\ell_{0}}^{\infty}\ell^{-(1+\epsilon)\sum_{j=1}^{N}1/p_{j}}$ is
finite for each $\epsilon>0$. This implies that we must have (1.7). ∎

##  4 Examples

In this section, we give several of examples of forms for where we can use our
theorem to study the boundedness. We also give an example of a non-generic set
of vectors where a naive extension of our methods fails to establish
boundedness in the interior of the polytope defined by the necessary
conditions in Theorem 1.8.

  * Example.

Let $E=\\{e_{1}+\dots+e_{m},e_{1},\dots,e_{m}\\}\subset\mathbf{R}^{m}$. Then
it is easy to see that the set $E$ is generic. Thus Theorem 1.3 will apply to
the form

$\int_{\mathbf{R}^{m}}f_{0}(x_{1}+\dots+x_{m})\prod_{i=1}^{m}f_{i}(x_{i})\,dx.$

Our next example shows how to generate arbitrarily large sets of generic
vectors $E$ and helps to justify our use of the term generic.

  * Example.

If $E_{N}=\\{v_{1},\dots,v_{N}\\}$ is a generic family in $\mathbf{R}^{m}$, we
may add an additional vector $v_{N+1}$ so that
$E_{N+1}=\\{v_{1},\dots,v_{N+1}\\}$ is a generic set. By the generic condition
on $E_{N}$, for each subset $K\subset E_{N}$ with $\\#K=m-1$, $\mathop{\rm
span}\nolimits(K)$ is a subspace of dimension $m-1$. As $\mathbf{R}^{m}$
cannot be the union of a finite number of proper subspaces, we may find a
vector $v_{N+1}$ which does not belong to any of the subspaces spanned the
subsets of $E_{N}$ of cardinality $m-1$. Thus, the set $E_{N+1}$ is generic.
For completeness, we note that we can begin with the standard basis and then
use the inductive step above to generate large generic sets of vectors.

Our final observation shows some of the aforementioned limitations of the
current methods. As we note in Theorem 1.8, our necessary conditions do not
require the set of vectors $E$ to be generic. When we began this work, we had
hoped to establish a result that was close to necessary and sufficient for
forms that are based on general sets of vectors $E$. Unfortunately, we are not
able to do this. We will give a non-generic set of five vectors in
$\mathbf{R}^{3}$ and show that a naive attempt to extend the proof of Theorem
1.3 fails to establish that (1.2) holds for indices in the interior of the
polytope given by Theorem 1.8.

  * Example.

Consider the set of 5 vectors in $\mathbf{R}^{3}$ given by

$E=\\{e_{1},e_{1}+e_{2},e_{1}+e_{3},e_{1}-e_{2},e_{1}-e_{3}\\}.$

We will label these vectors by
$v_{1}=e_{1},v_{2}=e_{1}+e_{2},v_{3}=e_{1}+e_{3},v_{4}=e_{1}-e_{2},v_{5}=e_{1}-e_{3}$.
Note that there are two dependent sets of three vectors in $E$.

As before, the result of Bennett et al. characterizes the indices for which we
have (1.2) when the exponents for the weights $\lambda_{j}$ are zero.
Continuing, we may extend the result to Lorentz spaces and use the generalized
Hölder’s inequality to obtain (1.2) in the case that the weights are non-
negative. We only need to note that as long as no two vectors are collinear,
we may use (1.5) as in the proof of (2.4) to conclude that
$0<1/p_{j}+\lambda_{j}<1$ (here $k=1$).

We consider the vector of indices

$(1/p_{1},\dots,1/p_{5},\lambda_{1},\dots,\lambda_{5})=(11/15,6/15,2/3,6/15,2/3,-2/15,2/15,0,2/15,0).$

We leave it as an exercise to verify that this vector of indices satisfies the
conditions of Theorem 1.3. The most interesting condition to check is (1.5),
and here one must note that because of the linear dependencies
$2v_{1}=v_{2}+v_{4}$ and $2v_{1}=v_{3}+v_{5}$, there are two sums in (1.5) to
check where $\mbox{dim}(V)=2$ and the condition $v_{j}\notin V$ is true for
two indices $j$ rather than three due to the linear dependence.

We observe that we have a linear dependency $2v_{1}=v_{2}+v_{4}$ and arguing
as in (2.19) we can show that

$\Lambda(f_{1},\dots f_{5})\leq
C(\Lambda(|\cdot|^{-2/15}f_{1},|\cdot|^{2/15}f_{2},f_{3},f_{4},f_{5})+\Lambda(|\cdot|^{-2/15}f_{1},f_{2},f_{3},|\cdot|^{2/15}f_{4},f_{5})).$

We would like to have the estimate (1.2) for the vectors of indices:

$\displaystyle(1/p_{1},\dots,1/p_{5},\beta_{1}^{(2,0)},\dots\beta_{5}^{(2,0)})$
$\displaystyle=(11/15,6/15,2/3,6/15,2/3,0,0,0,2/15,0),$
$\displaystyle(1/p_{1},\dots,1/p_{5},\beta_{1}^{(4,0)},\dots,\beta_{5}^{(4,0)})$
$\displaystyle=(11/15,6/15,2/3,6/15,2/3,0,2/15,0,0,0).$

If we consider the inequality (1.5) for the subspace $V=\mathop{\rm
span}\nolimits\\{v_{1},v_{3},v_{5}\\}=\mathop{\rm
span}\nolimits\\{e_{1},e_{3}\\}$, we see that for both $\beta^{(2,0)}$ and
$\beta^{(4,0)}$

$\sum_{v_{j}\notin
V}\frac{1}{p_{j}}+\beta^{(k,0)}_{j}=\frac{1}{p_{2}}+\beta^{(k,0)}_{2}+\frac{1}{p_{4}}+\beta^{(k,0)}_{4}=\frac{14}{15}<1=3-\dim
V.$

Thus, this avenue of proof would require us to use an estimate which Theorem
1.8 tells us cannot hold.

We close by listing several problems related to our work worthy of further
study.

  * •

Find conditions which are close to necessary and sufficient for forms that are
based on general sets of vectors $E$, rather than being restricted to generic
sets of vectors.

  * •

Consider weighted estimates for the more general forms such as those studied
in Bennett et al. [3].

  * •

Find conditions on families of more general weights which allow us to
establish that a Brascamp-Lieb form is bounded on weighted $L^{p}$-spaces.

## References

  * [1] Franck Barthe.  On a reverse form of the Brascamp-Lieb inequality.  Invent. Math., 134(2):335–361, 1998.
  * [2] R. Beals and R.R. Coifman.  The spectral problem for the Davey-Stewartson and Ishimori hierarchies.  In Nonlinear evolution equations: Integrability and spectral methods, pages 15–23. Manchester University Press, 1988.
  * [3] Jonathan Bennett, Anthony Carbery, Michael Christ, and Terence Tao.  Finite bounds for Hölder-Brascamp-Lieb multilinear inequalities.  Math. Res. Lett., 17(4):647–666, 2010.
  * [4] Neal Bez, Sanghyuk Lee, Shohei Nakamura, and Yoshihiro Sawano.  Sharpness of the Brascamp-Lieb inequality in Lorentz spaces.  Electron. Res. Announc. Math. Sci., 24:53–63, 2017.
  * [5] H. J. Brascamp, Elliott H. Lieb, and J. M. Luttinger.  A general rearrangement inequality for multiple integrals.  J. Functional Analysis, 17:227–237, 1974.
  * [6] R. M. Brown.  Estimates for the scattering map associated with a two-dimensional first-order system.  J. Nonlinear Sci., 11(6):459–471, 2001.
  * [7] R. M. Brown, C. W. Lee, and K. A. Ott.  Estimates for Brascamp-Lieb forms in $L^{p}$-spaces with power weights.  Proc. Amer. Math. Soc., 149(2):747–760, 2021.
  * [8] R. M. Brown, K. A. Ott, and P. A. Perry.  Action of a scattering map on weighted Sobolev spaces in the plane.  J. Funct. Anal., 271(1):85–106, 2016.
  * [9] E. A. Carlen, E. H. Lieb, and M. Loss.  A sharp analog of Young’s inequality on $S^{N}$ and related entropy inequalities.  J. Geom. Anal., 14(3):487–520, 2004.
  * [10] M. Christ.  On the restriction of the Fourier transform to curves: endpoint results and the degenerate case.  Trans. Amer. Math. Soc., 287(1):223–238, 1985.
  * [11] A.S. Fokas and M.J. Ablowitz.  On the inverse scattering transform of multidimensional nonlinear equations related to first-order systems in the plane.  J. Math. Phys., 25:2494–2505, 1984.
  * [12] Loukas Grafakos.  On multilinear fractional integrals.  Studia Math., 102(1):49–56, 1992.
  * [13] Loukas Grafakos and Nigel Kalton.  Some remarks on multilinear maps and interpolation.  Math. Ann., 319(1):151–180, 2001.
  * [14] S. Janson.  On interpolation of multi-linear operators.  Function Spaces and Applications (Proceedings, Lund 1986), Lecture Notes in Math, 1302:290–302, 1986.
  * [15] Carlos E. Kenig and Elias M. Stein.  Multilinear estimates and fractional integration.  Math. Res. Lett., 6(1):1–15, 1999.
  * [16] Yasuo Komori-Furuya.  Weighted estimates for bilinear fractional integral operators: a necessary and sufficient condition for power weights.  Collect. Math., 71(1):25–37, 2020.
  * [17] Kabe Moen.  New weighted estimates for bilinear fractional integral operators.  Trans. Amer. Math. Soc., 366(2):627–646, 2014.
  * [18] Adrian Nachman, Idan Regev, and Daniel Tataru.  A nonlinear Plancherel theorem with applications to global well-posedness for the defocusing Davey-Stewartson equation and to the inverse boundary value problem of Calderón.  Invent. Math., 220(2):395–451, 2020.
  * [19] Z. Nie.  Estimates for a class of multi-linear forms.  PhD thesis, University of Kentucky, 2009.
  * [20] Zhongyi Nie and Russell M. Brown.  Estimates for a family of multi-linear forms.  J. Math. Anal. Appl., 377(1):79–87, 2011.
  * [21] Richard O’Neil.  Convolution operators and $L(p,\,q)$ spaces.  Duke Math. J., 30:129–142, 1963.
  * [22] Peter A. Perry.  Global well-posedness and long-time asymptotics for the defocussing Davey-Stewartson II equation in $H^{1,1}(\mathbb{C})$.  J. Spectr. Theory, 6(3):429–481, 2016.  With an appendix by Michael Christ.
  * [23] E. M. Stein and Guido Weiss.  Fractional integrals on $n$-dimensional Euclidean space.  J. Math. Mech., 7:503–514, 1958.
  * [24] E.M. Stein and Guido Weiss.  Introduction to Fourier analysis on Euclidean spaces.  Princeton University Press, 1971.


# Flip colouring of graphs II

Xandru Mifsud
University of Malta

###### Abstract

We give results concerning two problems on the recently introduced flip
colourings of graphs, a new class of local v. global phenomena. We prove that
for $(b,r)$-flip sequences with $4\leq
b<r<b+2\left\lfloor\frac{b+2}{6}\right\rfloor^{2}$, small constructions of
$(b,r)$-flip graphs on $O(b+r)$ vertices are possible. Furthermore, we prove
that there exists $k$-flip sequences $(a_{1},\dots,a_{k})$ where $k>4$, such
that $a_{k}$ can be arbitrarily large whilst $a_{i}$ is constant for $1\leq
i<\frac{k}{4}$.

##  1 Introduction

Flip colourings of graphs were first introduced in [4], as yet another example
of local versus global phenomena studied in graph theory, such as [1, 5, 6] .
Several open-problems concerning flip colourings were posed in [4], which we
consider here. Before we proceed any further, we establish some notational
conventions.

The open-neighbourhood $N^{G}(v)$ is the set of neighbours of a vertex $v$ in
a graph $G$, and the closed-neighbourhood $N^{G}[v]$ is $N^{G}(v)\cup\\{v\\}$.
Let $k\in\mathbb{N}$ and let $f\colon E(G)\rightarrow\\{1,\dots,k\\}$ be an
edge-colouring of $G$. For $1\leq j\leq k$,

  1. i.

Given a subset $S$ of $V(G)$, $E^{G}_{j}(S)$ is the set of edges coloured $j$
in the vertex-induced subgraph of $G$ by $S$, and
$e^{G}_{j}(S)=|E^{G}_{j}(S)|$.

  2. ii.

For a vertex $v$, let $e^{G}_{j}[v]=e^{G}_{j}\left(N^{G}[v]\right)$ and
$e^{G}_{j}(v)=e^{G}_{j}\left(N^{G}(v)\right)$.

  3. iii.

For a vertex $v$, $\deg_{j}(v)$ is the number of edges incident to $v$
coloured $j$.

When there is no ambiguity, we simplify our notation by removing any symbolic
reference to the graph.

We are interested in the following problem on flip-graphs: Given $k\geq 2$, a
$d$-regular graph $G$ and an increasing positive-integer sequence
$(a_{1},\dots,a_{k})$ such that $d=\sum_{j=1}^{k}a_{j}$, does there exists an
edge-colouring on $k$ colours such that:

  1. i.

$E_{j}(V)$ spans an $a_{j}$-regular subgraph, namely $\deg_{j}(v)=a_{j}$ for
every $v\in V$,

  2. ii.

and for every vertex $v\in V$, $e_{k}[v]<e_{k-1}[v]<\ldots<e_{1}[v]$.

If such an edge-colouring exists then $G$ is said to be an
$(a_{1},\ldots,a_{k})$-flip graph, or more simply a $k$-flip graph, and
$(a_{1},\dots,a_{k})$ is called a $k$-flip sequence of $G$.

The case when $k=2$ is fully characterised by the following theorem.

######  Theorem 1.1 (Theorem 3.1, [4]).

Let $r,b\in\mathbb{N}$. If $3\leq b<r\leq\binom{b+1}{2}-1$ then there exists a
$(b,r)$-flip graph, and both the upper and lower bounds are sharp.

Given a $k$-flip sequence $(a_{1},\dots,a_{k})$, a problem of interest is that
of finding the smallest order $h(a_{1},\dots,a_{k})$ of a graph realising it.
In the case when $k=2$, the following theorem gives the best known upper-bound
on $h(b,r)$.

######  Theorem 1.2 (Corollary 3.6, [4]).

Let $b,r\in\mathbb{N}$ such that $3\leq b<r\leq\binom{b+1}{2}-1$. Then,

$h(b,r)\leq
2\left(r+b+1-\left\lfloor\dfrac{5+\sqrt{1+8(r-b)}}{2}\right\rfloor\right)\left\lfloor\dfrac{5+\sqrt{1+8(r-b)}}{2}\right\rfloor\,$

Smaller constructions for certain 2-flip sequences, such as $(3,4)$, than
those given by this upper-bound are known. We shall improve this upper-bound
to $h(b,r)\leq
16\left(2+\left\lfloor\frac{r}{2}\right\rfloor+\left\lfloor\frac{b+2}{2}\right\rfloor-2\left\lfloor\frac{b+2}{6}\right\rfloor\right)$
for $4\leq b<r<b+2\left\lfloor\frac{b+2}{6}\right\rfloor^{2}$.

For three colours, as in the case for two colours (Theorem 1.1), the largest
colour-degree is quadratically bound in terms of the smallest.

######  Theorem 1.3 (Theorem 4.1, [4]).

If $(a_{1},a_{2},a_{3})$ is a $3$-flip sequence, then

$a_{3}<2(a_{1})^{2}$

However, for four or more colours, it is known that no such relationship
exists, as highlighted in the following theorem.

######  Theorem 1.4 (Theorem 4.3, [4]).

Let $k\in\mathbb{N},k>3$. Then there is some constant $m=m(k)\in\mathbb{N}$
such that for all $N\in\mathbb{N}$, there exists a $k$-flip sequence
$\left(a_{1},a_{2},\dots,a_{k}\right)$ such that $a_{1}=m$ and $a_{k}>N$.

Let $q(k)$ be an integer, $q(k)<k$, such that there exists some
$h(k)\in\mathbb{N}$ and for all $N\in\mathbb{N}$, there is a $k$-flip sequence
$(a_{1},\dots,a_{k})$ where $a_{q(k)}=h(k)$ and $a_{k}>N$. By Theorem 1.4 we
establish that $q(k)\geq 1$ for all $k\geq 4$. We are interested in finding
the longest possible sub-sequence $(a_{1},\dots,a_{q(k)})$ such that $a_{k}$
is independent of this sub-sequence. Our contribution shall be that

$\left\lceil\frac{k}{4}\right\rceil-1\leq q(k)<\begin{cases}\
\frac{k}{3}&\mbox{if $k\mod 3=0$}\\\
\left\lceil\frac{k}{2}\right\rceil&\mbox{otherwise}\end{cases}$

for $k>4$.

Two foundational concepts employed heavily throughout this paper are Cayley
graphs and sum-free sets, which we introduce next.

Let $\Gamma$ be a group. We shall denote the identity of a group $\Gamma$ by
$1_{\Gamma}$. We say that a group is Abelian if it is endowed with a
commutative group operation. All groups considered are assumed to be finite.
By $\mathbb{Z}_{n}$ we denote the group of integers under addition modulo $n$.

Let $S$ be a subset of $\Gamma$ such that $S$ is inverse-closed and does not
contain the identity. The Cayley graph $\mathsf{Cay}\left(\Gamma;S\right)$ has
vertex set $\Gamma$ and edge set $\left\\{\\{g,gs\\}\colon s\in
S,g\in\Gamma\right\\}$. The set $S$ is termed as the connecting set.

Let $\Gamma$ be an Abelian group and let $A,B\subseteq\Gamma$. The sum-set
$A+B$ is the set $\\{a+b\colon a\in A,b\in B\\}$. By $2A$ we denote the set
$A+A$ whilst by $A^{-1}$ we denote the set of inverses of $A$. We say that $A$
is sum-free if $2A\cap A=\emptyset$.

In the case when $\Gamma=\mathbb{Z}_{n}$, we write $A<B$ if, and only if,
given any $x\in A$ and $y\in B$ we have $(x\mod n)<(y\mod n)$.

In Section 2 we shall outline a number of properties of products and packings
of edge-coloured graphs. Section 3 shall be dedicated to improving the upper-
bound on $h(b,r)$, while Section 4 presents lower and upper bounds on $q(k)$
for $k\geq 4$. In Section 5 we give some concluding remarks and further open
problems to those in [4].

##  2 New edge-coloured graphs from old

We begin by first outlining the toolset required, looking at a number of graph
operations and how they affect edge-colourings. Namely we will consider the
Cartesian and strong products of graphs, as well as the packing of graphs.

###  2.1 Products of edge-coloured graphs

We begin by recalling the definition of the strong product of two graphs $G$
and $H$, and in particular how an edge-colouring of $G\boxtimes H$ is
inherited from edge-colourings of its factors.

######  Definition 2.1 (Strong product).

The strong product $G\boxtimes H$ of two graphs $G$ and $H$ is the graph such
that $V\left(G\boxtimes H\right)=V(G)\times V(H)$ and there is an edge
$\left\\{(u,v),(u^{\prime},v^{\prime})\right\\}$ in $G\boxtimes H$ if, and
only if, either $u=u^{\prime}$ and $v\sim v^{\prime}$ in $H$, or
$v=v^{\prime}$ and $u\sim u^{\prime}$ in $G$, or $u\sim u^{\prime}$ in $G$ and
$v\sim v^{\prime}$ in $H$.

We extend the edge-colourings of $G$ and $H$ to an edge-colouring of
$G\boxtimes H$ as follows. Consider the edge
$e=\left\\{(u,v),(u^{\prime},v^{\prime})\right\\}$ in $G\boxtimes H$; if
$u=u^{\prime}$ then $e$ inherits the colouring of the edge
$\\{v,v^{\prime}\\}$ in $H$, otherwise if $u\neq u^{\prime}$ the colouring of
the edge $\\{v,v^{\prime}\\}$ in $G$ is inherited. This colouring inheritance
is illustrated in Figure 1, with its properties summarised in Lemma 2.1.

######  Lemma 2.1.

Let $G$ and $H$ be edge-coloured from $\\{1,\dots,k\\}$. Then in the coloured
strong product $G\boxtimes H$, for any $1\leq j\leq k$ and $(u,v)\in
V(G\boxtimes H)$,

  1. i.

$\deg_{j}\big{(}(u,v)\big{)}=\deg_{j}^{H}(v)+\deg_{j}^{G}(u)\left(1+\deg^{H}(v)\right)$

  2. ii.

$e_{j}\big{[}(u,v)\big{]}=e_{j}^{H}[v]\left(1+\deg^{G}(u)\right)+e_{j}^{G}[u]\left(1+\deg^{H}(v)+2\sum\limits_{i=1}^{k}e_{i}^{H}[v]\right)$

Figure 1: Illustration of Lemma 2.1, with the closed-neighbourhood of $(u,v)$
in $K_{3}\boxtimes P_{3}$ highlighted.

Another useful product shall be Cartesian product, which we recall below.

######  Definition 2.2 (Cartesian product).

The Cartesian product $G\ \square\ H$ of the graphs $G$ and $H$ is the graph
such that $V\left(G\ \square\ H\right)=V(G)\times V(H)$ and there is an edge
$\left\\{(u,v),(u^{\prime},v^{\prime})\right\\}$ in $G\ \square\ H$ if, and
only if, either $u=u^{\prime}$ and $v\sim v^{\prime}$ in $H$, or
$v=v^{\prime}$ and $u\sim u^{\prime}$ in $G$.

We extend the edge-colourings of $G$ and $H$ to an edge-colouring of $G\
\square\ H$ as follows. Consider the edge
$e=\left\\{(u,v),(u^{\prime},v^{\prime})\right\\}$ in $G\ \square\ H$; if
$u=u^{\prime}$ then $e$ inherits the colouring of the edge
$\\{v,v^{\prime}\\}$ in $H$, otherwise if $v=v^{\prime}$ the colouring of the
edge $\\{u,u^{\prime}\\}$ in $G$ is inherited. This colouring inheritance is
illustrated in Figure 2, with its properties summarised in Lemma 2.2.

Figure 2: Illustration of Lemma 2.2, with the closed-neighbourhood of $(u,v)$
in $K_{3}\ \square\ P_{3}$ highlighted.

######  Lemma 2.2.

Let $G$ and $H$ be edge-coloured from $\\{1,\dots,k\\}$. Then in the coloured
Cartesian product $G\ \square\ H$, for any $1\leq j\leq k$ and $(u,v)\in V(G\
\square\ H)$,

  1. i.

$\deg_{j}\big{(}(u,v)\big{)}=\deg_{j}^{G}(u)+\deg_{j}^{H}(v)$

  2. ii.

$e_{j}\left[(u,v)\right]=e_{j}^{G}[u]+e_{j}^{H}[v]$

###  2.2 Packing of edge-coloured graphs

In this section we shall consider, in particular, the packing of edge-coloured
Cayley graphs. We first formally define graph packing.

######  Definition 2.3 (Packing).

Two graphs $G$ and $H$ are said to pack if there exists bijections $g\colon
V(G)\rightarrow\\{1,\dots,n\\}$ and $h\colon V(H)\rightarrow\\{1,\dots,n\\}$
such that the images of $E(G)$ and $E(H)$ under $g$ and $h$, respectively, do
not intersect.

The packing of $G$ and $H$ is the graph with vertex set $\\{1,\dots,n\\}$ and
edge set being union of the images of $E(G)$ and $E(H)$ under $g$ and $h$,
respectively.

An edge-colouring is naturally inherited by a packing of $G$ and $H$, by
keeping the original colour of every single edge. Note that by the definition
of a packing, the edge-colouring is well-defined.

Counting the colour-degree of every vertex in a packing of $G$ and $H$, in
terms of the colour-degrees of $G$ and $H$, is straight-forward, however
counting the coloured closed-neighbourhood sizes is more difficult. In certain
cases such as the case when $G$ and $H$ are monochromatically coloured Cayley
graphs on an Abelian group, we can do such counting. This is summarised in
Proposition 2.3.

Let $S$ and $T$ be two disjoint inverse-closed subsets of $\Gamma$ not
containing $1_{\Gamma}$. Consider the two Cayley graphs
$G=\mathsf{Cay}\left(\Gamma;S\right)$ and
$H=\mathsf{Cay}\left(\Gamma;T\right)$. Then the Cayley graph
$\mathsf{Cay}\left(\Gamma;S\cup T\right)$ is a packing of $G$ and $H$. Cayley
graphs enjoy a number of properties, most notably that they are vertex-
transitive.

######  Proposition 2.3.

Let $\Gamma$ be an Abelian group and let $R,B$ be disjoint inverse-closed
subsets of $\Gamma$ which do not contain $1_{\Gamma}$. Let
$G=\mathsf{Cay}\left(\Gamma;B\right)$ and
$H=\mathsf{Cay}\left(\Gamma;R\right)$ be monochromatically edge-coloured using
colours $1$ and $2$, respectively. Then in $\mathsf{Cay}\left(\Gamma;B\cup
R\right)$, for $v\in\Gamma$,

  1. i.

$\deg_{1}(v)=\deg^{G}(v)$ and $\deg_{2}(v)=\deg^{H}(v)$

  2. ii.

$e_{1}[v]-e_{2}[v]=\left(e_{1}^{G}[v]-e_{2}^{H}[v]\right)+\left(e_{2}^{H}\left(N^{G}[v]\right)-e_{1}^{G}\left(N^{H}[v]\right)\right)$

  3. iii.

Furthermore, if $(R+B)\cap R=\emptyset$ and $e_{1}^{G}[v]>e_{2}^{H}[v]$, then
$e_{1}[v]>e_{2}[v]$.

###### Proof.

It suffices to consider a single vertex, say $1_{\Gamma}$, by virtue of the
vertex-transitivity of Cayley graphs. Note that $B=N^{G}[1_{\Gamma}]$ and
$R=N^{H}[1_{\Gamma}]$. More so, since $R$ and $B$ are disjoint, the edge-
colouring of the union is well-defined and $N[1_{\Gamma}]=B\ \dot{\cup}\ R$.
Clearly all the edges incident to $1_{\Gamma}$ are incident to $1_{\Gamma}$ in
either $G$ or $H$, and therefore $\deg_{1}(v)=\deg^{G}(v)$ and
$\deg_{2}(v)=\deg^{H}(v)$. We now count the number of edges coloured $1$ in
$N[1_{\Gamma}]$. We have three cases for an edge $\\{u,v\\}$ coloured 1,

  1. i.

Both $u$ and $v$ are in $B$, of which there are $e_{1}^{G}[1_{\Gamma}]$ such
edges.

  2. ii.

Both $u$ and $v$ are in $R$, of which there are $e_{1}^{G}\left(R\right)$ such
edges.

  3. iii.

The vertex $u$ is in $B$ and the vertex $v$ is in $R$. We show that the number
of such edges is $2e_{2}^{H}\left(B\right)$, i.e. twice the number of edges
coloured $2$ amongst the neighbours of $1_{\Gamma}$ in $G$.

Since $\\{u,v\\}$ is coloured $1$ then it is an edge in the Cayley graph $G$.
Therefore there is some $x\in B$ such that $u=xv$. Since $v^{-1}\in R$, then
$\\{u,x\\}$ is an edge in $H$. Hence $x=uv^{-1}$ and since $\Gamma$ is Abelian
and $u\in B$, $\\{x,v^{-1}\\}$ is an edge in $G$.

In other words, for every edge $\\{u,x\\}$ in $H$, where $u,x\in B$ and $u=xv$
for some $v\in R$, there are two edges $\\{u,v\\}$ and $\\{x,v^{-1}\\}$ in $G$
with one vertex in $R$ and one vertex in $B$. This counting argument is
illustrated in Figure 4.

Hence,
$e_{1}[1_{\Gamma}]=e_{1}^{G}[1_{\Gamma}]+e_{1}^{G}\left(R\right)+2e_{2}^{H}\left(B\right)$.
Repeating the argument for $e_{2}[1_{\Gamma}]$ and subtracting, we get (ii) as
required.

$1_{\Gamma}$$u=xv$$x=uv^{-1}$$v$$v^{-1}$ Figure 3: Illustration of the
counting argument in the proof of Proposition 2.3, where the red edge
$\\{u,v\\}$ between two blue neighbours of $1_{\Gamma}$ corresponds to two
blue edges, each incident to a blue and red neighbour of $1_{\Gamma}$.

Now, suppose that $(R+B)\cap R=\emptyset$ and $e_{1}^{G}[v]>e_{2}^{H}[v]$.
Then given any $u\in R$ and $v\in B$, $uv\notin R$ and therefore $\\{u,uv\\}$
is not an edge in the subgraph of $\mathsf{Cay}\left(\Gamma;B\cup R\right)$
induced by $R$. In other-words, this subgraph has no edges coloured $1$ and
therefore $e^{G}_{1}\left(R\right)=0$. Therefore (iii) follows from (ii). ∎

##  3 Bounding $h(b,r)$ through Cayley flip graphs

If we can construct Cayley graphs satisfying the conditions in Proposition 2.3
(iii) and $|B|<|R|$, we can then construct a $\left(|B|,|R|\right)$-flip graph
(which in particular turns out to be another Cayley graph). Note that the
requirement $e_{1}[v]>e_{2}[v]$ necessitates that $|B|\geq 3$. Moreover, from
the proof of Proposition 2.3 (iii) we have that in this case,

$\binom{|B|+1}{2}\geq
e_{1}^{G}[v]+e_{2}^{H}\left(N^{G}[v]\right)>e_{2}^{H}[v]\geq|R|$

and therefore the constraints of Theorem 1.1 are satisfied. In the proof of
the following theorem we shall demonstrate not only that such a construction
is feasible, but also that they can be done with a small number of vertices.

######  Theorem 3.1.

Let $b,r\in\mathbb{N}$ such that $4\leq
b<r<b+2\left\lfloor\frac{b+2}{6}\right\rfloor^{2}$. Then,

$h(b,r)\leq
8\lambda_{b,r}\left(2+\bigg{\lfloor}\dfrac{r}{2}\bigg{\rfloor}+\bigg{\lfloor}\dfrac{b+2}{2}\bigg{\rfloor}-2\bigg{\lfloor}\dfrac{b+2}{6}\bigg{\rfloor}\right)$

where $\lambda_{b,r}=\max\\{1,\left(b\mod 2\right)+\left(r\mod 2\right)\\}$.

A key step in our proof will be the choice of suitably large subsets of
$\mathbb{Z}_{n}$ which are both inverse-closed and sum-free. Sum-free sets in
Abelian groups have been studied vastly and are of interest in additive
combinatorics and number theory, see [2, 7, 8]. We therefore begin with the
following useful lemma.

######  Lemma 3.2.

Let $A_{0},B_{0}$ be non-empty disjoint integer intervals of
$\left(\frac{n}{8},\frac{n}{4}\right)$ in $\mathbb{Z}_{n}$, such that
$A_{0}<B_{0}$. Let $B_{1}\subseteq B_{0}$ be an integer interval, $A=A_{0}\cup
A_{0}^{-1}$ and $B=B_{0}\cup B_{0}^{-1}\cup 2B_{1}\cup 2B_{1}^{-1}$. Then,
$\left(A+B\right)\cap A=\emptyset$. Moreover if $n$ is even,
$\left(A+\left\\{\frac{n}{2}\right\\}\right)\cap A=\emptyset$ and furthermore
if $\min(B_{1})\geq\frac{3n}{16}$ then
$\left(\left\\{\frac{n}{2}\right\\}+B\right)\cap A=\emptyset$.

###### Proof.

Since $A_{0}$ and $B_{0}$ are disjoint integer intervals of
$\left(\frac{n}{8},\frac{n}{4}\right)$ such that $A_{0}<B_{0}$, then there
exists integers $m,l,M,L$ such that $\frac{n}{8}<m<l<L<M<\frac{n}{4}$,
$A_{0}=\left[m,l\right]$ and $B_{0}=\left[L,M\right]$. Observe that the sets
$A_{0}$, $B_{0}$, $2B_{1}$ and their inverses are all disjoint and, in the
case when $n$ is even, none include the involution $\frac{n}{2}$.

Now, $\min\left(A_{0}+2B_{0}^{-1}\right)=(m-2M)\mod n>\max(A_{0})$ and

$\max\left(A_{0}+2B_{0}^{-1}\right)=l-2L<-l=\min\left(A_{0}^{-1}\right)$

Hence $A_{0}<A_{0}+2B_{0}^{-1}<A_{0}^{-1}$ and therefore since $B_{1}\subseteq
B_{0}$, $\left(A_{0}+2B_{1}^{-1}\right)\cap A=\emptyset$.

A similar argument follows for every possible summation, in order to obtain
that $(A+B)\cap A=\emptyset$, as required.

Now suppose that $n$ is even. Since
$A+\left\\{\frac{n}{2}\right\\}\subseteq\left[\frac{n}{4},\frac{3n}{8}\right]\cup\left[\frac{5n}{8},\frac{3n}{4}\right]$
then $\left(A+\left\\{\frac{n}{2}\right\\}\right)\cap A=\emptyset$ as
required.

Also, $\left\\{\frac{n}{2}\right\\}+B_{0}\cup
B_{0}^{-1}\subseteq\left[\frac{n}{4},\frac{3n}{8}\right]\cup\left[\frac{5n}{8},\frac{3n}{4}\right]$.
Moreover, $\min\left(\left\\{\frac{n}{2}\right\\}+2B_{1}^{-1}\right)>0$. If
$\min(B_{1})\geq\frac{3n}{16}$, then

$\max\left(\left\\{\frac{n}{2}\right\\}+2B_{1}^{-1}\right)=\frac{n}{2}-2\min(B_{1})\leq\frac{n}{8}$

and consequently $\left(\left\\{\frac{n}{2}\right\\}+2B_{1}^{-1}\right)\cap
A=\emptyset$. By a similar argument we obtain that
$\left(\left\\{\frac{n}{2}\right\\}+2B_{1}\right)\cap A=\emptyset$ and hence
$\left(\left\\{\frac{n}{2}\right\\}+B\right)\cap A=\emptyset$, as required. ∎

$1_{\Gamma}$$u=xv$$x=uv^{-1}$$v$$v^{-1}$$10$$9$$8$$28$$-8$$-9$$-10$$22$$-22$$12$$11$$-11$$-12$$T_{0}^{-1}$$T_{0}$$2T_{2}$$2T_{2}^{-1}$$R_{0}^{-1}$$R_{0}$
Figure 4: Illustration of the closed-neighbourhood of $1$ in the Cayley graph
construction for $(b,r)=(6,7)$ and $n=56$ in the proof of Theorem 3.1, with
the choice of $R_{0}$, $T_{0}$ and $T_{2}$ highlighted.

###### Proof of Theorem 3.1.

Let $n\in\mathbb{N}$ such that
$n=8\left(2+\big{\lfloor}\frac{r}{2}\big{\rfloor}+\big{\lfloor}\frac{b+2}{2}\big{\rfloor}-2\big{\lfloor}\frac{b+2}{6}\big{\rfloor}\right)$
and consider $\mathbb{Z}_{n}$, the additive group modulo $n$. By this choice
of $n$, the interval $\left(\frac{n}{8},\frac{n}{4}\right)$ has two disjoint
integer intervals $R_{0}$ and $T_{0}$ of sizes
$\big{\lfloor}\frac{r}{2}\big{\rfloor}$ and
$\big{\lfloor}\frac{b+2}{2}\big{\rfloor}-2\big{\lfloor}\frac{b+2}{6}\big{\rfloor}$
respectively. Choose these intervals such that $R_{0}<T_{0}$. Now,

$\big{\lfloor}\frac{b+2}{2}\big{\rfloor}-2\big{\lfloor}\frac{b+2}{6}\big{\rfloor}=\big{\lfloor}\frac{b+2}{6}\big{\rfloor}+\big{\lfloor}\frac{1}{2}\left(b+2-6\big{\lfloor}\frac{b+2}{2}\big{\rfloor}\right)\big{\rfloor}=\big{\lfloor}\frac{b+2}{6}\big{\rfloor}+\big{\lfloor}\frac{(b+2)\\!\mod
6}{2}\big{\rfloor}$

and therefore $T_{0}$ has at least $\big{\lfloor}\frac{b+2}{6}\big{\rfloor}$
integers. By our choice of $n$, we can choose $T_{0}$ such that it has a sub-
interval $T_{2}$ of size $\big{\lfloor}\frac{b+2}{6}\big{\rfloor}$ and
$\min(T_{2})\geq\frac{3n}{16}$.

Define the sets $R_{1}=R_{0}\ \dot{\cup}\ R_{0}^{-1}$ and $T_{1}=T_{0}\
\dot{\cup}\ T_{0}^{-1}$, which are inverse-closed and sum-free. Define
$B_{1}=T_{1}\ \dot{\cup}\ 2T_{2}\ \dot{\cup}\ 2T_{2}^{-1}$. Since $T_{2}$ is
an integer interval and $2T_{2}$ is the sum-set of $T_{2}$ with itself, then
$|2T_{2}|=2|T_{2}|-1$. Moreover, $|T_{2}|=|T_{2}^{-1}|$ and
$|T_{0}|=|T_{0}^{-1}|$. Therefore,

$|T_{1}|+|2T_{2}|+\left|2\left(T_{2}^{-1}\right)\right|=2|T_{0}|+4|T_{2}|-2=6\left\lfloor\frac{b+2}{6}\right\rfloor+2\left\lfloor\frac{(b+2)\\!\mod
6}{2}\right\rfloor-2$

and hence $|B_{1}|=b-\left(b\mod 2\right)$.

The sets $R_{1}$ and $B_{1}$ have even size, and we may need to add some
involutions to them to get the size equal to $r$ and $b$ respectively. Three
cases may arise:

  1. i.

Both $r$ and $b$ are even and therefore $|R_{1}|=r$ and $|B_{1}|=b$. In this
case let $\Gamma=\mathbb{Z}_{n}$, $R=R_{1}$ and $B=B_{1}$. In this case
$\lambda_{b,r}=1$.

  2. ii.

Either $r$ is odd or $b$ is odd, in which case we let $\Gamma=\mathbb{Z}_{n}$.
If $r$ is odd we define $R=R_{1}\cup\\{\frac{n}{2}\\}$ and $B=B_{1}$. Else if
$b$ is odd we define $R=R_{1}$ and $B=B_{1}\cup\\{\frac{n}{2}\\}$.
Consequently $R$ and $B$ are inverse-closed and have size $r$ and $b$
respectively. Moreover, $R$ is sum-free. In this case $\lambda_{b,r}=1$.

  3. iii.

Both $r$ and $b$ are odd, in which case we let
$\Gamma=\mathbb{Z}_{2}\times\mathbb{Z}_{n}$. Define $B=\left(\\{0\\}\times
B_{1}\right)\cup\\{(0,\frac{n}{2})\\}$ and $R=\left(\\{0\\}\times
R_{1}\right)\cup\\{(1,0)\\}$, noting that $(0,\frac{n}{2})$ and $(1,0)$ are
involutions in $\mathbb{Z}_{2}\times\mathbb{Z}_{n}$. Moreover, $R$ is sum-free
by choice of $R_{1}$ and by the properties of the direct product. In this case
$\lambda_{b,r}=2$.

Consider $H=\mathsf{Cay}\left(\Gamma;R\right)$ coloured monochromatically
using colour $2$. Since $R$ is sum-free, then $e_{2}^{H}[v]=r=\deg^{H}_{2}(v)$
for any $v$ in $\Gamma$.

Now consider $H=\mathsf{Cay}\left(\Gamma;B\right)$ coloured monochromatically
using colour $1$. For any $v$ in $\Gamma$, $\deg_{1}^{G}(v)=b$. Moreover,
there are at least $2\left\lfloor\frac{b+2}{6}\right\rfloor^{2}$ edges in the
open-neighbourhood of $v$, since the group is Abelian and therefore the
$\left\lfloor\frac{b+2}{6}\right\rfloor^{2}$ sums from $T_{2}$ to $2T_{2}$,
and from $T_{2}^{-1}$ to $2T_{2}^{-1}$, all contribute an edge to the open-
neighbourhood. Hence,

$e_{1}^{G}[v]\geq
b+2\left\lfloor\frac{b+2}{6}\right\rfloor^{2}>r=e_{2}^{H}[v]$

Finally observe that by construction, as a consequence of Lemma 3.2 and
properties of the direct product, $(R+B)\cap R=\emptyset$. By Proposition 2.3
(iii), $\mathsf{Cay}\left(\Gamma;R\cup B\right)$ is a $(b,r)$-flip graph and
(i) follows. Moreover by choice of $\Gamma$, we obtain the bound on $h(b,r)$
in (i) ∎

It is worth comparing this bound to the existing bound given in Theorem 1.2
from [4]. We begin by noting that the new bound is significantly better than
the existing bound. This is illustrated in Figure 5, for fixed $b$ and
$1<r-b<2\left\lfloor\frac{b}{6}\right\rfloor^{2}$.

Figure 5: Comparison of the bounds in $\triangle$ Theorem 1.2 and $\bullet$
Theorem 3.1 for $b=11$ and $b=25$ over the common range for $r$ between the
two bounds.

Observe, however, that the existing bound in Theorem 1.2 holds for a wider
range of values of $b$, suggesting that further work is to be done towards a
unified bound.

##  4 Bounding $q(k)$

In this section we shall consider the problem in [4] on establishing bounds on
$q(k)$. In particular we shall prove the following theorem.

######  Theorem 4.1.

Let $k\in\mathbb{N}$ such that $k>3$. Then,

$\min\left\\{1,\left\lceil\frac{k}{4}\right\rceil-1\right\\}\leq
q(k)<\begin{cases}\ \frac{k}{3}&\mbox{if $k\mod 3=0$}\\\
\left\lceil\frac{k}{2}\right\rceil&\mbox{otherwise}\end{cases}$

###  4.1 Upper bounds on $q(k)$

We begin by proving the upper bound in Theorem 4.1. The following ideas stem
from a communication by Caro [3].

######  Theorem 4.2.

Let $k\in\mathbb{N},k\geq 2$. Then $q(k)<\begin{cases}\ \frac{k}{3}&\mbox{if
$k\mod 3=0$}\\\ \left\lceil\frac{k}{2}\right\rceil&\mbox{otherwise}\\\
\end{cases}$.

###### Proof.

The cases $k=2$ and $k=3$ immediately follows from Theorems 1.1 and 1.3. Hence
consider $k\geq 4$. Let $G$ be an $(a_{1},\dots,a_{k})$-flip graph. Consider
the case when $k\mod 3=0$ and let $p=\frac{k}{3}$. Re-colour the edges of $G$
such that the $p$ colours $p(j-1)+1,\dots,pj$ are coloured $j$ for
$j\in\\{1,2,3\\}$. For $j\in\\{1,2,3\\}$, define
$b_{j}=\sum_{i=1}^{s}a_{(i-1)s+j}$. Note that $b_{1}<b_{2}<b_{3}$ by the
monotonicity of the $k$-flip sequence and the fact that each $b_{j}$ is a sum
of $s$ terms.

Applying a similar argument to the coloured closed-neighbourhood sizes, one
observes that $G$ is a $(b_{1},b_{2},b_{3})$-flip graph.

By Theorem 1.3, it follows that $b_{3}\leq 2(b_{1})^{2}$ and hence $a_{k}\leq
2k^{2}(a_{s})^{2}$. Therefore $a_{k}$ is bound in $a_{\frac{k}{3}}$ and hence
$q(k)<\frac{k}{3}$ when $k\mod 3=0$.

Otherwise, consider $t=\left\lceil\frac{k}{2}\right\rceil$. Let
$c_{1}=\sum_{i=1}^{t}a_{i}$ and $c_{2}=\sum_{i=1}^{k-t}a_{t+i}$. Two cases are
possible: either $2t=k$ or $2t-1=k$. In the case that $2t-1=k$, it need not
necessarily be that case that $c_{1}<c_{2}$. Indeed, suppose that $c_{1}\geq
c_{2}$. Then $ta_{t}\geq a_{k}$ and hence $a_{k}$ is bounded in
$a_{\left\lceil\frac{k}{2}\right\rceil}$.

Consider the cases when $2t=k$ or $2t-1=k$ but $c_{1}<c_{2}$. In both these
cases, by a similar argument to the case when $k\mod 3=0$, we have that $G$ is
a $(c_{1},c_{2})$-flip graph. By Theorem 1.1 it follows that
$c_{2}<\binom{c_{1}+1}{2}$ and hence $a_{k}$ is quadratically bound in
$a_{\left\lceil\frac{k}{2}\right\rceil}$. It follows that
$q(k)<\left\lceil\frac{k}{2}\right\rceil$. ∎

###  4.2 Lower bounds on $q(k)$

In this section we shall prove the lower bound in Theorem 4.1. We first note
this useful result on the existence of flipping intervals which are realised
by flip-graphs having a difference of 1 in the sequence of coloured closed-
neighbourhood sizes, which will be a critical step in our proof of the lower
bound.

######  Theorem 4.3 ([4]).

Let $q,b\in\mathbb{N}$ such that $q>1$, $b\geq 101$ and
$\left\lfloor\frac{1}{4}\big{(}b^{2}-10b^{\frac{3}{2}}\big{)}\right\rfloor\geq
q-1$. Then $[b,b+q-1]$ is a flipping interval realised by a $q$-flip graph $G$
with $e_{j}[v]-e_{j+1}[v]=1$ for all $1\leq j<q$ and $v\in V(G)$.

###### Proof.

Follows immediately from the construction in the proof of Theorem 5.2 and
Corollary 5.3 of [4]. ∎

We next show that, if $q$-flip graphs satisfying particular properties exist,
then $(a_{1},\dots,a_{k})$-flip graphs exist for $k>4q$, where $a_{k}$ can be
arbitrarily large whilst $a_{i}$ is constant for $1\leq i\leq q$.

######  Lemma 4.4.

Let $q,k\in\mathbb{N}$ such that $1<q<\frac{k}{4}$. Let
$D_{1},\dots,D_{q}\in\mathbb{N}$ such that $D_{q}(k-4q)>1+\xi
q(q-1)+5\binom{k-q}{2}$ where $\xi=\max\limits_{1\leq j\leq
q}\\{D_{j}-D_{j+1}\\}$.

If there exists a $(a_{1},\dots,a_{q})$-flip graph $F$ such that for every
$v\in V(F)$ and $1\leq j\leq q$, $e_{j}^{F}[v]=D_{j}$, then given any
$N\in\mathbb{N}$ there exists a $(a_{1},\dots,a_{k})$-flip graph for some
$a_{q+1},\dots,a_{k}\in\mathbb{N}$ where $a_{k}>N$.

###### Proof.

Let $\Gamma$ be a sufficiently large finite group such that $\Gamma$ has
$k-q-1$ disjoint and inverse-closed subsets $S_{j}$ where $|S_{j}|=k-q-j$ for
$1\leq j<k-q$, and such that $S=\bigcup\limits_{j=1}^{k-q-1}S_{j}$ is sum-free
in $\Gamma$.

Consider $K=\mathsf{Cay}\left(\Gamma;S\right)$ with an edge-colouring such
that the edges labelled in $S_{j}$ are coloured using $q+j$. Hence for any
$v\in\Gamma$, $\deg_{q+j}^{K}(v)=k-q-j$ and by the sum-free condition on $S$,
$e_{q+j}^{K}[v]=k-q-j$.

Now consider the coloured Cartesian product $F\ \square\ K$, which is $k-1$
coloured since $F$ is coloured using $1,\dots,q$ and $K$ is coloured using
$q+1,\dots,k-1$.

By Lemma 2.2, for a given colour $j$ the graph has colour-degree $a_{j}$
inherited from $F$ for $1\leq j\leq q$, and $a_{j}=k-j$ inherited from $K$
when $q<j<k$. Likewise, the number of edges coloured $j$ in a closed-
neighbourhood is $D_{j}$ inherited from $F$ for $1\leq j\leq q$ and
$D_{j}=k-j$ inherited from $K$ for $q<j<k$.

Finally, note that $F\ \square\ K$ is
$\mu=\binom{k-q}{2}+\sum\limits_{i=1}^{q}a_{i}$ regular. Let $t\in\mathbb{N}$
such that

$t\geq\dfrac{1+\mu+2\sum\limits_{i=1}^{k}D_{i}}{(k-q)\min\limits_{q<i<k}\\{D_{i}-D_{i+1}\\}}$

and let $H$ be a $\rho=(k-q)t+\binom{k-q}{2}$ regular bipartite graph. For
$1\leq j\leq k-q$, colour $t+j-1$ matchings of $H$ using $q+j$.

Let $G$ be the coloured strong product $H\boxtimes(F\ \square\ K)$. By Lemma
2.1, for $v\in V(G)$ and $1\leq j\leq k$, the edge-colouring in $G$ is such
that

$\deg_{j}(v)=\begin{cases}a_{j}&1\leq j\leq q\\\
a_{j}+(t+i-q-1)(1+\mu)&q<j\leq k\end{cases}$

and

$e_{j}[v]=\begin{cases}D_{j}(\rho+1)&1\leq j\leq q\\\
D_{j}(\rho+1)+(t+j-q-1)\left(1+\mu+2\sum\limits_{i=1}^{k}D_{i}\right)&q<j\leq
k\end{cases}$

We will show that $G$ as constructed and edge-coloured is a $k$-flip graph.
Observe that for $1\leq j\leq k$, $a_{j}<1+\mu$. Hence for $j=q$ we have that

$\deg_{q}(v)=a_{q}<1+\mu<a_{q+1}+t(1+\mu)=\deg_{q+1}(v)$

and for $j>q$ we have that $\deg_{j+1}(v)-\deg_{j}(v)=\mu>0$. Consequently the
colour-degree sequence in $G$ is strictly increasing.

Since for $1\leq j<q$ we have $D_{j}>D_{j+1}$ then in $G$ we have
$e_{j}[v]>e_{j+1}[v]$. Next note that $\rho+1=(k-q)t\kappa$ for some
$\kappa>1$. Hence $(D_{q}-D_{q+1})(\rho+1)>(D_{q}-D_{q+1})(k-q)t$. Therefore
to show that $e_{q}[v]>e_{q+1}[v]$ it suffices to show

$(D_{q}-D_{q+1})(k-q)>1+\mu+2\sum\limits_{i=1}^{k}D_{i}$

From the lower-bound on $D_{q}$ in the theorem statement we have that

$\displaystyle D_{q}(k-q)$ $\displaystyle>1+(3q)D_{q}+\xi
q(q-1)+5\binom{k-q}{2}$
$\displaystyle>1+\sum\limits_{i=1}^{q}a_{i}+(2q)D_{q}+\xi
q(q-1)+5\binom{k-q}{2}$ $\displaystyle\because a_{1}<\dots<a_{q}\leq D_{q}$
$\displaystyle=1+\mu+(2q)D_{q}+\xi q(q-1)+4\binom{k-q}{2}$
$\displaystyle\because\mu=\sum\limits_{i=1}^{q}a_{i}+\binom{k-q}{2}$
$\displaystyle\geq 1+\mu+2\sum_{i=1}^{q}D_{i}+4\binom{k-q}{2}$
$\displaystyle\because D_{q-i}\leq D_{q}+i\xi$
$\displaystyle=1+\mu+2\sum_{i=1}^{k}D_{i}+2\binom{k-q}{2}$
$\displaystyle\because\binom{k-q}{2}=\sum\limits_{i=q+1}^{k}D_{i}$
$\displaystyle=D_{q+1}(k-q)+1+\mu+2\sum_{i=1}^{k}D_{i}$ $\displaystyle\because
D_{q+1}=k-q-1$

as required and therefore the colours $q$ and $q+1$ flip in $G$.

Consider the final case when $q<j<k$. By the choice of $t$ and $\kappa>1$, we
have that

$(D_{j}-D_{j+1})(\rho+1)=(D_{j}-D_{j+1})(k-q)(t\kappa)>1+\mu+2\sum\limits_{i=1}^{k}D_{i}$

which we can re-arrange to get $e_{j}[v]>e_{j+1}[v]$. Hence the sequence of
closed-neighbourhood sizes is strictly decreasing as required.

It follows that $G$ is a flip-graph on $k$ colours, such that for any vertex
$v$, the difference between $\deg_{q}(v)$ and $\deg_{k}(v)$ grows in $t$ as
$t\to\infty$. ∎

We are finally in a position to prove the lower bound in Theorem 4.1.

######  Theorem 4.5.

Let $k\in\mathbb{N}$ such that $k>3$. Then for any $q\in\mathbb{N}$ such that
$q=1$ or $q<\frac{k}{4}$, there exists $a_{1},\dots,a_{q}\in\mathbb{N}$ such
that given any $N\in\mathbb{N}$ there exists a $(a_{1},\dots,a_{k})$-flip
graph for some $a_{q+1},\dots,a_{k}\in\mathbb{N}$ where $a_{k}>N$.

###### Proof.

The case $q=1$ follows immediately from Theorem 1.4. Hence consider the case
when $1<q<\frac{k}{4}$.

Let $b\in\mathbb{N}$ be sufficiently large such that
$b\geq\max\left\\{101,\dfrac{1+q(q-1)+5\binom{k-5}{2}}{k-4q}\right\\}$ and
$\left\lfloor\frac{1}{4}\big{(}b^{2}-10b^{\frac{3}{2}}\big{)}\right\rfloor\geq
q-1$. By Corollary 4.3 and the choice of $b$, there exists a $(b,\dots,b+q-1)$
flip-graph $F$ where for every vertex $v\in V(F)$ and $1\leq j<q$,
$\xi=\max\limits_{1\leq j\leq q}\\{e_{j}[v]-e_{j+1}[v]\\}=1$. Moreover,

$e_{q}[v](k-4q)\geq(b+q-1)(k-4q)>b(k-4q)\geq 1+\xi q(q-1)+5\binom{q-5}{2}$

and therefore the result follows as an immediate consequence of Lemma 4.4. ∎

##  5 Concluding remarks

In this paper we set out to answer two problems of [4] concerning bounds on
$h(b,r)$ and $q(k)$ for flip-graphs. Given $k>4$, since
$h(a_{1},\dots,a_{k})>a_{k}$, as a consequence of Theorem 4.5 we have that
there exists $k$-flip sequences were $a_{i}$ are fixed for $1\leq
i<\frac{k}{4}$, but $a_{k}\to\infty$. In particular one observes that
consequently $h(a_{1},\dots,a_{k})$ is not bounded above by a polynomial in
$a_{i}$ for $1\leq i<\frac{k}{4}$.

This contrasts the case for when $k=2$ and $k=3$, where $h(a_{1},a_{2})$ and
$h(a_{1},a_{2},a_{3})$ are polynomially bound in $a_{1}$, and in particular we
have proven that $h(a_{1},a_{2})$ is quadratically bound in $a_{1}$ whenever
$a_{1}<a_{1}+2\left\lfloor\frac{a_{1}+2}{6}\right\rfloor^{2}$. In light of
this, we pose the following problem.

######  Problem.

For $k\geq 4$, is there a smallest integer $p(k)$, $\frac{k}{4}\leq p(k)\leq
k$, such that $h(a_{1},\dots,a_{k})$ is polynomially bound in $a_{p(k)}$?

Finding large subsets of Abelian groups which are both sum-free and inverse-
closed are of interest with regards to expanding the range of admissible
values $a_{2}$ for fixed $a_{1}$ such that $h(a_{1},a_{2})$ is
$O(a_{1}+a_{2})$.

######  Problem.

Given a finite Abelian group $\Gamma$, what is size of the largest subset
which is both sum-free and inverse-closed?

## Acknowledgements

The author would like to thank Yair Caro for the re–colouring idea behind
Theorem 4.2, along with Josef Lauri and Christina Zarb for their valuable
input which helped improve the overall presentation of this paper.

## References

  * [1] M.A. Abdullah and M. Draief.  Global majority consensus by local majority polling on graphs of a given degree sequence.  Discrete Applied Mathematics, 180:1–10, 2015.
  * [2] N. Alon and D. J. Kleitman.  Sum-free subsets.  In A. Baker, B. Bollobás, and A.Editors Hajnal, editors, A Tribute to Paul Erdos, page 13–26. Cambridge University Press, 1990.
  * [3] Y. Caro.  personal communication, 2023.
  * [4] Y. Caro, J. Lauri, X Mifsud, R. Yuster, and C. Zarb.  Flip colouring of graphs.  arXiv preprint arXiv:2312.08777, 2023.
  * [5] Y. Caro and R. Yuster.  The effect of local majority on global majority in connected graphs.  Graphs and Combinatorics, 34(6):1469–1487, 2018.
  * [6] P.C. Fishburn, F.K. Hwang, and Hikyu Lee.  Do local majorities force a global majority?  Discrete Mathematics, 61(2):165–179, 1986.
  * [7] B. Green and I. Z. Ruzsa.  Sum-free sets in abelian groups.  Israel journal of mathematics, 147(1):157–188, 2005.
  * [8] T. Tao and V. Vu.  Sumfree sets in groups: a survey.  Journal of Combinatorics, 8, 03 2016.