$0<\varepsilon<\infty$. Since this is not an exact solution to HyQMOM-BGK, we
need to augment eq. 144 with an additional manufactured solution source term:

$\displaystyle{\underline{q}}_{,t}+{\underline{f}}\left({\underline{q}}\right)_{,x}=\frac{1}{\varepsilon}\,{\underline{S^{\text{cons}}}}\left({\underline{q}}\right)+{\underline{s_{q}}},\quad{\underline{\alpha}}_{,t}+{\underline{\underline{B}}}\left({\underline{\alpha}}\right)\,{\underline{\alpha}}_{,x}=\frac{1}{\varepsilon}\,{\underline{S^{\text{prim}}}}\left({\underline{\alpha}}\right)+{\underline{q}}^{-1}_{,{\underline{\alpha}}}\left({\underline{\alpha^{\text{ms}}}}\right){\underline{s_{q}}},$
(171)

where

$\begin{gathered}{\underline{s_{q}}}=\left[\pi^{3/2}\sin\bigl{(}2\pi(t-x)\bigr{)}\right]{\underline{v_{1}}}+\left[\pi^{1/2}\Bigl{(}2-\cos\bigl{(}2\pi(t-x)\bigr{)}\Bigr{)}\right]{\underline{v_{2}}},\\\
{\underline{v_{1}}}=\left(A_{1},\,A_{2},\,A_{3},\,A_{4},\,A_{7}\right),\quad{\underline{v_{2}}}=\left(0,\,0,\,0,\,A_{5},\,A_{6}\right).\end{gathered}$
(172)

with

$\begin{gathered}A_{1}=\frac{3+11\varepsilon}{4(1+\varepsilon)},\quad
A_{2}=\frac{1-33\varepsilon}{16(1+\varepsilon)},\quad
A_{3}=\frac{5(1+33\varepsilon)}{64(1+\varepsilon)},\quad
A_{4}=\frac{3-809\varepsilon}{256(1+\varepsilon)},\\\
A_{5}=\frac{-125}{128(1+2\varepsilon)^{2}},\quad
A_{6}=\frac{125(1+2\varepsilon-10\varepsilon^{2})}{512(1+2\varepsilon)^{3}},\\\
A_{7}=\frac{76+3620\varepsilon+521895\varepsilon^{2}+5285445\varepsilon^{3}+9544425\varepsilon^{4}+4794867\varepsilon^{5}}{1024(1+\varepsilon)(2+33\varepsilon(1+\varepsilon))^{2}}.\end{gathered}$
(173)

Convergence tables for the ${M_{\text{O}}}=4$ scheme are shown in table 4.
Importantly, we consider various values of the Knudsen number that span ten
orders of magnitude:
$\varepsilon=10^{4},\,10^{2},\,10^{0},\,10^{-2},\,10^{-4},\,\text{and}\,10^{-6}$,
and in each case, we achieve optimal convergence. These results confirm the
asymptotic-preserving (AP) property for small $\varepsilon>0$.

$N$ | $\varepsilon=10^{4}$ | $\log_{2}\frac{\text{e}_{N/2}}{\text{e}_{N}}$ | $\varepsilon=10^{2}$ | $\log_{2}\frac{\text{e}_{N/2}}{\text{e}_{N}}$ | $\varepsilon=10^{0}$ | $\log_{2}\frac{\text{e}_{N/2}}{\text{e}_{N}}$
---|---|---|---|---|---|---
10 | 1.181e-03 | – | 1.193e-03 | – | 1.426e-03 | –
20 | 5.809e-05 | $4.346$ | 5.897e-05 | $4.339$ | 6.321e-05 | $4.496$
40 | 3.541e-06 | $4.036$ | 3.515e-06 | $4.068$ | 3.655e-06 | $4.112$
80 | 2.212e-07 | $4.001$ | 2.622e-07 | $3.745$ | 2.601e-07 | $3.813$
160 | 1.376e-08 | $4.007$ | 1.622e-08 | $4.015$ | 1.529e-08 | $4.088$
320 | 8.592e-10 | $4.001$ | 9.983e-10 | $4.022$ | 8.986e-10 | $4.089$
$N$ | $\varepsilon=10^{-2}$ | $\log_{2}\frac{\text{e}_{N/2}}{\text{e}_{N}}$ | $\varepsilon=10^{-4}$ | $\log_{2}\frac{\text{e}_{N/2}}{\text{e}_{N}}$ | $\varepsilon=10^{-6}$ | $\log_{2}\frac{\text{e}_{N/2}}{\text{e}_{N}}$
10 | 1.327e-03 | – | 1.644e-03 | – | 1.660e-03 | –
20 | 6.608e-05 | $4.328$ | 6.826e-05 | $4.590$ | 6.861e-05 | $4.597$
40 | 4.040e-06 | $4.032$ | 4.222e-06 | $4.015$ | 4.148e-06 | $4.048$
80 | 2.537e-07 | $3.993$ | 2.575e-07 | $4.035$ | 2.557e-07 | $4.020$
160 | 1.572e-08 | $4.012$ | 1.622e-08 | $3.989$ | 1.601e-08 | $3.998$
320 | 9.929e-10 | $3.985$ | 1.006e-09 | $4.011$ | 1.008e-09 | $3.989$
Table 4: (§8.1: HyQMOM-BGK manufactured solution problem) Relative $L^{2}$
errors for a manufactured solution example for the one-dimensional HyQMOM
equations with a BGK collision operator. The errors are computed for various
values of the Knudsen number:
$\varepsilon=10^{4},\,10^{2},\,10^{0},\,10^{-2},\,10^{-4},\,\text{and}\,10^{-6}$.
In each case, we use the fourth order method: ${M_{\text{O}}}=4$.

###  8.2 BGK shock tube problem

Consider the Riemann problem for (144)–(145) with the following initial data
at $t=0$:

$\bigl{(}\rho,u,p,h,k\bigr{)}(t=0,x)=\begin{cases}\bigl{(}1.0,\,0.0,\,1.0,\,0.0,\,2.0\bigr{)}&\quad
x<0,\\\ \bigl{(}0.125,\,0.0,\,0.1,\,0.0,\,0.16\,\bigr{)}&\quad
x>0,\end{cases}$ (174)

on $x\in[-1,1]$ with extrapolation boundary conditions. This is the standard
Sod shock tube problem article:Sod78 , which is ubiquitous in shock-capturing
literature, and is also often found as a standard test for Boltzmann-BGK
solvers (e.g., see article:Ben08 ).

We consider three different values of the Knudsen number: (a)
$\varepsilon=10^{-2}$, (b) $\varepsilon=10^{-3}$, and (c)
$\varepsilon=10^{-4}$. In each case we run the ${M_{\text{O}}}=4$ scheme with
$M_{\text{elem}}=200$; we also compare in each case the HyQMOM-BGK solution to
the exact solution for the compressible Euler equations eq. 147 (e.g., see
Chapter 14 of LeVeque book:Le02  for a derivation). We used the following
values of ${\mathcal{A}}_{0}$ in formula eq. 129: (a) ${\mathcal{A}}_{0}=50$
for $\varepsilon=10^{-2}$, (b) ${\mathcal{A}}_{0}=50$ for
$\varepsilon=10^{-3}$, and (c) ${\mathcal{A}}_{0}=350$ for
$\varepsilon=10^{-4}$.

Figure 7 displays the $\varepsilon=10^{-2}$ numerical simulation at $t=0.28$
showing the (a) density: $\rho(t,x)$, (b) macroscopic velocity: $u(t,x)$, (c)
pressure: $p(t,x)$, and (d) heat flux: $h(t,x)$. At this Knudsen number, the
solution is still significantly different than the compressible Euler
solution, which is also shown in each panel. The results are consistent with
fully kinetic solutions article:Ben08 .

Figure 8 displays the $\varepsilon=10^{-3}$ numerical simulation at $t=0.28$
showing the (a) density: $\rho(t,x)$, (b) macroscopic velocity: $u(t,x)$, (c)
pressure: $p(t,x)$, and (d) heat flux: $h(t,x)$. At this Knudsen number, the
solution looks closer to the compressible Euler solution, which is also shown
in each panel. The results are again consistent with fully kinetic solutions
article:Ben08 .

Figure 9 displays the $\varepsilon=10^{-4}$ numerical simulation at $t=0.28$
showing the (a) density: $\rho(t,x)$, (b) macroscopic velocity: $u(t,x)$, (c)
pressure: $p(t,x)$, and (d) heat flux: $h(t,x)$. At this Knudsen number, the
solution is very close to the compressible Euler solution, which is also shown
in each panel. The results are again consistent with fully kinetic solutions
article:Ben08 .

(a) | (b)
---|---
(c) | (d)
Figure 7: (§8.2: BGK shock tube problem with $\varepsilon=10^{-2}$) Numerical solution of shock tube problem on $x\in[-1,1]$ with initial conditions given by (174). Shown are the results from a simulation run with the proposed ${M_{\text{O}}}=4$ scheme with 200 elements (shown as blue dots) and the exact solution of the compressible Euler equations with the same initial conditions (shown as a solid red line). For the ${M_{\text{O}}}=4$ scheme, we are plotting four points-per-element in order to show the intra-element solution structure. The panels show the primitive variables: (a) density: $\rho(t,x)$, (b) macroscopic velocity: $u(t,x)$, (c) pressure: $p(t,x)$, and (d) heat flux: $h(t,x)$.  (a) | (b)
---|---
(c) | (d)
Figure 8: (§8.2: BGK shock tube problem with $\varepsilon=10^{-3}$) Numerical solution of shock tube problem on $x\in[-1,1]$ with initial conditions given by (174). Shown are the results from a simulation run with the proposed ${M_{\text{O}}}=4$ scheme with 200 elements (shown as blue dots) and the exact solution of the compressible Euler equations with the same initial conditions (shown as a solid red line). For the ${M_{\text{O}}}=4$ scheme, we are plotting four points per element in order to show the intra-element solution structure. The panels show the primitive variables: (a) density: $\rho(t,x)$, (b) macroscopic velocity: $u(t,x)$, (c) pressure: $p(t,x)$, and (d) heat flux: $h(t,x)$.  (a) | (b)
---|---
(c) | (d)
Figure 9: (§8.2: BGK shock tube problem with $\varepsilon=10^{-4}$) Numerical
solution of shock tube problem on $x\in[-1,1]$ with initial conditions given
by (174). Shown are the results from a simulation run with the proposed
${M_{\text{O}}}=4$ scheme with 200 elements (shown as blue dots) and the exact
solution of the compressible Euler equations with the same initial conditions
(shown as a solid red line). For the ${M_{\text{O}}}=4$ scheme, we are
plotting four points-per-element in order to show the intra-element solution
structure. The panels show the primitive variables: (a) density: $\rho(t,x)$,
(b) macroscopic velocity: $u(t,x)$, (c) pressure: $p(t,x)$, and (d) heat flux:
$h(t,x)$.

##  9 Conclusions

In this work, we considered a particular moment closure called HyQMOM (the
hyperbolic quadrature-based method of moments), which was originally
introduced by Fox, Laurent, Vie article:FoxLauVie2018  and further studied by
Johnson thesis:Johnson2017  and Wiersma thesis:Wiersma2019 . Quadrature-based
method of moments (QMOM), including the HyQMOM variant, are a promising class
of approximation techniques for reducing kinetic equations to fluid equations
that are valid beyond thermodynamic equilibrium. In particular, the goal of
the present work was to develop high-order discontinuous Galerkin schemes and
corresponding limiters that control both unphysical oscillations and eliminate
positivity violations.

The numerical scheme developed is based on the Lax-Wendroff discontinuous
Galerkin scheme introduced by Qiu, Dumbser, and Shu article:Qiu05 , with the
predictor-corrector interpretation developed by Gassner et al.
article:GasDumHinMun2011 , and further refinements developed by Felton et al.
article:REU2018 . The resulting numerical method is performed in two phases at
each time step.

Prediction step.

The equation and numerical solution are written in the primitive variables in
this phase. In the space-time DG approximation, which is applied to each
element, integration-by-parts is only performed on the time variable. The
result is a system of local nonlinear equations on each element. These
equations are solved using a Picard iteration, which provides a sufficiently
accurate solution after ${M_{\text{O}}}-1$ iterations, where ${M_{\text{O}}}$
is the order of accuracy of the method.

Correction step.

The correction is a straightforward explicit update based on the time-integral
of the evolution equation in conservation form, where the space-time
prediction replaces all instances of the exact solution.

Several limiters were applied to the scheme to guarantee positivity and
achieve solutions without unphysical oscillations.

Limiter I: Prediction step positivity limiter.

This limiter is completely local and minimally damps high-order corrections to
the primitive variables to get pointwise positivity of the predicted density,
pressure, and modified kurtosis on all space-time quadrature points (Gauss-
Legendre + edges). The limiter is applied once after each Picard iteration,
meaning it is applied a total of ${M_{\text{O}}}-1$ times per time step.

Limiter II: Correction step positivity limiter on cell average.

This limiter is applied once per time step and blends high-order numerical
fluxes with positivity preserving low-order fluxes in such a way as to
preserve the positivity of the corrected element averages of density,
pressure, and modified kurtosis. This limiter is applied once per time step.

Limiter III: Correction step positivity limiter on quadrature points.

This limiter is similar to Limiter I and involves minimally damping the high-
order corrections to preserve the positivity of the corrected density,
pressure, and modified kurtosis, on all spatial quadrature points (Gauss-
Legendre + edges). This limiter is applied once per time step at the end of
the step.

Limiter IV: Oscillation Limiter.

This limiter damps the solution if the primitive solution variables on the
current element significantly exceed the primitive solution variables on
neighboring elements. This limiter is applied once per time step at the end of
the time step.

In the collisionless regime, the proposed high-order method and the limiting
strategy were tested on both smooth and Riemann problems. The smooth solution
was used to perform convergence tests that demonstrated the expected orders of
accuracy. The Riemann data tests clearly showed that the limiters were
successful in damping unphysical oscillations without adversely diffusing the
solution and preserving the positivity of the relevant variables.

Once the collisionless method is fully developed, we propose a version of the
scheme for HyQMOM with a BGK collision operator. We carefully show how to
handle the collision operator in both the prediction and collision steps to
achieve an asymptotic-preserving (AP) property in the high-collision limit.
Several numerical examples are provided to validate the scheme both for smooth
solutions and Riemann initial data. The asymptotic-preserving property is
validated for smooth solutions and Riemann initial data.

Future work will focus on extending this work to higher dimensions; perhaps
using the conditional moment strategy of article:FoxLauVie2018 ;
article:PaDeFo2019 , or some other higher-dimensional extension.

##  Appendix A Appendix

######  Lemma 2 (Hermite interpolation)

Consider the Hermite interpolation problem of interpolating the function
$f(v)=v^{2N}$ with a polynomial of degree $2N-1$:

$P_{2N-1}(v)=a_{0}+a_{1}v+a_{2}v^{2}+\cdots+a_{2N-1}v^{2N-1}=\sum_{{j}=0}^{2N-1}a_{{j}}v^{j},$
(175)

with interpolating conditions for ${\ell}=1,2,\ldots,N$:

$P_{2N-1}(\mu_{\ell})=f(\mu_{\ell})=\mu_{\ell}^{2N}\qquad\text{and}\qquad
P^{\prime}_{2N-1}(\mu_{\ell})=f^{\prime}(\mu_{\ell})=2N\mu_{\ell}^{2N-1},$
(176)

where

$\mu_{1}<\mu_{2}<\cdots<\mu_{N-1}<\mu_{N}.$ (177)

Applying these conditions yields the following formula for the polynomial
coefficients:

$\begin{bmatrix}[1.5]a_{0}\\\ \vdots\\\ a_{N-1}\\\ a_{N}\\\ \vdots\\\
a_{2N-1}\end{bmatrix}=\begin{bmatrix}[1.5]1&\mu_{1}&\mu_{1}^{2}&\mu_{1}^{3}&\cdots&\mu_{1}^{2N-1}\\\
\vdots&\vdots&\vdots&&&\vdots\\\
1&\mu_{N}&\mu_{N}^{2}&\mu_{N}^{3}&\cdots&\mu_{N}^{2N-1}\\\
0&1&2\mu_{1}&3\mu_{1}^{2}&\cdots&(2N-1)\mu_{1}^{2N-2}\\\
\vdots&\vdots&\vdots&\vdots&&\vdots\\\
0&1&2\mu_{N}&3\mu_{N}^{2}&\cdots&(2N-1)\mu_{N}^{2N-2}\end{bmatrix}^{-1}\begin{bmatrix}[1.5]\mu_{1}^{2N}\\\
\vdots\\\ \mu_{N}^{2N}\\\ 2N\mu_{1}^{2N-1}\\\ \vdots\\\
2N\mu_{N}^{2N-1}\end{bmatrix}.$ (178)

###### Proof

The claimed result follows directly from applying the interpolating conditions
to the polynomial $P_{2N-1}(v)$. $\blacksquare$

######  Lemma 3 (Moment gradient operator I)

Let
$f\left({\underline{\omega}},{\underline{\mu}}\right):\mathbb{R}^{N}\times\mathbb{R}^{N}\mapsto\mathbb{R}$
be a continuously differentiable function, where
${\underline{\omega}},{\underline{\mu}}\in\mathbb{R}^{N}$ satisfy the moment
condition (22). The gradient of $f$ with respect to the moments,
${\underline{{\mathsf{M}}}}=\left({\mathsf{M}}_{0},{\mathsf{M}}_{1},\ldots,{\mathsf{M}}_{2N-1}\right)$,
is given by

$\nabla_{{\underline{{\mathsf{M}}}}}f\left({\underline{\omega}},{\underline{\mu}}\right)={\underline{\underline{B}}}^{-1}\nabla_{\left({\underline{\omega}},{\underline{\mu}}\right)}f\left({\underline{\omega}},{\underline{\mu}}\right),$
(179)

where

$\displaystyle\nabla_{{\underline{{\mathsf{M}}}}}:=$
$\displaystyle\left(\frac{\partial}{\partial{\mathsf{M}}_{0}},\,\frac{\partial}{\partial{\mathsf{M}}_{1}},\ldots,\frac{\partial}{\partial{\mathsf{M}}_{2N-1}}\right),$
(180)
$\displaystyle\nabla_{\left({\underline{\omega}},{\underline{\mu}}\right)}:=$
$\displaystyle\left(\frac{\partial}{\partial\omega_{1}},\ldots,\frac{\partial}{\partial\omega_{N}},\frac{\partial}{\partial\mu_{1}},\ldots,\frac{\partial}{\partial\mu_{N}}\right),$
(181)
$\displaystyle{\underline{\underline{B}}}:=\frac{\partial{\underline{{\mathsf{M}}}}}{\partial\left({\underline{\omega}},{\underline{\mu}}\right)}=$
$\displaystyle\begin{bmatrix}[1.5]1&\mu_{1}&\mu_{1}^{2}&\cdots&\mu_{1}^{2N-1}\\\
\vdots&\vdots&\vdots&&\vdots\\\ 1&\mu_{N}&\mu_{N}^{2}&\cdots&\mu_{N}^{2N-1}\\\
0&\omega_{1}&2\omega_{1}\mu_{1}&\cdots&(2N-1)\omega_{1}\mu_{1}^{2N-2}\\\
\vdots&\vdots&\vdots&&\vdots\\\
0&\omega_{N}&2\omega_{N}\mu_{N}&\cdots&(2N-1)\omega_{N}\mu_{N}^{2N-2}\end{bmatrix}.$
(182)

###### Proof

The results follows directly from the chain rule applied to the moment
condition: (22). $\blacksquare$

######  Lemma 4 (Moment gradient operator II)

The moment gradient as defined by (179)–(182) applied to the function
$f\left({\underline{\omega}},{\underline{\mu}}\right)=\mu_{\ell}$ for some
${\ell}=1,2,\ldots,N$ is the following vector:

$\mathbb{R}^{2N}\ni{\underline{b}}:=\Bigl{[}b_{0},\,b_{1},\,\ldots,b_{2N-1}\Bigr{]}^{T}=\nabla_{{\underline{{\mathsf{M}}}}}\,\mu_{\ell}={\underline{\underline{B}}}^{-1}\,\nabla_{\left({\underline{\omega}},{\underline{\mu}}\right)}\,\mu_{\ell}={\underline{\underline{B}}}^{-1}\,{\underline{e_{N+{\ell}}}},$
(183)

where ${\underline{e_{N+{\ell}}}}\in\mathbb{R}^{2N}$ is a vector with a value
of one in component $N+{\ell}$ and a value of zero in all other components.

Furthermore, ${\underline{b}}$ as defined above can be interpreted as the
vector of coefficients of the following polynomial:

$Q_{2N-1}(v):=b_{0}+b_{1}v+b_{2}v^{2}+\cdots+b_{2N-1}v^{2N-1}=\sum_{j=0}^{2N-1}b_{{j}}v^{j},$
(184)

which satisfies all of the following conditions:

$Q_{2N-1}\left(\mu_{m}\right)=0\qquad\text{and}\qquad
Q_{2N-1}^{\prime}\left(\mu_{m}\right)=\frac{1}{\omega_{\ell}}\,\delta^{{\ell}}_{m}\qquad\text{for}\qquad
m=1,2,\ldots,N.$ (185)

The polynomial $Q_{2N-1}$ can be explicitly written as follows:

$Q_{2N-1}(v)=\frac{\left(v-\mu_{\ell}\right)}{\omega_{\ell}}\left[{\displaystyle\prod_{\begin{subarray}{c}j=1\\\
j\neq{\ell}\end{subarray}}^{N}\left(v-\mu_{j}\right)^{2}}\middle/{\displaystyle\prod_{\begin{subarray}{c}j=1\\\
j\neq{\ell}\end{subarray}}^{N}\left(\mu_{\ell}-\mu_{j}\right)^{2}}\right].$
(186)

Finally, the dot product between the vector
${\underline{b}}\in\mathbb{R}^{2N}$ defined by (183) and the following vector:

${\underline{{\mathcal{R}}}}(s):=\Bigl{[}1,\,s,\,s^{2},\,\ldots,\,s^{2N-1}\Bigr{]}^{T},\qquad
s\in\mathbb{R},$ (187)

can be written as

${\underline{b}}\cdot{\underline{{\mathcal{R}}}}(s)=Q_{2N-1}(s)=\frac{\left(s-\mu_{\ell}\right)}{\omega_{\ell}}\left[{\displaystyle\prod_{\begin{subarray}{c}j=1\\\
j\neq{\ell}\end{subarray}}^{N}\left(s-\mu_{j}\right)^{2}}\middle/{\displaystyle\prod_{\begin{subarray}{c}j=1\\\
j\neq{\ell}\end{subarray}}^{N}\left(\mu_{\ell}-\mu_{j}\right)^{2}}\right].$
(188)

###### Proof

Equation (183) follows directly from definitions (179)–(182). Polynomial (184)
with Hermite interpolation conditions (185) follows from an argument similar
to the one provided in Lemma (2). Equation (186) follows from invoking the
Lagrange form of the interpolating polynomial that satisfies conditions (185).

Finally, dot product (188) follows from the simple observation that

$\displaystyle
Q_{2N-1}(sv)=\sum_{{j}=0}^{2N-1}b_{{j}}s^{j}v^{j}=b_{0}+\left(b_{1}s\right)v+\cdots+\left(b_{2N-1}s^{2N-1}\right)v^{2N-1}$
$\displaystyle\Longrightarrow\quad$ $\displaystyle
Q_{2N-1}(s)=\sum_{{j}=0}^{2N-1}b_{{j}}{\mathcal{R}}_{j}(s)={\underline{b}}\cdot{\underline{{\mathcal{R}}}}(s),$

which when combined with (186) gives the desired result. $\blacksquare$

######  Theorem A.1 (Weak hyperbolicity and linear degeneracy of QMOM)

The classical quadrature-based moment (QMOM) closure for a fixed
$N\in{\mathbb{N}}_{\geq 1}$, denoted by eq. 21, leads to a system of partial
differential equations that has the following quasilinear form:

${\underline{q}}_{,t}+{\underline{\underline{A}}}\left({\underline{q}}\right)\,{\underline{q}}_{,x},\qquad\text{where}\quad{\underline{q}}=\begin{bmatrix}{\mathsf{M}}_{0},\,{\mathsf{M}}_{1},\,\cdots,\,{\mathsf{M}}_{2N-2},\,{\mathsf{M}}_{2N-1}\end{bmatrix},$
(189)

where the flux Jacobian matrix is given by

${\underline{\underline{A}}}\left({\underline{q}}\right)=\begin{bmatrix}[1.5]0&1&&&\\\
&0&1&&\\\ &&\ddots&\ddots&\\\ &&&0&1\\\
\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}_{0}}&\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}_{1}}&\cdots&\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}^{\star}_{2N-2}}&\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}_{2N-1}}\end{bmatrix},$
(190)

where ${\mathsf{M}}^{\star}_{2N}$ is given by (22). System (189) and (190) is
weakly hyperbolic for any integer $N\geq 1$ with the following properties:

  1. 1.

The eigenvalues of (190) are $\lambda_{\ell}=\mu_{\ell}$ for
${\ell}=1,2,3,\ldots,N$, where $\mu_{\ell}$ are the abscissas in (21);

  2. 2.

Every eigenvalue has algebraic multiplicity exactly two;

  3. 3.

Every eigenvalue has geometric multiplicity exactly one; and

  4. 4.

Every wave in the system is linearly degenerate:
$\frac{\partial\lambda_{\ell}}{\partial{\underline{q}}}\cdot{\underline{{\mathcal{R}}^{\ell}}}=0$
for ${\ell}=1,2,3,\ldots,N$, where
$\left(\lambda_{\ell},{\underline{{\mathcal{R}}^{\ell}}}\right)$ is an
eigenvalue-eigenvector pair of flux Jacobian (190).

###### Proof

The key to understanding the eigenvalues of flux Jacobian (190) is to
understand the last row. To this end, consider:

${\mathsf{M}}^{\star}_{2N}=\sum_{{j}=1}^{N}\omega_{j}\mu_{j}^{2N}\quad\Longrightarrow\quad\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}_{\ell}}=\sum_{{j}=1}^{N}\left[\mu_{j}^{2N}\frac{\partial\omega_{j}}{\partial{\mathsf{M}}_{\ell}}+2N\omega_{j}\mu_{j}^{2N-1}\frac{\partial\mu_{j}}{\partial{\mathsf{M}}_{\ell}}\right].$
(191)

To make sense of this we need to obtain expressions for the partial
derivatives of the quadrature weights and abscissas with respect to the
moments. To this end, we compute the related quantities:

$\displaystyle{\mathsf{M}}_{s}=\sum_{{j}=1}^{N}\omega_{j}\mu_{j}^{s}\quad\Longrightarrow\quad\frac{\partial{\mathsf{M}}_{s}}{\partial{\mathsf{M}}_{\ell}}=\sum_{{j}=1}^{N}\left[\mu_{j}^{s}\frac{\partial\omega_{j}}{\partial{\mathsf{M}}_{\ell}}+s\omega_{j}\mu_{j}^{s-1}\frac{\partial\mu_{j}}{\partial{\mathsf{M}}_{\ell}}\right]=\delta^{s}_{\ell},$
(192)

where $s,\ell=0,1,\ldots,2N-1$ and $\delta^{s}_{\ell}$ is the Kronecker delta,
which arises due to the fact that ${\mathsf{M}}_{\ell}$ and ${\mathsf{M}}_{s}$
are independent variables if $s\neq\ell$. The expression in (192) can be
written in matrix form to obtain the following result:

$\displaystyle\begin{bmatrix}[1.5]\frac{\partial\omega_{1}}{\partial{\mathsf{M}}_{0}}&\cdots&\frac{\partial\omega_{1}}{\partial{\mathsf{M}}_{2N-1}}\\\
\vdots&&\vdots\\\
\frac{\partial\omega_{N}}{\partial{\mathsf{M}}_{0}}&\cdots&\frac{\partial\omega_{N}}{\partial{\mathsf{M}}_{2N-1}}\\\
\omega_{1}\frac{\partial\mu_{1}}{\partial{\mathsf{M}}_{0}}&\cdots&\omega_{1}\frac{\partial\mu_{1}}{\partial{\mathsf{M}}_{2N-1}}\\\
\vdots&&\vdots\\\
\omega_{N}\frac{\partial\mu_{N}}{\partial{\mathsf{M}}_{0}}&\cdots&\omega_{N}\frac{\partial\mu_{N}}{\partial{\mathsf{M}}_{2N-1}}\end{bmatrix}^{T}=\begin{bmatrix}[1.5]1&\mu_{1}&\mu_{1}^{2}&\cdots&\mu_{1}^{2N-1}\\\
\vdots&\vdots&\vdots&&\vdots\\\ 1&\mu_{N}&\mu_{N}^{2}&\cdots&\mu_{N}^{2N-1}\\\
0&1&2\mu_{1}&\cdots&(2N-1)\mu_{1}^{2N-2}\\\ \vdots&\vdots&\vdots&&\vdots\\\
0&1&2\mu_{N}&\cdots&(2N-1)\mu_{N}^{2N-2}\end{bmatrix}^{-1}.$ (193)

Using this result in (191) produces expressions for the last row of flux
Jacobian (190):

$\displaystyle\begin{bmatrix}[1.5]\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}_{0}}\\\
\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}_{1}}\\\
\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}_{2}}\\\
\vdots\\\
\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}_{2N-2}}\\\
\frac{\partial{\mathsf{M}}^{\star}_{2N}}{\partial{\mathsf{M}}_{2N-1}}\end{bmatrix}=\begin{bmatrix}[1.5]1&\mu_{1}&\cdots&\mu_{1}^{2N-1}\\\
\vdots&\vdots&&\vdots\\\ 1&\mu_{N}&\cdots&\mu_{N}^{2N-1}\\\
0&1&\cdots&(2N-1)\mu_{1}^{2N-2}\\\ \vdots&\vdots&&\vdots\\\
0&1&\cdots&(2N-1)\mu_{N}^{2N-2}\end{bmatrix}^{-1}\begin{bmatrix}[1.5]\mu_{1}^{2N}\\\
\vdots\\\ \mu_{N}^{2N}\\\ 2N\mu_{1}^{2N-1}\\\ \vdots\\\
2N\mu_{N}^{2N-1}\end{bmatrix}=\begin{bmatrix}[1.5]a_{0}\\\ \vdots\\\
a_{N-1}\\\ a_{N}\\\ \vdots\\\ a_{2N-1}\end{bmatrix},$ (194)

where the last equality follows from Lemma 2 and $a_{j}$ for
$j=0,1,\ldots,2N-1$ are the coefficients of the Hermite interpolating
polynomial defined through (175) and (176).

Next we attempt to directly compute the eigenvalues of the flux Jacobian:

$\left|{\underline{\underline{A}}}-v{\underline{\underline{\mathbb{I}}}}\right|=\begin{vmatrix}[1.5]-v&\quad
1\\\ &\quad\ddots&\quad\ddots\\\ &&-v&1\\\ a_{0}&\quad\cdots&\quad
a_{2N-2}&\quad\left(a_{2N-1}-v\right)\end{vmatrix}=v^{2N}-\sum_{{j}=0}^{2N-1}a_{j}v^{{j}}.$
(195)

Using a classical result from Hermite polynomial interpolation, we can write
the right-most term in the above expression as follows (e.g., see Theorem 6.4
on page 190 of Süli and Mayer book:suli2003 ):

$\left|{\underline{\underline{A}}}-v{\underline{\underline{\mathbb{I}}}}\right|=\left(v-\mu_{1}\right)^{2}\left(v-\mu_{2}\right)^{2}\cdots\left(v-\mu_{N}\right)^{2}.$
(196)

This proves the first two claims of the theorem: (1) the eigenvalues are the
quadrature abscissas, and (2) each eigenvalue has algebraic multiplicity
exactly two.

Next we look at the eigenvectors. For example, the ${\ell}^{\text{th}}$
eigenvector for each ${\ell}=1,2,\ldots,N$ satisfies the relationship:

$\left({\underline{\underline{A}}}-\mu_{\ell}\,{\underline{\underline{\mathbb{I}}}}\right){\underline{{\mathcal{R}}^{\ell}}}={\underline{0}}.$
(197)

By inspection, we see that
${\underline{{\mathcal{R}}^{\ell}}}\not\equiv{\underline{0}}$ if and only if
the first component of ${\underline{{\mathcal{R}}^{\ell}}}$ is not zero.
Without loss of generality the first component is taken to be unity, and then
by inspection we note that the only eigenvector associated to eigenvalue
$v=\mu_{\ell}$ must be

${\underline{{\mathcal{R}}^{\ell}}}=\left(1,\,\mu_{\ell},\,\mu_{\ell}^{2},\,\ldots,\,\mu_{\ell}^{2N-1}\right)^{T}.$
(198)

This proves the third claim of the theorem: (3) each eigenvalue has geometric
multiplicity exactly one. Since the geometric multiplicity for each eigenvalue
is strictly less than the algebraic multiplicity, system (189) and (190) is
weakly hyperbolic for any integer $N\geq 1$.

The final claim in the theorem is that each wave is linearly degenerate.
Proving this requires us to investigate the following dot product

$\frac{\partial\mu_{\ell}}{\partial{\underline{q}}}\cdot{\underline{{\mathcal{R}}^{\ell}}}.$
(199)

Invoking Lemmas (3) and (4) shows that for every ${\ell}=1,2,\ldots,N$:

$\frac{\partial\mu_{\ell}}{\partial{\underline{q}}}\cdot{\underline{{\mathcal{R}}^{\ell}}}=\lim_{s\rightarrow\mu_{\ell}}\left\\{\frac{\left(s-\mu_{\ell}\right)}{\omega_{\ell}}\left[{\displaystyle\prod_{\begin{subarray}{c}j=1\\\
j\neq{\ell}\end{subarray}}^{N}\left(s-\mu_{j}\right)^{2}}\middle/{\displaystyle\prod_{\begin{subarray}{c}j=1\\\
j\neq{\ell}\end{subarray}}^{N}\left(\mu_{\ell}-\mu_{j}\right)^{2}}\right]\right\\}=0,$
(200)

which proves that every wave for ${\ell}=1,2,\ldots,N$ is linearly degenerate.
$\blacksquare$

######  Lemma 5 (Convexity property)

Let
${\mathcal{C}}_{\alpha}\left({\underline{Q}}\right):\mathbb{R}^{5}\mapsto\mathbb{R}$
be a convex function. Then for all $a,b\in\mathbb{R}$ such that

$a\geq 0,\quad b\geq 0,\quad 1-a-b\geq 0,$ (201)

the following inequality holds:

${\mathcal{C}}_{\alpha}\Bigl{(}(1-a-b){\underline{P}}+a{\underline{Q}}+b{\underline{R}}\Bigr{)}\leq(1-a-b){\mathcal{C}}_{\alpha}\Bigl{(}{\underline{P}}\Bigr{)}+a{\mathcal{C}}_{\alpha}\Bigl{(}{\underline{Q}}\Bigr{)}+b{\mathcal{C}}_{\alpha}\Bigl{(}{\underline{R}}\Bigr{)}\quad\forall{\underline{P}},{\underline{Q}},{\underline{R}}\in\mathbb{R}^{5}.$
(202)

###### Proof

By definition, the function ${\mathcal{C}}_{\alpha}$ is convex if and only if
the following is true for all $\theta\in[0,1]$:

${\mathcal{C}}_{\alpha}\Bigl{(}\bigl{(}1-\theta\bigr{)}{\underline{P}}+\theta{\underline{Q}}\Bigr{)}\leq\bigl{(}1-\theta\bigr{)}\,{\mathcal{C}}_{\alpha}\Bigl{(}{\underline{P}}\Bigr{)}+\theta\,{\mathcal{C}}_{\alpha}\Bigl{(}{\underline{Q}}\Bigr{)}\quad\forall{\underline{P}},{\underline{Q}}\in\mathbb{R}^{5}.$
(203)

Consider the convex function applied to a sum of three vectors of the
following form:

${\mathcal{C}}_{\alpha}\Bigl{(}(1-a-b){\underline{P}}+a{\underline{Q}}+b{\underline{R}}\Bigr{)}\quad\text{where}\quad
a,b,(1-a-b)\geq 0.$ (204)

We can temporarily define the following vector:

${\underline{S}}:=\biggl{(}\frac{a}{a+b}\biggr{)}\,{\underline{Q}}+\biggl{(}\frac{b}{a+b}\biggr{)}\,{\underline{R}}\quad\Longrightarrow\quad
a{\underline{Q}}+b{\underline{R}}=(a+b){\underline{S}},$ (205)

such that

${\mathcal{C}}_{\alpha}\Bigl{(}(1-a-b){\underline{P}}+a{\underline{Q}}+b{\underline{R}}\Bigr{)}={\mathcal{C}}_{\alpha}\Bigl{(}(1-a-b){\underline{P}}+(a+b){\underline{S}}\Bigr{)}.$
(206)

Invoking the convexity definition (203) with $\theta=a+b$, which by assumption
satisfies $\theta\in[0,1]$, we have that

${\mathcal{C}}_{\alpha}\Bigl{(}(1-a-b){\underline{P}}+a{\underline{Q}}+b{\underline{R}}\Bigr{)}\leq(1-a-b){\mathcal{C}}_{\alpha}\Bigl{(}{\underline{P}}\Bigr{)}+(a+b){\mathcal{C}}_{\alpha}\Biggl{(}\biggl{(}\frac{a}{a+b}\biggr{)}{\underline{Q}}+\biggl{(}\frac{b}{a+b}\biggr{)}{\underline{R}}\Biggr{)}.$
(207)

We then again invoke definition (203), this time with $\theta=\frac{b}{a+b}$,
which also satisfies $\theta\in[0,1]$, to get that

${\mathcal{C}}_{\alpha}\Biggl{(}\biggl{(}\frac{a}{a+b}\biggr{)}{\underline{Q}}+\biggl{(}\frac{b}{a+b}\biggr{)}{\underline{R}}\Biggr{)}\leq\biggl{(}\frac{a}{a+b}\biggr{)}{\mathcal{C}}_{\alpha}\Bigl{(}{\underline{Q}}\Bigr{)}+\biggl{(}\frac{b}{a+b}\biggr{)}{\mathcal{C}}_{\alpha}\Bigl{(}{\underline{R}}\Bigr{)}.$
(208)

Combining the last two inequalities, (207) and (208), results in desired
inequality: (202). $\blacksquare$

## Acknowledgments

This research was partially funded by NSF Grants DMS–1620128 and DMS–2012699.

## Statements and Declarations

Funding.

This research was funded by Iowa State University in Ames, Iowa, USA and US
National Science Foundation Grants DMS–1620128 and DMS–2012699.

Competing interests.

The authors have no conflicts of interest to disclose.

Data availability statement.

Data sharing does not apply to this article as no datasets were generated or
analyzed during the current study.

## References

  * (1) Abdelmalik, M., van Brummelen, E.: Moment closure approximations of the Boltzmann equation based on $\varphi$-divergences.  J. Stat. Phys. 164, 77–104 (2016)
  * (2) Bardos, C., Golse, F., Levermore, D.: Fluid dynamic limits of kinetic equations. I. Formal derivations.  J. Stat. Phys. 63(1–2), 323–344 (1991)
  * (3) Bennoune, M., Lemou, M., Mieussens, L.: Uniformly stable numerical schemes for the boltzmann equation preserving the compressible navier–stokes asymptotics.  J. Comput. Phys. 227, 3781–3803 (2008)
  * (4) Bhatnagar, P., Gross, E., Krook, M.: A model for collision processes in gases I. small amplitude processes in charged and neutral one-component systems.  Phys. Rev. Letters 94(511–525) (1954)
  * (5) Böhmer, N., Torrilhon, M.: Entropic quadrature for moment approximations of the Boltzmann-BGK equation.  J. Comput. Phys. 401(108992) (2020)
  * (6) Broadwell, J.: Study of rarefied shear flow by the discrete velocity method.  J. Fluid Mech. 19, 401–414 (1964)
  * (7) Broadwell, J.E.: Shock structure in a simple discrete velocity gas.  Phys. Fluids 7, 1243–1247 (1964)
  * (8) Caflisch, R., Jin, S., Russo, G.: Uniformly accurate schemes for hyperbolic systems with relaxation.  SIAM J. Numer. Anal. 34, 246–281 (1997)
  * (9) Cai, Z., Fan, Y., Li, R.: Globally hyperbolic regularization of grad’s moment system in one dimensional space.  Comm. Math. Sci. 11, 547–571 (2013)
  * (10) Cai, Z., Fan, Y., Li, R.: Globally hyperbolic regularization of grad’s moment system.  Comm. Pure Appl. Math. 32, 464–518 (2014)
  * (11) Chalons, C., Fox, R., Massot, M.: A multi-Gaussian quadrature method of moments for gas-particle fows in a LES framework.  In: Proceedings of the Summer Program, pp. 347–358. Center for Turbulence Research (2010)
  * (12) Chalons, C., Kah, D., Massot, M.: Beyond pressureless gas dynamics: Quadrature-based velocity moment models.  Comm. Math. Sci. 10, 1241–1272 (2012)
  * (13) Cheng, Y., Rossmanith, J.: A class of quadrature-based moment-closure methods with application to the Vlasov-Poisson-Fokker-Planck system in the high-field limit.  J. Comput. Appl. Math. 262, 384–398 (2014)
  * (14) Cockburn, B., Shu, C.W.: The Runge–Kutta discontinuous Galerkin method for conservation laws V.  J. Comput. Physics 141(2), 199–224 (1998).  DOI 10.1006/jcph.1998.5892.  URL http://www.sciencedirect.com/science/article/pii/S0021999198958922
  * (15) Coron, F., Perhame, B.: Numerical passage from kinetic to fluid equations.  SIAM J. Numer. Anal. 28, 26–42 (1991)
  * (16) Desjardins, O., Fox, R., Villedieu, P.: A quadrature-based moment method for dilute fluid-particle flows.  J. Comput. Phys. 227, 2514–2539 (2008)
  * (17) Dreyer, W.: Maximisation of the entropy in non-equilibrium.  J Phys A-Math 20, 6505–6517 (1987)
  * (18) Felton, C., Harris, M., Logemann, C., Nelson, S., Pelakh, I., Rossmanith, J.: A positivity-preserving limiting strategy for locally-implicit Lax-Wendroff discontinuous Galerkin methods.  https://arxiv.org/abs/1806.06756 (2018)
  * (19) Fox, R.: Computational Models for Turbulent Flows.  Cambridge University Press (2003)
  * (20) Fox, R.: A quadrature-based third-order moment method for dilute gas-particle flows.  J. Comput. Phys. 227, 6313 – 6350 (2008)
  * (21) Fox, R.: Higher-order quadrature-based moment methods for kinetic equations.  J. Comput. Phys. 228, 7771—7791 (2009)
  * (22) Fox, R., Laurent, F., Vié, A.: Conditional hyperbolic quadrature method of moments for kinetic equations.  J. Comput. Phys. 365, 269–293 (2018)
  * (23) Gabetta, E., Pareschi, L., Toscani, G.: Relaxation schemes for nonlinear kinetic equations.  SIAM J. Numer. Anal. 34, 2168–2194 (1997)
  * (24) Gassner, G., Dumbser, M., Hindenlang, F., Munz, C.D.: Explicit one-step time discretizations for discontinuous Galerkin and finite volume schemes based on local predictors.  J. Comput. Physics 230, 4232–4247 (2011)
  * (25) Grad, H.: On the kinetic theory of rarefied gases.  Comm. Pure Appl. Math. 2, 331–407 (1949)
  * (26) Guthrey, P., Rossmanith, J.: The regionally-implicit discontinuous Galerkin method: Improving the stability of DG-FEM.  SIAM J. Num. Analysis 57, 1263–1288 (2019)
  * (27) Jin, S.: Runge-Kutta methods for hyperbolic conservation laws with stiff relaxation terms.  J. Comput. Phys. 122, 51–67 (1995)
  * (28) Jin, S.: Efficient asymptotic-preserving (AP) schemes for some multiscale kinetic equations.  SIAM J. Sci. Comput. 21, 441–454 (1999)
  * (29) Jin, S.: Asymptotic preserving (AP) schemes for multiscale kinetic and hyperbolic equations: a review.  Rivista Di Matematica Della Universita Di Parma 3, 177–216 (2012)
  * (30) Jin, S., Levermore, C.: Numerical schemes for hyperbolic conservation laws with stiff relaxation terms.  J. Comput. Phys. 126, 449–467 (1996)
  * (31) Johnson, E.R.: A high-order discontinuous Galerkin finite element method for a quadrature-based moment-closure model.  Master’s thesis, Iowa State University (2017)
  * (32) Junk, M.: Domain of definition of Levermore’s five-moment system.  J. Stat. Phys. 93, 1143–1167 (1998)
  * (33) Kamermans, M.: Gaussian quadrature weights and abscissae.  URL https://pomax.github.io/bezierinfo/legendre-gauss.html
  * (34) Koellermeier, J., Castro, M.: High-order non-conservative simulation of hyperbolic moment models in partially conservative form.  East Asian J. Appl. Math. 11, 435–467 (2021)
  * (35) Koellermeier, J., Schaerer, R., Torrilhon, M.: A framework for hyperbolic approximation of kinetic equations using quadrature-based projection methods.  Kinetic and Related Models 7(3), 531–549 (2014)
  * (36) Koellermeier, J., Torrilhon, M.: Numerical solution of hyperbolic moment models for the Boltzmann equation.  Eur. J. Mech. B/Fluids 64, 41–46 (2017)
  * (37) von Kowalesky, S.: Zur Theorie der partiallen Differentialgleichungen.  Journal für die reine und angewandte Mathematik 80, 1–32 (1875)
  * (38) Lax, P., Wendroff, B.: Systems of conservation laws.  Comm. Pure Appl. Math. 13, 217–237 (1960)
  * (39) LeVeque, R.: Wave propagation algorithms for multi-dimensional hyperbolic systems.  J. Comp. Phys. 131, 327–335 (1997)
  * (40) LeVeque, R.: Finite Volume Methods for Hyperbolic Problems.  Cambridge University Press (2002)
  * (41) Levermore, C.: Moment closure hierarchies for kinetic theories.  J. Stat. Phys. 83, 1021–1065 (1996)
  * (42) Marchisio, D., Fox, R.: Solution of population balance equations using the direct quadrature method of moments.  J. Aerosol Science 36, 43–73 (2005)
  * (43) Moe, S., Rossmanith, J., Seal, D.: A simple and effective high-order shock-capturing limiter for discontinuous Galerkin methods (2015).  https://arxiv.org/abs/1507.03024
  * (44) Moe, S., Rossmanith, J., Seal, D.: Positivity-preserving discontinuous Galerkin methods with Lax-Wendroff time discretizations.  J. Sci. Comput. 71, 44–70 (2017)
  * (45) Müller, I., Ruggeri, T.: Extended thermodynamics.  Springer (1993)
  * (46) Patel, R., Desjardins, O., Fox, R.: Three-dimensional conditional hyperbolic quadrature method of moments.  J. Comput. Physics: X 1(100006) (2019)
  * (47) Pieraccini, S., Puppo, G.: Implicit–explicit schemes for BGK kinetic equations.  J. Sci. Comput. 32, 1–28 (2007)
  * (48) Platkowski, T., Illner, R.: Discrete velocity models of the Boltzmann equation: a survey on the mathematical aspects of the theory.  SIAM Rev. 30(2), 213–255 (1988)
  * (49) Qiu, J., Dumbser, M., Shu, C.W.: The discontinuous Galerkin method with Lax-Wendroff type time discretizations.  Comput. Methods Appl. Mech. Engr. 194, 4528—4543 (2005)
  * (50) Reed, W., Hill, T.: Triangular mesh methods for the neutron transport equation.  Tech. Rep. LA-UR-73-479, Los Alamos Scientific Laboratory (1973)
  * (51) Rusanov, V.: Calculation of interaction of non-steady shock waves with obstacles.  J. Comp. Math. Phys. USSR 1, 267–279 (1961)
  * (52) Schmüdgen, K.: The Moment Problem.  Graduate Texts in Mathematics. Springer (2017)
  * (53) Sod, G.: A survey of several finite difference methods for systems of nonlinear hyperbolic conservation laws.  J. Comput. Phys. 27, 1–31 (1978)
  * (54) Süli, E., Mayers, D.: An Introduction to Numerical Analysis.  Cambridge University Press (2003)
  * (55) Titarev, V., Toro, E.: ADER: arbitrary high order Godunov approach.  J. Sci. Comput. 17, 609–618 (2002)
  * (56) Torrilhon, M.: Editorial: special issue on moment methods in kinetic gas theory.  Continuum Mech. Thermodyn. 21, 341–343 (2009)
  * (57) Torrilhon, M.: Modeling nonequilibrium gas flows based on moment equations.  Ann. Rev. Fluid Mech. 48(1), 429–458 (2016)
  * (58) Vikas, V., Wang, Z., Passalacqua, A., Fox, R.: Realizable high-order finite-volume schemes for quadrature-based moment methods.  J. Comp. Phys. 230, 5328 – 5352 (2011)
  * (59) Wiersma, C.: A locally-implicit Lax-Wendroff discontinuous Galerkin scheme with limiters that guarantees moment-realizability for quadrature-based moment closures.  Master’s thesis, Iowa State University (2019)
  * (60) Xiong, T., Qiu, J.M.: A hierarchical uniformly high order DG-IMEX scheme for the 1D BGK equation.  J. Comput. Phys. 336, 164–191 (2017)
  * (61) Zhang, X., Shu, C.W.: Maximum-principle-satisfying and positivity-preserving high-order schemes for conservation laws: Survey and new developments.  Proc. R. Soc. A 467, 2752–2776 (2011)
  * (62) Zhang, X., Shu, C.W.: Positivity-preserving high order discontinuous Galerkin schemes for compressible Euler equations with source terms.  J. Comput. Phys. 230, 1238–1248 (2011)


# On the Erdős-Tuza-Valtr Conjecture

Jineon Baek  Jineon Baek, University of Michigan, Department of Mathematics,
2074 East Hall, 530 Church Street, Ann Arbor, MI 48109-1043<EMAIL_ADDRESS>
###### Abstract.

The Erdős-Szekeres conjecture states that any set of more than $2^{n-2}$
points in the plane with no three on a line contains the vertices of a convex
$n$-gon. Erdős, Tuza, and Valtr strengthened the conjecture by stating that
any set of more than $\sum_{i=n-b}^{a-2}\binom{n-2}{i}$ points in a plane
either contains the vertices of a convex $n$-gon, $a$ points lying on a
concave downward curve, or $b$ points lying on a concave upward curve. They
also showed that the generalization is actually equivalent to the Erdős-
Szekeres conjecture.

We prove the first new case of the Erdős-Tuza-Valtr conjecture since the
original 1935 paper of Erdős and Szekeres. Namely, we show that any set of
$\binom{n-1}{2}+2$ points in the plane with no three points on a line and no
two points sharing the same $x$-coordinate either contains 4 points lying on a
concave downward curve or the vertices of a convex $n$-gon.

##  1\. Introduction

A set of $n$ points on a plane is in a _convex position_ if they form the
vertices of a convex polygon. For simplicity, denote any set of $n$ points in
convex position as an _$n$ -gon_. The well-known Erdős-Szekeres conjecture is
the following. Here, a finite set of points on a plane is in _general
position_ if no three points are on a line and no two points share the same
$x$-coordinate111It is not usually required for the $x$-coordinates to be
different when stating the Erdős-Szekeres conjecture. However, the extra
assumption does not hurt generality as we can rotate the point set slightly if
there is any overlap in the $x$-coordinates..

######  Definition 1.1.

For any $n\geq 3$, let $N(n)$ be the maximum number of points on a plane in a
general position with no subset forming an $n$-gon.

######  Conjecture 1 (Erdős-Szekeres [4]).

For any $n\geq 3$, $N(n)=2^{n-2}$.

In 1935, Erdős and Szekeres showed
$N(n)\leq\binom{2n-4}{n-2}=O\left(4^{n}/\sqrt{n}\right)$ [3]. In 1960, they
provided a construction of exactly $2^{n-2}$ points with no $n$ points in
convex position, showing the lower bound $N(n)\geq 2^{n-2}$ [4]. The upper
bound of $N(n)$ stayed in the magnitude of $O(4^{n}/\sqrt{n})$ despite many
improvements [2, 8, 14, 15, 9, 11] until Suk [12] proved an upper bound of
$N(n)\leq 2^{n+o(n)}$ in 2016. The best upper bound so far is $N(n)\leq
2^{n+O(\sqrt{n\log n})}$ [7], and the precise equality $N(n)=2^{n-2}$ remains
neither proven or disproven to this date.

Now we state the generalization of Conjecture 1 by Erdős, Tuza, and Valtr [5].

######  Definition 1.2.

An _$a$ -cap_ (resp. _$a$ -cup_) is a set of $a$ points lying on the graph of
a downwardly (resp. upwardly) convex function (see Figure 1).

######  Definition 1.3.

Call any tuple $(n,a,b)$ of integers satisfying $2\leq a,b\leq n\leq a+b-2$ a
_triplet_. For any triplet $(n,a,b)$, define $N(n,a,b)$ as the maximum number
of points on a plane in general position with no subset forming an $n$-gon,
$a$-cap, or $b$-cup.

Figure 1. A 4-cap, 5-cup and 6-gon (from left to right)

######  Conjecture 2 (Erdős-Tuza-Valtr [5]).

For any triplet $(n,a,b)$, we have

$N(n,a,b)=\sum_{i=n-b}^{a-2}\binom{n-2}{i}.$

######  Definition 1.4.

For any triplet $(n,a,b)$, let $P(n,a,b)$ be the statement that
$N(n,a,b)=\sum_{i=n-b}^{a-2}\binom{n-2}{i}.$ That is, $P(n,a,b)$ is the
special case of Conjecture 1 with the triplet $(n,a,b)$.

Then the special case $P(n,n,n)$ of Conjecture 2 is Conjecture 1, as
$n$-caps/cups are $n$-gons and the conjectured sum equals $2^{n-2}$.
Interestingly, they showed that the strengthened Conjecture 2 is actually
_implied by_ the original Conjecture 1 as well.

######  Theorem 1.5 ([5]).

Conjecture 1 and Conjecture 2 are equivalent. Specifically, for any $n\geq 3$
and any triplets $(n,a,b)$, $(n,a^{\prime},b^{\prime})$ with $a\geq
a^{\prime}$ and $b\geq b^{\prime}$, the statement $P(n,a,b)$ implies
$P(n,a^{\prime},b^{\prime})$.

So any counterexample of Conjecture 2 for one triplet $(n,a,b)$ would disprove
Conjecture 1 immediately. Indeed, such a line of attack [1] succeeded in
disproving a set-theoretic generalization [13] of Conjecture 1 by disproving
an analogous set-theoretic generalization of Conjecture 2 for the triplet
$(n,4,n)$.

It is then natural to ask whether the original Conjecture 2 will hold for the
same triplet $(n,4,n)$ or not. We show that it does.

######  Theorem 1.6 (Main Theorem).

For any $n\geq 3$, the statement $P(n,4,n)$ holds. That is, $\binom{n-1}{2}+2$
points on a plane in general position determine either a 4-cap or a $n$-gon.

Related, Erdős and Szekeres proved the following _cups-caps theorem_ in 1935
[3].

######  Theorem 1.7 (Erdős–Szekeres).

For any $a,b\geq 2$, any set of more than $\binom{a+b-4}{a-2}$ points in
general position contains either an $a$-cap or $b$-cup.

For any $a,b\geq 2$, the cases $P(a+b-3,a,b)$ and $P(a+b-2,a,b)$ of Conjecture
2 are immediate consequences of this theorem. To see this, observe that any
$(a+b-3)$-gon either contains an $a$-cap on top or a $b$-cap on the bottom,
and that the conjectured values
$N(a+b-3,a,b)=\binom{a+b-5}{a-3}+\binom{a+b-5}{a-2}=\binom{a+b-4}{a-2}$ and
$N(a+b-2,a,b)=\binom{a+b-4}{a-2}$ match with the cups-caps theorem. Our
Theorem 1.6 is not a consequence of the cups-caps theorem as $n<a+b-3$ in the
triplet $(n,4,n)$.

By Theorem 1.5, for triplets $(n,a,b)$ with a fixed $n$, the cases $P(n,a,b)$
of Conjecture 2 form a pyramid of implications from top to bottom (Figure 2).
On the top, we have the Erdős-Szekeres conjecture (Conjecture 1), and at the
bottom, we have the cups-caps theorem (Theorem 1.7). Our theorem lies strictly
in the middle of them (Theorem 1.6). To the best of our knowledge, this is the
first new instance of Conjecture 2 proven so far since the original 1935 paper
[3] of Erdős and Szekeres.

$P(n,n,n)$$P(n,n-1,n)$$P(n,n,n-1)$$P(n,n-2,n)$$P(n,n-1,n-1)$$P(n,n,n-2)$$P(n,4,n)$$P(n,5,n-1)$$\phantom{P(}\cdots\phantom{P)}$$P(n,n,4)$$P(n,3,n)$$P(n,4,n-1)$$\phantom{P(}\cdots\phantom{P)}$$\phantom{P(}\cdots\phantom{P)}$$\phantom{P(}\cdots\phantom{P)}$$P(n,n,3)$Erdős-
Szekeres (Conjecture 1)Our theorem (Theorem 1.6)Cups-caps theorem (Theorem
1.7)$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$$\cdots$

Figure 2. A schematic diagram of the implications between Conjecture 1,
Theorem 1.7 and our Theorem 1.6.

The proof of main Theorem 1.6 generalizes to a purely combinatorial model of
convexity (Theorem 2.7). Section 2 describes the combinatorial setup we mainly
work with. Section 3 describes the _$\alpha$ -statistic_, a function for
understanding $a$-cap, $b$-cup free configurations especially with nearly
maximal number of points. Section 4 introduces $(\alpha,\beta)$-plane, an
useful notion for understanding 4-cap free configurations, and motivates the
definition of _interweaved laced cups_ (Definition 4.4 and 4.5). Finally,
Section 5 proves main Theorem 1.6 by finding interweaved laced cups with
induction (Theorem 5.10).

##  2\. A combinatorial model of convexity

We introduce a purely combinatorial model of convexity that we mainly work
with. It is a slight modification of the one first suggested in [13] and
explored further in [6], [10] and [1].

######  Definition 2.1.

In this paper, a _configuration_ is a finite set $S$ of elements called
_points_ or _vertices_ equipped with the following structures.

  * •

A linear ordering $<$ of the vertices.

  * •

For any subset of $S$ with size 3, an arbitrary assignment of whether they
form a cap or a cup.

In standard terms, a configuration is a bi-coloring of a finite, complete
3-uniform hypergraph with a prescribed linear ordering of vertices.

Given a finite set of points in general position, we can make a configuration
by ordering the points in their increasing $x$-coordinates and assigning each
size 3 subset to be either a cap or cup according to its position in the
plane. Let’s say that a configuration is _realizable_ if it can be constructed
from actual points in this way. The notion of caps and cups in plane are
generalized to arbitrary configurations which may not be realizable.

######  Definition 2.2.

Denote any set of vertices $x_{1}<x_{2}<\cdots<x_{a}$ of a configuration as
simply $x_{1}x_{2}\cdots x_{a}$ in the increasing order.

In a configuration, a set $C=x_{1}x_{2}\cdots x_{a}$ of $a$ vertices forms an
$a$-cup (resp. $a$-cap) if any three consecutive points $x_{i-1}x_{i}x_{i+1}$
form a cup (resp. cap) for any $1<i<a$. In particular, we allow 1-cups and
1-caps. The _size_ of $C$, also denoted $|C|$, is the number of vertices $a$
in $C$.

We say that $x_{1}$ is the _starting point_ of $C$ and $x_{a}$ is the _ending
point_ of $C$. The points $x_{1}$ and $x_{a}$ are the _endpoints_ of $C$.
Equivalently, we say that $C$ starts with $x_{1}$ and ends with $x_{a}$, or
that $C$ is a cap (resp. cup) from $x_{1}$ to $x_{a}$. Call any pair $x<y$ of
vertices in a configuration an _edge_. If the size $a$ of $C$ is at least 2,
we say that $C$ _starts_ with the edge $x_{1}x_{2}$ and _ends_ with the edge
$x_{a-1}x_{a}$.

For a cap (resp. cup) $C$ from vertex $s$ to vertex $t$, say that $C$ _extends
to left_ with the vertex $x$ (or edge $xs$) if $xC$ is also a cap (resp. cup).
Likewise, say that $C$ _extends to right_ with the vertex $x$ (or edge $tx$)
if $Cx$ forms a cap (resp. cup).

We also introduce the _mirror reflection_ of a configuration. For realizable
configurations, this corresponds to reflecting the points along the $y$-axis.

######  Definition 2.3.

The _mirror reflection_ $S^{op}$ of a configuration $S$ is the configuration
with the same vertex set and assignments of 3-caps and 3-cups, but the
prescribed linear ordering reversed. In this way, a cap (resp. cup) $C$ in $S$
naturally corresponds to the reflected cap (resp. cup) $C^{op}$ in $S^{op}$
with the same set of vertices.

We introduce two possible generalizations of an $n$-gon in this combinatorial
model of convexity.

######  Definition 2.4.

In a configuration, a _weak $(a,b)$-gon_ is a pair of $a$-cap $C_{1}$ and
$b$-cup $C_{2}$ sharing the same endpoints $x$ and $y$. An _weak $n$-gon_ is
any weak $(a,b)$-gon with $a+b=n+2$.

On the other hand, a _strong $(a,b)$-gon_ is a weak $(a,b)$-gon
$(C_{1},C_{2})$ with the additional constraint that $C_{1}\cap
C_{2}=\\{x,y\\}$. An _strong $n$-gon_ is any strong $(a,b)$-gon with
$a+b=n+2$.

An _$(a,b)$ -gon_ or _$n$ -gon_ denotes the weak $(a,b)$-gon or $n$-gon by
default.

The only difference is that a weak $n$-gon allows the cap and cup to have
overlapping vertices in the middle, while a strong $n$-gon does not. Note also
that there is no difference in any realizable configurations. We use the
following notion.

######  Definition 2.5.

A configuration is $a$-cap (resp. $b$-cup or weak/strong $n$-gon) free if it
has no $a$-cap (resp. $b$-cup or weak/strong $n$-gon) in the configuration.

Peters and Szekeres [13] proposed to generalize Conjecture 1 by stating that
for any $n\geq 2$, the maximum size of a _strong_ $n$-gon free configuration
is $2^{n-2}$, and supplied a computer proof for the case $n=6$. Later, Balko
and Valtr [1] found counterexamples for $n=7$ and $8$ with SAT solvers by
finding counterexamples for analogues of Conjecture 2. We instead propose to
use the definition of a _weak_ $n$-gon instead to generalize Conjecture 1.

######  Conjecture 3 (Set-theoretic Erdős-Szekeres).

For any $n\geq 2$, the maximum size $\widehat{N}(n)$ of a _weak_ $n$-gon free
configuration is equal to $2^{n-2}$.

From now on, we omit the word _weak_ when we mention any $(a,b)$-gon or
$n$-gon. We can also state the analogous generalization of Conjecture 2 to
arbitrary configurations.

######  Conjecture 4 (Set-theoretic Erdős-Tuza-Valtr).

For any triplet $(n,a,b)$, the maximum size $\widehat{N}(n,a,b)$ of a weak
$n$-gon, $a$-cap and $b$-cup free configuration is equal to
$\sum_{i=n+2-b}^{a}\binom{n-2}{i-2}$.

The generalization of cups-caps theorem (Theorem 1.7) to arbitrary
configurations is well-known (e.g. [10]).

######  Theorem 2.6 (Set-theoretic cups-caps).

For any $a,b\geq 2$, the maximum size of an $a$-cap and $b$-cup free
configuration is $\binom{a+b-4}{a-2}$.

Our main result is the proof of Conjecture 4 for the case $(n,a,b)=(n,4,n)$.
It is the generalization of Theorem 1.6 to arbitrary configurations.

######  Theorem 2.7.

For any $n\geq 3$, any configuration of size $\binom{n-1}{2}+2$ contains
either a 4-cap, $n$-cup or a $(3,n-1)$-gon.

##  3\. Structure of $a$-cap, $b$-cup free configurations

In this section, we discuss some properties of a configuration $S$ that avoids
$a$-caps and $b$-cups. They will be useful especially when the size of $S$ is
close to the maximum possible value $\binom{a+b-4}{a-2}$ shown in Theorem 2.6.
We do not claim originality of the results in this section - it is mostly a
recasting of the definitions introduced in [10].

First, we define the _slope labeling_ of an $a$-cap free configuration $S$.

######  Definition 3.1.

A _slope labeling_ $s$ of an $a$-cap free configuration $S$ is the assignment
of an integer $s(xy)\in\\{1,2,\cdots,a-2\\}$ to all the edges $xy$ of $S$ so
that it satisfies the following.

  * •

For any points $x<y<z$ in $S$, $s(xy)\leq s(yz)$ implies that $xyz$ is a
3-cup.

The value $s(xy)$ assigned to the edge $xy$ is the _label_ of $xy$.

For the actual slope $s_{\mathbb{R}}(xy)\in\mathbb{R}$ of an edge in a
realizable configuration $S$, both the following properties would hold.

  * •

For any points $x<y<z$ in $S$, $s_{\mathbb{R}}(xy)>s_{\mathbb{R}}(yz)$ implies
that $xyz$ is a 3-cap.

  * •

For any points $x<y<z$ in $S$, $s_{\mathbb{R}}(xy)<s_{\mathbb{R}}(yz)$ implies
that $xyz$ is a 3-cup.

A slope labeling restricts the possible values of a ‘slope’ (label) to a much
smaller set $\\{1,2,\cdots,a-2\\}$ at the cost of giving up the first
property. That is, edges of strictly decreasing labels may not form a cap (see
the cup ABF in Figure 3). It is also impossible in general to assign a slope
labeling that satisfies both the properties. However, any $a$-cap free
configuration has a slope labeling that satisfies the second property.

######  Theorem 3.2.

For any $a$-cap free configuration $S$, a slope labeling always exists. In
particular, for any edge $e$, let $c(e)$ be the maximum length of a cap
starting with $e$; the function $c(e)-1$ is a slope labeling.

###### Proof.

For any edge $e$, its assigned label $i$ is in between 1 and $a-2$ inclusive
by definition. Assume by contrary that there is a 3-cap $xyz$ in $S$ with the
label $s$ of $xy$ less than or equal to the label $t$ of $yz$. As the label of
edge $yz$ is $t$, there is a cap $C$ of size $t+1$ starting with $yz$. Since
$xyz$ forms a cap, the cap $C$ extends to a cap $xC$ of size $t+2$ that starts
with $xy$. By the definition of $s$, we have $s+1\geq t+2$, which contradicts
the hypothesis $s\leq t$. ∎

ABCDEF$2$$1$$2$$2$$1$$2$$1$$1$$1$$1$$1$ Figure 3.  A $4$-cap and $4$-cup free
realizable configuration with the slope labeling of Theorem 3.2. The labels of
the edges AF, BD, CD and CE are 1, 2, 2 and 2 respectively.

For the rest of the paper, we will fix a large $a$-cap free configuration $S$
and a slope labeling of $S$ so that there is no confusion in the label of an
arbitrary edge of $S$. The following lemma is immediate.

######  Lemma 3.3.

For any $a$-cap free configuration $S$ with slope labeling $s$, the
restriction of $s$ to an arbitrary subset $S^{\prime}$ of $S$ is a slope
labeling of $S^{\prime}$.

Assume any $a$-cap, $b$-cup free configuration $S$ with a slope labeling $s$
by integers from 1 to $a-2$. For each point $p$ of $S$, we assign its
_$\alpha$ -statistic_ which is a tuple
$\alpha(p)=(\alpha_{1}(p),\alpha_{2}(p),\cdots,\alpha_{a-2}(p))$ of natural
numbers.

######  Definition 3.4.

Fix any $a$-cap, $b$-cup free configuration $S$ with a slope labeling. For all
$p\in S$ and $1\leq i\leq a-2$, define the integer $\alpha_{i}(p)$ as maximum
length of a cup that ends with the point $p$ and an edge of slope $\leq i$. If
there is no such cup, then let $\alpha_{i}(p)=1$. In particular, the rightmost
point $p$ has the value $\alpha^{i}(p)=1$ for any $i$. The _$\alpha$
-statistic_ of a point $p$ in $S$ is the tuple
$\alpha(p)=(\alpha_{1}(p),\alpha_{2}(p),\cdots,\alpha_{a-2}(p))$.

######  Definition 3.5.

For any integers $a,b\geq 2$, define the grid simplex

$T_{a,b}:=\\{(x_{1},x_{2},\cdots,x_{a-2})\in\mathbb{N}^{a-2}\colon 1\leq
x_{1}\leq\cdots\leq x_{a-2}\leq b-1\\}.$

######  Theorem 3.6.

For any $a$-cap, $b$-cup free configuration $S$ with a fixed slope labeling
$s$, the $\alpha$-statistic of $S$ satisfies the following.

  1. (1)

For any point $p$, $1\leq\alpha_{1}(p)\leq\cdots\leq\alpha_{a-2}(p)\leq b-1$.
Consequently, the $\alpha$-statistic $\alpha$ is a map from $S$ to $T_{a,b}$.

  2. (2)

For any two points $x<y$ connected by an edge of label $i$,
$\alpha_{i}(x)<\alpha_{i}(y)$ holds. So in particular, $\alpha$ is injective.

###### Proof.

We check the two conditions the $\alpha$-statistic has to satisfy. The
inequality $1\leq\alpha_{1}(p)\leq\cdots\leq\alpha_{a-2}(p)\leq b-1$ for any
point $p$ follows directly from the definitions. The cup of length
$\alpha_{i}(x)$ that ends with the vertex $x$ and an edge of label $\leq i$
can be extended to the right with the edge $xy$ of label $i$, so that
$\alpha_{i}(x)+1\leq\alpha_{i}(y)$ in any of the two given definitions of
$\alpha_{i}$. ∎

Note that the size of $T_{a,b}$ is $\binom{a+b-4}{a-2}$. For a quick proof,
note that any $(x_{1},x_{2},\cdots,x_{a-2})\in T_{a,b}$ corresponds
bijectively to an arbitrary subset $\\{x_{i}+i-1\colon 1\leq i\leq a-2\\}$ of
$\\{1,2,\cdots,a+b-4\\}$ of size $a-2$. Consequently, $\alpha$ being injective
immediately proves Theorem 2.6 that $|S|\leq\binom{a+b-4}{a-2}$. Therefore, if
the size of $S$ is nearly equal to the maximum size $\binom{a+b-4}{a-2}$, we
can expect the map $\alpha$ to be almost bijective with some exceptional
‘holes’ in $T_{a,b}$.

Let us end this section with a remark on the $\alpha$-statistic of the mirror
configuration.

######  Definition 3.7.

For any $a$-cap, $b$-cup free configuration $S$ and its slope labeling $s$,
define the mirror reflection $s^{\textnormal{op}}$ of the slope labeling $s$
as the following.

$s^{\textnormal{op}}(yx)=a-1-s(xy)$

We leave it as an exercise to show that $s^{\textnormal{op}}$ is a proper
slope labeling of $S^{\textnormal{op}}$.

######  Lemma 3.8.

The mirror reflection $s^{\textnormal{op}}$ of a slope labeling $s$ of $S$ is
a slope labeling of $S^{\textnormal{op}}$.

######  Remark 3.9.

We use the mirror reflection of a labeling extensively to exploit the symmetry
without loss of generality. For example, take an arbitrary 4-cap free
configuration $S$. Its slope labeling $s$ has values in $\\{1,2\\}$. So for
any edge $xy$, if its label $s(xy)$ is 1 (resp. 2) then the labeling
$s^{\textnormal{op}}(yx)$ of its reflection is 2 (resp. 1). Therefore, if the
statement we want to show regarding $S$ is invariant under reflection, then we
can safely assume that the edge connecting $x$ and $y$ is labeled 1 by
reflecting $S$ if necessary.

##  4\. The $(\alpha,\beta)$-plane

In this section, we focus our attention on an arbitrary 4-cap, $n$-cup free
configuration $S$ with a fixed slope labeling and $\alpha$-statistic.

$\alpha(p)$$\beta(p)$112233ABCDEF$2$$1$$2$$2$$1$$2$$2$$1$$1$$1$$1$ Figure 4.
The $(\alpha,\beta)$-plane of the 4-cap, 4-cup free configuration in Figure 3
with the slope labels of some edges.

In our configuration $S$, we only have edges of label 1 and 2, and the
following is an immediate consequence of Definition 3.1. We will use this
extensively without further mentions.

######  Corollary 4.1.

In an arbitrary 4-cap free configuration with slope labeling, any edge of
label 1 extends a cup to the left. That is, for any edge $pq$ of label 1 and a
cup $C$ that starts with $q$, the sequence $pC$ is also a cup.

Likewise, any edge of label 2 extends a cup to the right. That is, for any
edge $pq$ of label 2 and a cup $C$ that ends with $p$, the sequence $Cq$ is
also a cup.

Also, we define aliases for the $\alpha$-statistic of $S$.

######  Definition 4.2.

For an arbitrary 4-cap, $n$-cup free configuration $S$ with a fixed slope
labeling and $\alpha$-statistic $p\mapsto(\alpha_{1}(p),\alpha_{2}(p))$,
define aliases $\alpha=\alpha_{1}$ and $\beta=\alpha_{2}$.

Thus, $\alpha(p)=\alpha_{1}(p)$ is the maximum length of a cup that ends with
the vertex $p$ and an edge of label 1 ($\alpha(p)=1$ if there is no such cup).
The value $\beta(p)=\alpha_{2}(p)$ is the maximum length of any cup that ends
with the vertex $p$.

The $\alpha$-statistic $\alpha(p)=(\alpha(p),\beta(p))$ maps $S$ to the
triangular grid set

$T_{4,n}:=\\{(a,b)\in\mathbb{N}^{2}\colon 1\leq a\leq b\leq n-1\\}$

injective by Theorem 3.6. With this, if the size of $S$ is
$|T_{4,n}|-k=\binom{n-1}{2}-k$ where $k$ is small, it helps to identify $S$
with the grid points $T_{4,n}$ with $k$ missing holes (see Figure 4). Call
such a diagram an _$(\alpha,\beta)$ -plane_ of the 4-cap, $n$-cup free
configuration $S$. The following is a direct consequence of Theorem 3.6, and
we will use it extensively without mentioning.

######  Corollary 4.3.

Assume an arbitrary 4-cap, $n$-cup free configuration $S$.

For any points $p,q$ with $\beta(p)=\beta(q)$,

  * •

$p$ and $q$ are always connected with an edge of label 1

  * •

and $p<q$ if and only if $\alpha(p)<\alpha(q)$.

Consequently, in an $(\alpha,\beta)$-plane any horizontal edge is labeled 1,
and each column is sorted in the increasing order of vertices from left to
right.

Likewise, for any points $p,q$ with $\alpha(p)=\alpha(q)$,

  1. (1)

$p$ and $q$ are always connected with an edge of label 2

  2. (2)

and $p<q$ if and only if $\beta(p)<\beta(q)$.

Consequently, in an $(\alpha,\beta)$-plane any vertical edges is labeled 2,
and each row is sorted in the increasing order of vertices from bottom to top.

We will now use the concept of the $(\alpha,\beta)$-plane to introduce and
motivate several key notions for our proof. Take a 4-cap, $n$-cup free
configuration $S$. For simplicity, assume at first that $S$ of size
$\binom{n}{2}$ (the maximum possible size), so that every location in the
$(\alpha,\beta)$-plane is occupied. Then we can identify a point $p$ in $S$
with its location $(\alpha(p),\beta(p))$ in the $(\alpha,\beta)$-plane.

Take any $1\leq k\leq n-1$ and consider the path of vertices

$C_{k}=(1,k),(2,k),\dots,(k-1,k),(k,k),(k,k+1),\dots,(k,n-1)$

in the $(\alpha,\beta)$-plane. By Corollary 4.3, the first $k-1$ edges in this
path are labeled 1, and the last $n-k-1$ edges are labeled 2, so these points
must form an $(n-1)$-cup $C_{k}$ from start $p_{k}=(1,k)$ to end
$q_{k}=(k,n-1)$. For any pair of $(n-1)$-cups $C_{k}$ and $C_{l}$ with $k<l$,
the ordering of their endpoints is then $p_{k}<p_{l}\leq q_{k}<q_{l}$.
Motivated by this, we introduce the following definition of _interweaved
cups_.

######  Definition 4.4.

Two cups $C_{1}$ and $C_{2}$ running from $p$ to $r$ and $q$ to $s$
respectively are _interweaved_ if $p<q\leq r<s$ holds.

So if $|S|=\binom{n}{2}$, we get $n-1$ different $(n-1)$-cups
$C_{1},\dots,C_{n-1}$ all mutually interweaved. Moreover, for each cup $C_{k}$
we have the $k$-cup $D_{k}$ of vertices

$D_{k}=(1,1),(1,2),...,(1,k)$

that ends with the left endpoint $p_{k}$ of $C_{k}$ and the $(n-k)$-cup
$E_{k}$ of vertices

$E_{k}=(k,n-1),(k+1,n-1),...,(n-1,n-1)$

that starts with the right endpoint $q_{k}$ of $C_{k}$. Motivated by this, we
introduce the following notion of _laced cups_.

######  Definition 4.5.

A $(n-1)$-cup $C$ from $p$ to $q$ is _laced_ if there exists a cup $C_{p}$
that ends with $p$, and a cup $C_{q}$ that starts with $q$, so that
$|C_{p}|+|C_{q}|=n-1$.222One might expect the sum to be $n$ given the above
motivation, but it turns out that $n-1$ is sufficient.

So if $|S|=\binom{n}{2}=\binom{n-1}{2}+(n-1)$, then all of our mutually
interweaved $(n-1)$-cups $C_{k}$ are laced. The importance of this concept
will be shown in Lemma 5.2 which shows that if $S$ contains just _two_
interweaved laced $(n-1)$-cups, then $S$ contains a $(3,n-1)$-gon. We expect
that for $|S|=\binom{n-1}{2}+d$ with any $1\leq d\leq n-1$, we can find $d$
mutually interweaved laced $(n-1)$-cups (Conjecture 5). Roughtly, this amounts
to saying that an additional hole in the $(\alpha,\beta)$-plane only destroys
one of the mutually interweaved laced $(n-1)$-cups.

We show this for $d=2$ (Theorem 5.10) and this is sufficient to show the main
theorem that for $|S|=\binom{n-1}{2}+2$ we can always find an $n$-gon (Theorem
2.7). The proof for case $d=2$ requires a delicate inductive argument and
several lemmas about interweaved laced $(n-1)$-cups; we now turn to stating
and proving those lemmas. Before doing so, we briefly remark that the concept
of interweaved cups and of laced cups are symmetric under mirror reflection.

######  Lemma 4.6.

Two cups $C_{1},C_{2}$ are interweaved in configuration $S$ if and only if
$C_{2}^{\textnormal{op}}$ and $C_{1}^{\textnormal{op}}$ are interweaved in
$S^{\textnormal{op}}$. An $(n-1)$-cup $C$ is laced in configuration $S$ if and
only if $C^{\textnormal{op}}$ is laced in $S^{\textnormal{op}}$.

##  5\. Interweaved laced cups

We first show that in a 4-cap free configuration, a pair of interweaved laced
$(n-1)$-cups from $p$ to $r$ and $q$ to $s$ respectively (so that $p<q\leq
r<s$) is sufficient to force an $n$-gon. The following covers the degenerate
case $q=r$.

######  Lemma 5.1 (Balko and Valtr [1]).

Take any $n\geq 3$ and a 4-cap, $n$-cup free configuration $S$. If the ending
point $x$ of an $(n-1)$-cup $C_{1}$ is also the starting point of another
$(n-1)$-cup $C_{2}$, then $S$ contains an $(3,n-1)$-gon.

$x$1$a$$b$$c$$Q$$P$ Figure 5. Figure for the proof of Lemma 5.1. The cup $P$
ends at $a$ and the cup $Q$ is from $b$ to $c$.

###### Proof.

(See Figure 5) Say $C_{1}=Px$ where $P$ is an $(n-2)$-cup that ends with some
vertex $a$. Likewise, say that $C_{2}=xQ$ where $Q$ is an $(n-2)$-cup that
starts with $b$. Note that the statement to prove and the definitions
introduced so far are symmetric under reflection. So without loss of
generality, we can assume that $ab$ is labeled 1. Now $aQ$ is a $(n-1)$-cup
because $ab$ has label 1. Say that $Q$ ends with the point $c$.

If $axc$ is a cap, then we find the $(3,n-1)$-gon formed by $axc$ and
$aC_{2}^{\prime}$ and we are done. If $axc$ is a cup, then the $(n-1)$-cup
$C_{1}$ extends to the right with vertex $c$, contradicting that $S$ is
$n$-cup free. ∎

Now we show the general case $q\leq r$.

######  Lemma 5.2.

Take any 4-cap, $n$-cup free configuration $S$ where $n\geq 3$. If $S$
contains a pair of interweaved laced $(n-1)$-cups, then $S$ contains an
$(3,n-1)$-gon.

$p$$q$$r$$s$$C_{p}$$C_{r}$12$C_{1}$$C_{2}$ Figure 6. Figure for the proof of
Lemma 5.2. The cup $C_{p}$ ends with $p$ and $C_{r}$ starts with $r$.

###### Proof.

(See Figure 6) Let $C_{1}$ and $C_{2}$ be the pair of interweaved laced
$(n-1)$-cups from $p$ to $r$ and $q$ to $s$ respectively, so that $p<q\leq
r<s$. If $q=r$, we are done by Lemma 5.1, so we can assume $q<r$. As the setup
is symmetric along reflection (e.g. Remark 3.9 and 4.6), we can assume that
the edge $qr$ is of label 1 without loss of generality.

As $C_{1}$ is laced we have a cup $C_{p}$ ending with $p$ and and a cup
$C_{r}$ starting with $r$ so that $|C_{p}|+|C_{r}|=n-1$. Observe that the edge
$pq$ is of label 2, or otherwise we can extend the $(n-1)$-cup $C_{2}$ to left
with $pq$ and reach contradiction.

If $pqr$ is a cap, then the cap $pqr$ and the cup $C_{1}$ forms a
$(3,n-1)$-gon and we are done. Now assume that $pqr$ is a cup. Since $pq$ is
of label 2, the cup $C_{p}$ extends to right with $q$. Since $qr$ is of label
1, the cup $C_{r}$ extends to left with $q$ as well. Now the cups $C_{p}q$ and
$qC_{r}$ are joined along the vertex $q$. Since $pqr$ is a cup, they all
connect to make a cup $C_{p}qC_{r}$ of size $|C_{p}|+|C_{r}|+1=n$, leading to
contradiction. ∎

We prepare more lemmas and observations before starting the main proof. In
particular, we will use the following special case to find a pair of
interweaved laced cups. Note that for this lemma we have $n\geq 4$ instead of
$n\geq 3$.

######  Lemma 5.3.

Take any 4-cap, $n$-cup free configuration $S$ with $n\geq 4$. Assume an
$(n-1)$-cup $C$ from $x$ to $y$ in $S$. Also, assume an $(n-2)$-cup $C_{x}$
that ends with $x$, and an $(n-2)$-cup $C_{y}$ that starts with $y$. Then $S$
contains a pair of interweaved laced $(n-1)$-cups.

$x$$a$$b$$y$$d$$c$$Q$$P$$R$ Figure 7. Figure for the proof of Lemma 5.3. The
cups $P$, $Q$ and $R$ contains the endpoints $a$, $b$ and $c$, and $d$
respectively.

###### Proof.

Using the symmetry of the statement along mirror reflection, we can assume
that $xy$ is labeled 1 without loss of generality.

Let $C_{x}=Px$, $C=xQy$ and $C_{y}=yR$ so that $P,Q,R$ are $(n-3)$-cups (see
Figure 7). Let $a$ be the ending point of $P$ and $d$ be the starting point of
$R$. Say that $Q$ is from point $b$ to $c$. As $|P|,|Q|,|R|\geq 1$, the points
$a,b,c$ and $d$ are all well-defined and we have $a<x<b\leq c<y<d$ (there is a
possibility for $b=c$ when $n=4$).

The sequence $xyR$ is an $(n-1)$-cup because $xy$ is labeled 1 and $C_{y}=yR$
is $(n-2)$-cup. It is also laced because $x$ is the endpoint of the
$(n-2)$-cup $C_{x}=Px$. So we have two laced $(n-1)$-cups $xQy=C$ and $xyR$.

Do case analysis on the label of $ab$. Assume first that $ab$ is labeled 1.
Then $aQy$ is an $(n-1)$-cup. It is also laced because $a$ is a 1-cup and $yR$
is a $(n-2)$-cup. $aQy$ interweaves with the laced $(n-1)$-cup $xyR$ because
$a<x<y$ and the endpoint of $R$ is strictly on the right of $y$.

Assume now that $ab$ is labeled 2. We do another case analysis on the label of
$by$. If $by$ is labeled 1, then $byR$ is a laced $(n-1)$-cup because it is a
$(n-1)$-cup and $Pb$ is a $(n-2)$-cup. Now the laced $(n-1)$-cups $xQy$ and
$byR$ are interweaved because $x<b<y$ and the endpoint of $R$ is strictly on
the right of $y$. If $by$ is labeled 2, then $Pby$ is an $(n-1)$-cup, and it
is also laced because $yR$ is an $(n-2)$-cup. Now laced $(n-1)$-cups $Pby$ and
$xyR$ are interweaved, because the starting point of $P$ comes before $x$,
$x<y$, and the endpoint of $R$ is strictly on the right side of $y$. The proof
is now done. ∎

We introduce the following terminologies for a 4-cap, $n$-cup free
configuration $S$ of size at least $\binom{n-1}{2}+1$. Note that the following
definition does not depend on a particular choice of a slope labeling of $S$.

######  Definition 5.4.

Assume an arbitrary 4-cap, $n$-cup free configuration $S$ of size at least
$\binom{n-1}{2}+1$ with $n\geq 3$.

Define $L(S)$ as the set of left endpoints of all $(n-1)$-cups in $S$, and
$R(S)$ as the set of right endpoints of all $(n-1)$-cups in $S$. Let $p_{S}$
be the rightmost point of $L(S)$ and $q_{S}$ be the leftmost point of $R(S)$.
By Theorem 2.6, there is at least one $(n-1)$-cup in $S$, so that $L(S),R(S)$
are nonempty and the points $p_{S},q_{S}$ are well-defined.

######  Remark 5.5.

Note that under the assumption of Definition 5.4,
$L(S^{\textnormal{op}})=R(S)$, $R(S^{\textnormal{op}})=L(S)$,
$p_{S^{\textnormal{op}}}=q_{S}$ and $q_{S^{\textnormal{op}}}=p_{S}$.

######  Lemma 5.6.

Under the assumption of Definition 5.4, we always have $p_{S}\leq q_{S}$. In
other words, the sets $L(S)$ and $R(S)$ are separated in the increasing order
with at most one overlap.

###### Proof.

Assume the contrary that $p_{S}>q_{S}$. Take any slope labeing of $S$. If the
edge $q_{S}p_{S}$ is of label 1 we can extend an $(n-1)$-cup starting with
$p_{S}$ to the left by $q_{S}$, finding an $n$-cup in $S$. Likewise, if the
edge $q_{S}p_{S}$ is of label 2 we can extend an $(n-1)$-cup starting with
$q_{S}$ to the right by $p_{S}$, finding an $n$-cup in $S$. Both cases lead to
contradiction. ∎

We rule out the following case where we can find a pair of interweaved laced
$(n-1)$-cups immediately as well.

######  Lemma 5.7.

Assume an arbitrary 4-cap, $n$-cup free configuration $S$ of size at least
$\binom{n-1}{2}+1$. If a $(n-2)$-cup in $S$ ends with $p_{S}$ and a
$(n-2)$-cup in $S$ starts with $q_{S}$, then $S$ contains a pair of
interweaved laced $(n-1)$-cups.

###### Proof.

An $(n-1)$-cup $C_{l}$ from some $p^{\prime}\in L(S)$ to $q_{S}$ exists by the
definition of $q_{S}$ and $L(S)$. Likewise, an $(n-1)$-cup $C_{r}$ from
$p_{S}$ to some $q^{\prime}\in R(S)$ exists by the definition of $p_{S}$ and
$R(S)$. Note that $C_{l}$ (or $C_{r}$) is laced by the existence of a
$(n-2)$-cup that ends with $p_{S}$ (or that starts with $q_{S}$).

We have $p^{\prime}\leq p_{S}$ by the definition of $p_{S}$, $p_{S}\leq q_{S}$
by Lemma 5.6 and $q_{S}\leq q^{\prime}$ by the definition of $q_{S}$. If
$p^{\prime}=p_{S}$, then we can apply lemma 5.3 to $C_{l}$ to conclude the
proof. If $q_{S}=q^{\prime}$, then we can apply lemma 5.3 to $C_{r}$ to
conclude the proof. If none of such equalities hold, then
$p^{\prime}<p_{S}\leq q_{S}<q^{\prime}$ holds so $C_{l}$ and $C_{r}$ forms a
pair of interweaved laced $(n-1)$-cups. ∎

We define the rows of $S$ in the $(\alpha,\beta)$-plane and show that each row
is nonempty.

######  Definition 5.8.

Fix an arbitrary 4-cap, $n$-cup free configuration $S$ of size at least
$\binom{n-1}{2}+1$ with $n\geq 3$ and a fixed slope labeing and
$\alpha$-statistic. For any $1\leq i\leq n-1$, define

$R_{i}(S)=\\{p\in S:\beta(p)=i\\}$

which is the $i$’th row of the $(\alpha,\beta)$-plane of $S$ from the bottom.
Note that $R_{n-1}(S)=R(S)$ in particular by definition.

######  Lemma 5.9.

Under the assumption of Definition 5.8, each row $R_{i}(S)$ is nonempty for
all $1\leq i\leq n-1$.

###### Proof.

Define the set $R_{\geq i}(S)=\\{p\in S:\beta(p)\geq i\\}$ for all $1\leq
i\leq n-1$. By Theorem 2.6, there is at least one $(n-1)$-cup $C$ in $S$, so
that the right endpoint of $C$ is contained in $R_{\geq i}(S)$ for all $i$.
Therefore, the minimum (leftmost) point $x_{i}$ of $R_{\geq i}(S)$ exists for
all $i$.

We show that $x_{i}<x_{i+1}$ for all $1\leq i<n-1$. As $x_{i+1}$ is in
$R_{\geq(i+1)}(S)$, we can take a $(i+1)$-cup $Cx_{i+1}$ that ends with
$x_{i+1}$. Let $y$ be the ending point of the $i$-cup $C$. Then $y\in R_{\geq
i}(S)$ by definition and also $y<x_{i+1}$ because $Cx_{i+1}$ forms a cup. This
implies that $x_{i}=\min R_{\geq i}(S)\leq y<x_{i+1}$.

Because $S$ is $n$-cup free, the equality $R_{n-1}(S)=R_{\geq(n-1)}(S)$ holds
and the set is nonempty. For all $1\leq i<n-1$, the set
$R_{i}(S)=R_{\geq(i+1)}(S)\setminus R_{\geq i}(S)$ contains $x_{i}$ because
$x_{i}<x_{i+1}$. This concludes the proof. ∎

Now we are ready to prove the existence of a pair of interweaved laced
$(n-1)$-cups by induction.

######  Theorem 5.10.

For any $n\geq 3$, any 4-cap, $n$-cup free configuration of size
$\binom{n-1}{2}+2$ contains a pair of interweaved laced $(n-1)$-cups.

###### Proof.

We proceed by induction. The base case $n=3$ can be checked as the following.
For any configuration of size $\binom{2}{2}+2=3$, if the points are $x,y,z$ in
the increasing order, then $xy$ and $yz$ forms a pair of interweaved laced
$2$-cups by definition.

Now we show the inductive step. Fix an arbitrary $n\geq 4$ and the following
inductive hypothesis ($\ast$).

  * ($\ast$)

Any 4-cap, $(n-1)$-cup free configuration of size $\binom{n-2}{2}+2$ contains
a pair of interweaved laced $(n-2)$-cups.

Fix an arbitrary 4-cap, $n$-cup free configuration $S$ of size
$\binom{n-1}{2}+2$. Our goal now is to show that $S$ contains a pair of
interweaved laced $(n-1)$-cups.

By Lemma 5.7, we are already done if $p_{S}$ is an endpoint of a $(n-2)$-cup
and $q_{S}$ is the starting point of an $(n-2)$-cup at the same time. It
remains for us to show the case where either $p_{S}$ is not the endpoint of a
$(n-2)$-cup, or $q_{S}$ is not the starting point of an $(n-2)$-cup. Without
loss of generality (e.g. Remark 5.5), we can assume that $q_{S}$ is not the
starting point of an $(n-2)$-cup by reflecting $S$ in the other case. Now fix
a specified slope labeling and $\alpha$-statistic of $S$ to use (Theorem 3.2).

$\alpha(p)$$\beta(p)$112233445566$x_{1}$$x_{2}$$x_{3}$$x_{4}$$x_{5}$$x_{6}$
Figure 8. A hypothetical $(\alpha,\beta)$-plane of a 4-cap, $n$-cup free set
$S$ of size $\binom{n-1}{2}+2$ with $n=7$. There are $n-3=4$ ‘holes’ not in
$S$ drawn as white points. The set $\Delta$ of size $n-2=5$ is marked with
circles.

We define the set $S^{\prime}$ on which we will apply the inductive hypothesis
($\ast$) as the following. For each $1\leq i\leq n-1$, define $x_{i}$ as the
leftmost point of the $i$’th row $R_{i}(S)$ of the $(\alpha,\beta)$-plane
(Definition 5.8). By Lemma 5.9, each $x_{i}$ is well-defined. Define the set
$\Delta=\\{x_{1},x_{2},\cdots,x_{n-2}\\}$ of size $n-2$. Note that the point
$x_{n-1}$ is excluded from $\Delta$ by definition, and that $x_{n-1}=q_{S}$ by
Definition 5.4. Define the set $S^{\prime}$ of size $\binom{n-2}{2}+2$ as
$S^{\prime}=S\setminus\Delta$ (see Figure 8). We will show later that
$S^{\prime}$ is $(n-1)$-cup free, so that we can apply the induction
hypothesis ($\ast$) to $S^{\prime}$.

We assumed without loss of generality that $q_{S}$ is not the starting point
of an $(n-2)$-cup. Using it, we show the following consequences.

  * ($\ast\ast$)

Let $x$ be the starting point of an arbitrary $(n-2)$-cup $C$ in $S^{\prime}$
and let $i=\beta(x)$. Then the following hold.

    1. (1)

$x<q_{S}$

    2. (2)

$x\not\in R_{n-1}(S)$ and $i\leq n-2$

    3. (3)

$x_{i}<x$ and the edge $x_{i}x$ is labeled 1, so $x_{i}C$ is an $(n-1)$-cup in
$S$

    4. (4)

$\alpha(x_{i})=1$ and $\alpha(x)=2$

First we show $x<q_{S}$, the first item of ($\ast\ast$). Assume otherwise that
$x\geq q_{S}$. Then the case $x=q_{S}$ directly contradicts our assumption, so
we should have $x>q_{S}$. If the edge $q_{S}x$ is labeled 1, then $q_{S}C$ is
an $(n-1)$-cup so it also contradicts our assumption. So $q_{S}x$ should be
labeled 2. But in this case, as $q_{S}$ is the ending point of some
$(n-1)$-cup $D$ by definition, $Dx$ is an $n$-cup which contradicts that $S$
is $n$-cup free. This concludes the proof of $x<q_{S}$ by contradiction.

As $q_{S}$ is the minimum value of $R(S)=R_{n-1}(S)$, we also get $x\not\in
R_{n-1}(S)$ and $i=\beta(x)\leq n-2$ (the second item of ($\ast\ast$)).
Therefore, $x_{i}\in\Delta$ and as $x_{i}$ is minimal in the row $R_{i}(S)$
that also contains $x$, we have $x_{i}<x$ and the edge $x_{i}x$ is labeled 1.
Consequently, the $(n-1)$-cup $C$ extends to left with $x_{i}$ (the third item
of ($\ast\ast$)).

If $\alpha(x_{i})>1$, then we can extend the $(n-1)$-cup $x_{i}C$ to left in
$S$, so it contradicts that $S$ is $n$-cup free. So $\alpha(x_{i})=1$. Next,
we show that $\alpha(x)=2$. Because the edge $x_{i}p$ is labeled 1, we have
$\alpha(p)\geq 2$. If $\alpha(p)>2$, then we have a 3-cup $D$ that ends with
$p_{\epsilon}$ and an edge with label 1. Now the cup $D$ and $C_{\epsilon}$
meets at $p_{\epsilon}$, and they form a cup because $D$ ends with an edge
with label 1. The cup is of size $|D|+|C_{\epsilon}|-1=n$ and we reach
contradiction. So the equality $\alpha(p_{\epsilon})=2$ holds (the fourth item
of ($\ast\ast$)). This concludes the proof of ($\ast\ast$).

We now show that $S^{\prime}$ is $(n-1)$-cup free. Assume otherwise that
$S^{\prime}$ contains an $(n-1)$-cup $C_{0}$ from some point $x$ to $y$. Let
$i=\beta(x)$. Then since $x$ is also the starting point of some $(n-2)$-cup in
$S^{\prime}$, the property ($\ast\ast$) implies that the edge $x_{i}x$ has
label 1. Now the $(n-1)$-cup $C_{0}$ in $S^{\prime}$ extends to left with
$x_{i}$ in $S$, contradicting that $S$ is $n$-cup free.

As $S^{\prime}$ is $(n-1)$-cup free, we can apply the inductive hypothesis
($\ast$). Doing so, we find a pair $(C_{1},C_{2})$ of interweaved laced
$(n-2)$-cups in $S^{\prime}$, each from $p_{1}$ to $r_{1}$ and $p_{2}$ to
$r_{2}$ so that $p_{1}<p_{2}\leq r_{1}<r_{2}$. Define $i_{1}=\beta(p_{1})$ and
$i_{2}=\beta(p_{2})$. By the property ($\ast\ast$) applied to $C_{1}$ and
$C_{2}$ respectively, we have the following.

  * •

$p_{1},p_{2}<q_{S}$

  * •

$i_{1},i_{2}<n-1$

  * •

$x_{i_{1}}p_{1}$ and $x_{i_{2}}p_{2}$ are edges with label 1

  * •

$x_{i_{1}}C_{1}$ are $x_{i_{2}}C_{2}$ are $(n-1)$-cups in $S$

  * •

$\alpha(x_{i_{1}})=\alpha(x_{i_{2}})=1$ and $\alpha(p_{1})=\alpha(p_{2})=2$

We show that the pair $(x_{i_{1}}C_{1},x_{i_{2}}C_{2})$ of $(n-1)$-cups is
interweaved and laced. This completes the inductive step and the whole proof.

First, we show that the pair is interweaved. That is, whether
$x_{i_{1}}<x_{i_{2}}\leq r_{1}<r_{2}$ is true. By the assumptions
$x_{i_{2}}<p_{2}\leq r_{1}<r_{2}$, it only remains for us to show that
$x_{i_{1}}<x_{i_{2}}$. Applying Corollary 4.3 to $p_{1}<p_{2}$ and
$\alpha(p_{1})=\alpha(p_{2})=2$, we have $\beta(p_{1})<\beta(p_{2})$ which is
exactly $i_{1}<i_{2}$ by definition. Applying Corollary 4.3 again to
$\beta(x_{i_{1}})=i_{1}<i_{2}=\beta(x_{i_{2}})$ and
$\alpha(x_{i_{1}})=\alpha(x_{i_{2}})=1$, we have $x_{i_{1}}<x_{i_{2}}$. This
completes the proof that the pair $(x_{i_{1}}C_{1},x_{i_{2}}C_{2})$ is
interweaved.

Now we show that each cup in the pair $(x_{i_{1}}C_{1},x_{i_{2}}C_{2})$ is
laced. Let $\epsilon\in\\{1,2\\}$ be any of the index 1 or 2. We extend the
laced $(n-2)$-cup $C_{\epsilon}$ in $S^{\prime}$ to show that
$x_{i_{\epsilon}}C_{\epsilon}$ in $S$ is also laced. Because $C_{\epsilon}$
from $p_{\epsilon}$ to $r_{\epsilon}$ is laced in $S^{\prime}$, there are cups
$C_{p_{\epsilon}}$ and $C_{r_{\epsilon}}$ in $S^{\prime}$ that ends with
$p_{\epsilon}$ and starts with $r_{\epsilon}$ respectively, so that
$|C_{p_{\epsilon}}|+|C_{r_{\epsilon}}|=n-2$.

Say that $C_{p_{\epsilon}}$ starts with a point $z$ in $S^{\prime}$. Then
$z\leq p_{\epsilon}<q_{S}$ so $\beta(z)<n-1$ by the definition of $q_{S}$.
Consequently, we have $\alpha(z)\geq 2$ as $\beta(z)<n-1$ and $z$ is not in
$\Delta$. So $z$ is the endpoint of an edge $yz$ of label 1 in $S$. We can
extend $C_{p_{\epsilon}}$ to left to a cup $yC_{p_{\epsilon}}$ of size
$|C_{p_{\epsilon}}|+1$ in $S$, and the cup $yC_{p_{\epsilon}}$ ends with
$p_{\epsilon}$. This implies that
$|C_{p_{\epsilon}}|+1\leq\beta(p_{\epsilon})=i_{\epsilon}=\beta(x_{i_{\epsilon}})$.
So in particular,
$\beta(x_{i_{\epsilon}})+|C_{r_{i}}|\geq|C_{p_{\epsilon}}|+|C_{r}|+1=n-1$ and
$x_{i_{\epsilon}}C_{\epsilon}$ is a laced $(n-1)$-cup for any of $\epsilon=$ 1
or 2. This concludes the proof.

∎

We obtain the main theorem (Theorem 2.7) immediately as the following.

###### Proof of Theorem 2.7.

Combine Theorem 5.10 with Lemma 5.2. ∎

We end with a conjecture that generalizes Theorem 5.10.

######  Conjecture 5.

For any $n\geq 3$ and $1\leq k\leq n$, any 4-cap, $n$-cup free configuration
of size $\binom{n-1}{2}+k$ contains $k$ mutually interweaved laced
$(n-1)$-cups.

Theorem 5.10 is a special case $k=2$ of this conjecture. We can also prove the
case $k=1$ with a similar induction argument with the same
$S^{\prime}=S\setminus\Delta$. The case $k=n$ is an immediate consequence of
the discussion at the end of Section 4. The proof of Theorem 5.10 fails to
extend because it exploits the mirror symmetry and essentially applies the
inductive hypothesis twice to force the ’rightmost’ laced $(n-1)$-cup starting
with $p_{S}$ and the ’leftmost’ laced $(n-1)$-cup ending with $q_{S}$. This
special case is then covered by Lemma 5.3.

## Acknowledgement

The author is indebted to David Speyer for many illuminating discussions and
his help in making the presentation much more organized and clear. The author
thanks to Andreas Holmsen for directing the author to the work of Moshkovitz
and Shapira [10] that inspired the notion of $(\alpha,\beta)$-plane. The
author also thanks to Martin Balko and Pavel Valtr for their work [1] that
inspired the main Theorem 1.6 and their thoughtful feedback on the early
version of the draft.

## References

  * [1] M. Balko and P. Valtr.  A sat attack on the erdős–szekeres conjecture.  European Journal of Combinatorics, 66:13–23, 2017.
  * [2] F. R. Chung and R. L. Graham.  Forced convex n-gons in the plane.  Discrete & Computational Geometry, 19(3):367–371, 1998.
  * [3] P. Erdös and G. Szekeres.  A combinatorial problem in geometry.  Compositio mathematica, 2:463–470, 1935.
  * [4] P. Erdös and G. Szekeres.  On some extremum problems in elementary geometry.  In Annales Univ. Sci. Budapest, pages 3–4, 1960.
  * [5] P. Erdos, Z. Tuza, and P. Valtr.  Ramsey-remainder.  European Journal of Combinatorics, 17(6):519–532, 1996.
  * [6] J. Fox, J. Pach, B. Sudakov, and A. Suk.  Erdős–szekeres-type theorems for monotone paths and convex bodies.  Proceedings of the London Mathematical Society, 105(5):953–982, 2012.
  * [7] A. F. Holmsen, H. N. Mojarrad, J. Pach, and G. Tardos.  Two extensions of the erdős–szekeres problem.  Journal of the European Mathematical Society, 22(12):3981–3995, 2020.
  * [8] D. Kleitman and L. Pachter.  Finding convex sets among points in the plane.  Discrete & Computational Geometry, 19(3):405–410, 1998.
  * [9] H. N. Mojarrad and G. Vlachos.  An improved upper bound for the erdős–szekeres conjecture.  Discrete & Computational Geometry, 56(1):165–180, 2016.
  * [10] G. Moshkovitz and A. Shapira.  Ramsey theory, integer partitions and a new proof of the erdős–szekeres theorem.  Advances in Mathematics, 262:1107–1129, 2014.
  * [11] S. Norin and Y. Yuditsky.  Erdős–szekeres without induction.  Discrete & Computational Geometry, 55(4):963–971, 2016.
  * [12] A. Suk.  On the erdős-szekeres convex polygon problem.  Journal of the American Mathematical Society, 30(4):1047–1053, 2017\.
  * [13] G. Szekeres and L. Peters.  Computer solution to the 17-point erdős-szekeres problem.  The ANZIAM Journal, 48(2):151–164, 2006.
  * [14] G. Tóth and P. Valtr.  Note on the erdos-szekeres theorem.  Discrete & Computational Geometry, 19(3):457–459, 1998.
  * [15] G. Tóth and P. Valtr.  The erdos-szekeres theorem: upper bounds and related results.  Combinatorial and computational geometry, 19:557–568, 2005.