# Covering grids with multiplicity

Anurag Bishnoi Delft Institute of Applied Mathematics, Technische Universiteit
Delft, 2628 CD Delft, Netherlands. E-mail<EMAIL_ADDRESS>Simona
Boyadzhiyska School of Mathematics, University of Birmingham, Edgbaston,
Birmingham, B15 2TT, UK. This research was done when the author was affiliated
with the Institut für Mathematik, Freie Universität Berlin, 14195 Berlin,
Germany. E-mail<EMAIL_ADDRESS>Research supported by the
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under
Germany’s Excellence Strategy – The Berlin Mathematics Research Center MATH+
(EXC-2046/1, project ID: 390685689, BMS Stipend) and Graduiertenkolleg “Facets
of Complexity” (GRK 2434). Shagnik Das Department of Mathematics, National
Taiwan University, Taiwan. E-mail<EMAIL_ADDRESS>Research supported by
Taiwan NSTC grant 111-2115-M-002-009-MY2. Yvonne den Bakker Delft Institute of
Applied Mathematics, Technische Universiteit Delft, 2628 CD Delft,
Netherlands. E-mail<EMAIL_ADDRESS>.

###### Abstract

Given a finite grid in $\mathbb{R}^{2}$, how many lines are needed to cover
all but one point at least $k$ times? Problems of this nature have been
studied for decades, with a general lower bound having been established by
Ball and Serra. We solve this problem for various types of grids, in
particular showing the tightness of the Ball–Serra bound when one side is much
larger than the other. In other cases, we prove new lower bounds that improve
upon Ball–Serra and provide an asymptotic answer for almost all grids. For the
standard grid $\\{0,\ldots,n-1\\}\times\\{0,\ldots,n-1\\}$, we prove
nontrivial upper and lower bounds on the number of lines needed. To prove our
results, we combine linear programming duality with some combinatorial
arguments.

##  1 Introduction

A celebrated result of Alon and Füredi [3] in combinatorial geometry states
that any multiset of hyperplanes that covers all but one point of a
$d$-dimensional finite grid $S_{1}\times\cdots\times
S_{d}\subseteq\mathbb{F}^{d}$ over an arbitrary field $\mathbb{F}$ must have
size at least $\sum_{i=1}^{d}(|S_{i}|-1)$. This lower bound is easily seen to
be tight by taking all hyperplanes of the form $x_{i}-a=0$ for $1\leq i\leq d$
and $a\in S_{i}\setminus\\{b_{i}\\}$, where $(b_{1},\dots,b_{n})$ is the point
that is uncovered. This is a significant theorem for a few different reasons;
not only did the proof of Alon and Füredi play an important role in the
development of the polynomial method [2, 16, 7], but this result and its
generalisations have also seen several applications in a wide variety of
mathematical disciplines [18, 9, 7, 1, 10].

One such generalisation that has been studied by several researchers is the
multiplicity version of the problem, where the points of the grid should be
covered multiple times. We introduce some notation to define this problem
formally.

######  Definition 1.

Given finite subsets $S_{1},S_{2},\ldots,S_{d}$ of some field $\mathbb{F}$, we
write $\Gamma=\Gamma(S_{1},S_{2},\ldots,S_{d})$ for the grid $S_{1}\times
S_{2}\times\ldots\times S_{d}\subseteq\mathbb{F}^{d}$. Note that by
translation we may, and will, assume $\vec{0}\in\Gamma$. We call a point in
$\Gamma$ a _boundary point_ if any of its coordinates is equal to $0$, and an
_interior point_ otherwise.

For a given integer $k\geq 1$, we call a multiset $\mathcal{H}$ of hyperplanes
in $\mathbb{F}^{d}$ a _$k$ -cover of $\Gamma$_ if every nonzero point of
$\Gamma$ is contained in at least $k$ of the hyperplanes, while $\vec{0}$ is
not covered at all. We denote by $\operatorname{cov}_{k}(\Gamma;\mathbb{F})$
the minimum cardinality of a $k$-cover of $\Gamma$ in $\mathbb{F}^{d}$. In the
case $\mathbb{F}=\mathbb{R}$, we shall omit the field from the notation and
simply write $\operatorname{cov}_{k}(\Gamma)$.

In this notation, the Alon–Füredi Theorem establishes that
$\operatorname{cov}_{1}(\Gamma,\mathbb{F})=\sum_{i=1}^{d}\left(\left|S_{i}\right|-1\right)$
for any grid $\Gamma$ over any field $\mathbb{F}$. The multiplicity extension
asks for the value of $\operatorname{cov}_{k}(\Gamma;\mathbb{F})$ for
multiplicities $k\geq 2$, and we can start with a few trivial observations.
First, if we remove any hyperplane from a $k$-cover, what we are left with is
still a $(k-1)$-cover, and so
$\operatorname{cov}_{k}(\Gamma;\mathbb{F})\geq\operatorname{cov}_{k-1}(\Gamma;\mathbb{F})+1$;
that is, this extremal function is strictly increasing in $k$. In the other
direction, since the union of a $k$-cover and an $\ell$-cover yields a
$(k+\ell)$-cover, we have
$\operatorname{cov}_{k+\ell}(\Gamma;\mathbb{F})\leq\operatorname{cov}_{k}(\Gamma;\mathbb{F})+\operatorname{cov}_{\ell}(\Gamma;\mathbb{F})$,
and so the function is subadditive in $k$. Applying these recursive
inequalities repeatedly until we reach the $k=1$ case of Alon–Füredi, we have

$\sum_{i=1}^{d}\left(\left|S_{i}\right|-1\right)+k-1=\operatorname{cov}_{1}(\Gamma;\mathbb{F})+k-1\leq\operatorname{cov}_{k}(\Gamma;\mathbb{F})\leq
k\operatorname{cov}_{1}(\Gamma;\mathbb{F})=k\sum_{i=1}^{d}\left(\left|S_{i}\right|-1\right).$
(1)

The goal, then, is to narrow the considerable gap between these bounds, and
there has been much previous research on some specific cases. Predating the
work of Alon and Füredi [3], the study of affine blocking sets in finite
geometry corresponds to setting $\mathbb{F}=\mathbb{F}_{q}$ for some prime
power $q$ and taking $\Gamma=\mathbb{F}_{q}^{d}$. For this grid, the classic
paper of Jamison [17] uses the polynomial method to prove
$\operatorname{cov}_{1}(\Gamma;\mathbb{F}_{q})=d(q-1)$. Bruen [12] later used
the polynomial method with multiplicities to provide lower bounds for the
multiplicity version, showing
$\operatorname{cov}_{k}(\Gamma,\mathbb{F}_{q})\geq(d+k-1)(q-1)$. This is an
improvement upon (1), but is generally not tight [22, 19]. In [8], the first
three authors together with Tamás Mészáros obtained new bounds in the case
$q=2$ by exploiting an equivalence between $k$-covers and linear binary codes
of minimum distance $k$.

Recent work of Clifton and Huang [13] considered this problem over
$\mathbb{R}$, where the grid is the hypercube $\Gamma=\\{0,1\\}^{d}$. For
fixed dimension $d$ and growing multiplicity $k$, they used linear programming
to determine $\operatorname{cov}_{k}(\Gamma)$ asymptotically. On the other
hand, when the dimension $d$ is large with respect to the multiplicity $k$,
they applied the polynomial method to provide general lower bounds that are
tight for $k=2$ and $k=3$. However, they conjectured that their lower bound of
$d+k+1$ is not tight for $k\geq 4$, and that the true value of
$\operatorname{cov}_{k}(\Gamma)$ is $d+\binom{k}{2}$ for all fixed $k$ and
large enough $d$ (see [13, Conjecture 4.1]). A subsequent paper of Sauermann
and Wigderson [21] determined the best bound one can obtain with the
polynomial method, where one seeks the minimum possible degree of a polynomial
that does not vanish at the origin but has zeroes of multiplicity $k$ at all
other points in the grid. While their result improves the Clifton–Huang lower
bound to $\operatorname{cov}_{k}(\Gamma)\geq d+2k-3$, it still falls short of
the conjectured value of $\operatorname{cov}_{k}(\Gamma)$ in this case,
suggesting a strong separation between the algebraic and geometric problems.

Apart from these special cases, Ball and Serra [5, Theorem 5.3] applied the
polynomial method to obtain a lower bound valid for any grid
$\Gamma=\Gamma(S_{1},S_{2},\ldots,S_{d})$ over any field $\mathbb{F}$:

$\operatorname{cov}_{k}(\Gamma;\mathbb{F})\geq\sum_{i=1}^{d}(|S_{i}|-1)+(k-1)\max\limits_{1\leq
i\leq d}(|S_{i}|-1).$ (2)

This extends the bound of Bruen, and is a sizeable improvement on the lower
bound of (1), but remains far removed from the upper bound. Indeed, in the
symmetric case when $|S_{i}|=n$ for all $i\in[d]$, we have
$(d+k-1)(n-1)\leq\operatorname{cov}_{k}(\Gamma;\mathbb{F})\leq kd(n-1)$. It is
thus of great interest to determine whether the Ball–Serra bound can be tight,
and to obtain better bounds when it is not.

In this paper we initiate the systematic study of the covering problem for
two-dimensional finite grids over $\mathbb{R}$. Our first set of results
concerns how the dimensions of the grid affect the tightness of the Ball–Serra
bound. We start by showing that when the grid is much wider than it is tall,
the Ball–Serra bound is sharp.

######  Theorem 1.1.

Let $S_{1},S_{2}\subseteq\mathbb{R}$ satisfy $|S_{1}|=n$, $|S_{2}|=m$, and
$0\in S_{1}\cap S_{2}$, and set
$\Gamma=\Gamma(S_{1},S_{2})\subseteq\mathbb{R}^{2}$. If, for a positive
integer $k$, we have $n\geq(k-1)(m-1)+1$, then

$\operatorname{cov}_{k}(\Gamma)=k(n-1)+(m-1).$

Our next result shows that the lower bound on $n$ from 1.1 cannot be improved
in general. In fact, when $n\leq(k-1)(m-1)$, the Ball–Serra bound can be
improved for almost all $n\times m$ grids. We make the “almost all” precise
with the following definition.

######  Definition 2.

Let $S_{1},S_{2}\subseteq\mathbb{R}$ with $0\in S_{1}\cap S_{2}$, let
$\Gamma=\Gamma(S_{1},S_{2})$, and let $\Delta\geq 0$ be an integer. We call
$\Gamma$ _$\Delta$ -generic_ if any line containing two boundary points
contains at most $\Delta$ interior points. In the case $\Delta=0$, when such
lines avoid all interior points, we simply call $\Gamma$ _generic_.

To see that grids are typically generic, suppose the nonzero points of $S_{1}$
and $S_{2}$ are sampled uniformly and independently from $[-1,1]$. If a line
contains two boundary points and an interior point, then the boundary points
must come from different axes, and so we may assume the points in question are
$(0,b_{1})$, $(a_{1},0)$ and $(a_{2},b_{2})$ for some nonzero $a_{1},a_{2}\in
S_{1}$ and $b_{1},b_{2}\in S_{2}$. For these points to be collinear, we
require $a_{1}(b_{1}-b_{2})=a_{2}b_{1}$, and the probability of such an
equation holding for any choice of $a_{i},b_{j}$ is $0$. We are now ready to
state our next result, which concerns $\operatorname{cov}_{k}(\Gamma)$ in the
special case where $\Gamma$ is a generic grid.

######  Theorem 1.2.

Let $\Gamma=\Gamma(S_{1},S_{2})\subseteq\mathbb{R}^{2}$ be a generic grid with
$|S_{1}|=n$, $|S_{2}|=m$ and $0\in S_{1}\cap S_{2}$. Then

$\operatorname{cov}_{k}(\Gamma)\geq k(n-1)+\frac{k}{n+m-2}(m-1)^{2}.$

Furthermore, if $\Gamma$ is an arbitrary $n\times m$ grid, and if $k$ is
divisible by $\frac{n+m-2}{\gcd(n-1,m-1)}$, then we have

$\operatorname{cov}_{k}(\Gamma)\leq k(n-1)+\frac{k}{n+m-2}(m-1)^{2}.$ (3)

In particular, if $\Gamma$ is generic, we have equality above.

Note that $\frac{k}{n+m-2}(m-1)^{2}$ is strictly larger than $m-1$ precisely
when $n\leq(k-1)(m-1)$, and hence these theorems show the Ball–Serra bound is
tight for generic grids if and only if $n\geq(k-1)(m-1)+1$.

Theorem 1.2 shows that the Ball–Serra bound gets worse as the dimensions of
the grid grow closer. For the majority of our paper, therefore, we focus on
square grids $\Gamma$, where $n=m$. In this case, the Ball–Serra bound gives
$\operatorname{cov}_{k}(\Gamma)\geq(k+1)(n-1)$. Our next theorem gives a stark
improvement for general square grids.

######  Theorem 1.3.

Let $\Gamma=\Gamma(S_{1},S_{2})\subset\mathbb{R}^{2}$ be a grid with
$|S_{1}|=|S_{2}|=n$ and $0\in S_{1}\cap S_{2}$. Then, for any integer $k\geq
2$, we have:

  1. (a)

$\operatorname{cov}_{k}(\Gamma)\leq\left\lceil\frac{3}{2}k\right\rceil(n-1)$.

  2. (b)

$\operatorname{cov}_{k}(\Gamma)\geq(10-4\sqrt{5}+o(1))k(n-1)$, where the
asymptotics are for $n\to\infty$.

  3. (c)

if $\Gamma$ is $\Delta$-generic for some $\Delta\geq 0$, then
$\operatorname{cov}_{k}(\Gamma)\geq\left[2-\frac{n-1}{2(n-1)-\Delta}\right]k(n-1)$.

Note that part (a) improves the trivial upper bound from (1), while, since
$10-4\sqrt{5}\approx 1.0557$, part (b) gives a constant factor improvement
over the Ball–Serra bound in (2), showing that it is never tight for large
square grids. Moreover, as previously discussed, almost all grids are generic,
and substituting $\Delta=0$ into part (c) gives a lower bound that matches the
upper bound of part (a) exactly when $k$ is even and asymptotically when $k$
is odd and large. In fact, part (c) gives an asymptotically tight bound for
all $o(n)$-generic grids.

However, the most natural grid to consider is the _standard $n\times n$ grid_,
given by $S_{1}=S_{2}=\\{0,1,2,\dots,n-1\\}$, and we denote this by
$\Gamma_{n}=\Gamma(S_{1},S_{2})$. By considering the diagonal $x+y=n-1$, we
see that $\Gamma_{n}$ is not $\Delta$-generic for any $\Delta<n-2$, and so
Theorem 1.3(c) is worse than the Ball–Serra bound when $n>k$. By tailoring our
methods to this specific grid, we obtain the following improvements on the
general bounds.

######  Theorem 1.4.

Let $n,k\geq 2$ be integers, let $S=\\{0,1,2,\dots,n-1\\}$ and let
$\Gamma_{n}=\Gamma(S,S)$ be the standard $n\times n$ grid. Then, as
$n,k\to\infty$, we have

$\displaystyle(2-e^{-1/2}+o(1))k(n-1)\leq\operatorname{cov}_{k}(\Gamma_{n})\leq(\sqrt{2}+o(1))k(n-1).$
(4)

Note that $2-e^{-1/2}\approx 1.3935$, while $\sqrt{2}\approx 1.4142$, so there
is still a gap between the best lower and upper bounds we obtain for standard
grids. To obtain sharper bounds, it can help to restrict the class of
$k$-covers we consider. As we will see in the proof of the upper bound in 1.4,
our construction uses only three types of lines: horizontal, vertical, and
lines of slope $-1$. A subsequent computer search verified that for small
values of $n$ and $k$, we can always find an optimal $k$-cover using only
these three kinds of lines. In our final result, we provide a matching lower
bound for these restricted $k$-covers, suggesting the upper bound of (4) may
be correct in the unrestricted case as well.

######  Theorem 1.5.

As $n\to\infty$, the smallest $k$-cover of the standard grid $\Gamma_{n}$ that
only contains lines of slope $0,\infty$, or $-1$ has size at least
$\left(\sqrt{2}+o(1)\right)k(n-1)$.

When proving these results, we shall establish the upper bounds by means of
explicit constructions of $k$-covers. The lower bounds, meanwhile, will follow
by applying duality to a linear programming relaxation of this problem, and we
shall set up this framework in Section 2. Having described our methodology, we
will prove Theorems 1.1 and 1.2 in Section 3. We then shift our focus to
square grids, proving Theorems 1.3, 1.4, and 1.5 in Section 4. Finally, we
provide some concluding remarks and open problems in Section 5.

##  2 The linear programming framework

In this section we introduce the linear programming method that will be used
to prove our lower bounds. The use of linear programming in extremal
combinatorics is well-established and has led to many results (see, for
example, [15]), including the Clifton–Huang [13] lower bound on
$\operatorname{cov}_{k}(\Gamma)$ for $\Gamma=\\{0,1\\}^{d}$ in the case when
$d$ is fixed and $k$ tends to infinity. The standard template is as follows:
assume without loss of generality that we are working with a minimization
problem; first, we interpret our extremal problem as an instance of an integer
programming problem. Then, since integer programming is intractable, we
consider the linear programming relaxation, where we allow fractional
solutions. Since an integer solution is in particular a fractional solution,
the value of the linear program gives a lower bound to the original extremal
problem. Crucially, we can then apply duality, and the task of finding lower
bounds translates to finding feasible solutions to the dual linear program. We
refer the reader to [20] for further background on linear programming.

To start with this plan of action, we need to recast the covering problem as
an integer linear program. Given a grid $\Gamma=\Gamma(S_{1},S_{2})$, for some
finite sets $S_{1},S_{2}\subseteq\mathbb{R}$ containing $0$, we wish to
determine $\operatorname{cov}_{k}(\Gamma)$, the minimum number of lines in a
$k$-cover of $\Gamma$. We shall assume $|S_{1}|,|S_{2}|\geq 2$, as the problem
is otherwise trivial.

For every possible line $\ell$ not containing the origin, we introduce a
variable $z(\ell)$ indicating its multiplicity in the $k$-cover. We thus wish
to minimise $\sum_{\ell}z(\ell)$, the size of the cover. In order to ensure
that the solution returned by the integer program is a $k$-cover, we need to
require that each nonzero point of $\Gamma$ be covered at least $k$ times
while the origin be omitted altogether. The latter constraint is easily seen
to be satisfied. Hence, for each $(x,y)\in\Gamma\setminus\\{(0,0)\\}$, we
require that the sum of $z(\ell)$ over all origin-avoiding lines $\ell$
containing $(x,y)$ be at least $k$.

The one catch is that there are infinitely many lines in $\mathbb{R}^{2}$. To
obtain a finite program, we observe that we may restrict our attention to
lines that contain at least two nonzero points in $\Gamma$. Indeed, in any
minimal $k$-cover of $\Gamma$, every line must contain at least one nonzero
point, and if a line contains only one point $(x,y)$, then we can replace it
by a different origin-avoiding line passing through $(x,y)$ and at least one
other point of $\Gamma$. Thus, we need only consider lines from the set
$\mathcal{L}=\mathcal{L}(\Gamma)$ of origin-avoiding lines containing at least
two points of $\Gamma$. Since there are fewer than $|\Gamma|^{2}$ pairs of
nonzero points in $\Gamma$, each of which determines a unique line, it follows
that $\mathcal{L}$ is finite.

In summary, $\operatorname{cov}_{k}(\Gamma)$ is the solution to the following
integer linear program $\mathcal{I}=\mathcal{I}(\Gamma,k)$.

$\displaystyle\text{minimize}\quad\sum\limits_{\ell\in{\mathcal{L}}}z(\ell)$
subject to
$\displaystyle\quad\quad\quad\quad\sum\limits_{\begin{subarray}{c}\ell\in{\mathcal{L}}:\\\
(x,y)\in\ell\end{subarray}}z(\ell)\geq k\quad\text{for all
}(x,y)\in\Gamma\setminus\\{(0,0)\\}$ $\displaystyle\quad\quad\quad\quad
z(\ell)\in\mathbb{Z}_{\geq 0}\quad\text{for all }\ell\in{\mathcal{L}}$

The final constraint, that the variables $z(\ell)$ be integral, renders
solving the program computationally infeasible. Instead, to obtain a
polynomial-time solvable problem, we can relax the variables to be real-
valued. Now that we are no longer constrained to the integers, we can also
divide through by $k$, removing the dependence of the program on this
parameter. We therefore obtain the linear program
${\mathcal{P}}={\mathcal{P}}(\Gamma)$ with the normalised variables $u(\ell)$
for $\ell\in{\mathcal{L}}$.

$\displaystyle\text{minimize}\quad\sum\limits_{\ell\in\mathcal{L}}u(\ell)$ (5)
subject to
$\displaystyle\quad\quad\quad\quad\sum\limits_{\begin{subarray}{c}\ell\in\mathcal{L}:\\\
(x,y)\in\ell\end{subarray}}u(\ell)\geq 1\quad\text{for all
}(x,y)\in\Gamma\setminus\\{(0,0)\\}$ $\displaystyle\quad\quad\quad\quad
u(\ell)\geq 0\quad\text{for all }\ell\in\mathcal{L}$

Let us denote by $\Phi(\Gamma)$ the solution to ${\mathcal{P}}(\Gamma)$. The
following result shows that $\Phi(\Gamma)$ describes the asymptotic behaviour
of $\operatorname{cov}_{k}(\Gamma)$ when $k$ is large with respect to the
dimensions of the grid.

######  Proposition 2.1.

For any grid $\Gamma$ and integer $k\geq 1$ we have

$k\Phi(\Gamma)\leq\operatorname{cov}_{k}(\Gamma)\leq
k\Phi(\Gamma)+|{\mathcal{L}}|.$

###### Proof.

As previously established, $\operatorname{cov}_{k}(\Gamma)$ is the value of
the integer linear program ${\mathcal{I}}(\Gamma,k)$. If we let
$(z(\ell):\ell\in{\mathcal{L}})$ be a solution to the program, then setting
$u(\ell)=\tfrac{1}{k}z(\ell)$ yields a feasible solution to the linear
relaxation ${\mathcal{P}}(\Gamma)$, with value
$\sum_{\ell}u(\ell)=\tfrac{1}{k}\sum_{\ell}z(\ell)=\tfrac{1}{k}\operatorname{cov}_{k}(\Gamma)$.
As $\Phi(\Gamma)$ is the minimum possible value of a feasible solution to
${\mathcal{P}}(\Gamma)$, the first inequality follows.

For the upper bound, let $\left(u^{*}(\ell):\ell\in{\mathcal{L}}\right)$ be an
optimal solution to the linear program ${\mathcal{P}}(\Gamma)$, with value
$\Phi(\Gamma)$. If we then set $z(\ell)=\left\lceil ku^{*}(\ell)\right\rceil$
for all $\ell\in{\mathcal{L}}$, we obtain a feasible solution to
${\mathcal{I}}(\Gamma,k)$. Thus,

$\operatorname{cov}_{k}(\Gamma)\leq\sum_{\ell}z(\ell)=\sum_{\ell}\left\lceil
ku^{*}(\ell)\right\rceil\leq\sum_{\ell}\left(ku^{*}(\ell)+1\right)=k\Phi(\Gamma)+|{\mathcal{L}}|.\qed$

We remark that in practice one often obtains better error bounds; for
instance, the $|{\mathcal{L}}|$ term can be replaced by the size of the
support of the optimal solution $u^{*}$. Furthermore, for an infinite sequence
of multiplicities $k$, we can do away with the error term altogether. Indeed,
since all the coefficients of ${\mathcal{P}}(\Gamma)$ are integral, there is a
rational optimal solution $u^{*}$ (the one returned by the Simplex Algorithm,
for example). If $k$ is divisible by the common divisor of the fractions
$u^{*}(\ell)$, then we can set $z(\ell)=ku^{*}(\ell)$ without needing any
rounding, thereby obtaining a solution to ${\mathcal{I}}(\Gamma,k)$ of value
precisely $k\Phi(\Gamma)$.

Therefore, asymptotically as $k$ tends to infinity, the problem reduces to
determining $\Phi(\Gamma)$. We can provide upper bounds by finding feasible
solutions to ${\mathcal{P}}(\Gamma)$ or, better yet, constructing $k$-covers
of $\Gamma$. To obtain lower bounds, we appeal to the theory of duality. The
dual of ${\mathcal{P}}(\Gamma)$, which we denote by ${\mathcal{D}}(\Gamma)$,
is the following linear program, where we have a variable $w(x,y)$ for each
point $(x,y)\in\Gamma\setminus\\{(0,0)\\}$, which we call the weight of the
point.

$\displaystyle\text{maximize}\quad\sum\limits_{(x,y)\in\Gamma\setminus\\{(0,0)\\}}w(x,y)$
(6) subject to
$\displaystyle\quad\quad\quad\quad\sum\limits_{\begin{subarray}{c}(x,y)\in\Gamma\setminus\\{(0,0)\\}:\\\
(x,y)\in\ell\end{subarray}}w(x,y)\leq 1\quad\text{for all }\ell\in\mathcal{L}$
$\displaystyle\quad\quad\quad\quad w(x,y)\geq 0\quad\text{for all
}(x,y)\in\Gamma\setminus\\{(0,0)\\}$

For convenience, given a set $S\subseteq\Gamma\setminus\\{(0,0)\\}$, we write
$w(S)=\sum_{(x,y)\in S}w(x,y)$ for the weight of $S$. The dual program thus
asks for the maximum possible weight of the grid, provided every line in
${\mathcal{L}}$ has weight at most $1$. By the duality theorem for linear
programming (see [20, Section 6.1]), the programs ${\mathcal{P}}(\Gamma)$ and
${\mathcal{D}}(\Gamma)$ have the same optimal objective value $\Phi(\Gamma)$.
We shall thus prove our lower bounds on $\operatorname{cov}_{k}(\Gamma)$ by
finding suitably large feasible weights on the grid $\Gamma$.

##  3 Wide rectangular grids

In this section we will prove Theorems 1.1 and 1.2, establishing precisely
when the Ball–Serra bound is tight for all grids of given dimensions. Our
first result establishes the value of $\operatorname{cov}_{k}(\Gamma)$ for all
$n\times m$ grids $\Gamma$ whenever $n\geq(k-1)(m-1)+1$.

###### Proof of 1.1.

The Ball–Serra bound (2) provides the requisite lower bound, as substituting
$|S_{1}|=n$ and $|S_{2}|=m$ gives $\operatorname{cov}_{k}(\Gamma)\geq
k(n-1)+m-1$. To prove a matching upper bound, we provide an explicit
construction of a $k$-cover containing this many lines.

Write $S_{2}=\\{0,t_{1},\dots,t_{m-1}\\}$, and let $P_{1}\cup\dots\cup
P_{m-1}$ be an arbitrary partition of $S_{1}\setminus\\{0\\}$ such that
$|P_{i}|\geq k-1$ for all $i\in[m-1]$; such a partition exists since
$n-1\geq(k-1)(m-1)$.

Now, consider the following collection of lines:

  1. (i)

the line $y=t_{i}$ for all $i\in[m-1]$;

  2. (ii)

$k-1$ copies of the line $x=s$ for all $s\in S_{1}\setminus\\{0\\}$;

  3. (iii)

the line connecting $(0,t_{i})$ and $(s,0)$ for every $i\in[m-1]$ and $s\in
P_{i}$.

In total, this collection contains $m-1+(k-1)(n-1)+n-1=k(n-1)+m-1$ lines. It
remains to verify that these lines form a valid $k$-cover of $\Gamma$. Note
first that no line in this collection passes through the origin $(0,0)$.

Any interior point of $\Gamma$ is covered $k$ times by the lines in (i) and
(ii), leaving us to check the boundary points. A point of the form $(s,0)$,
where $s\in S_{1}\setminus\\{0\\}$, is covered $k-1$ times by the lines in
(ii) and once by the lines in (iii). Finally, a point $(0,s)$ for $s\in
S_{2}\setminus\\{0\\}$ is covered once by the lines in (i) and at least $k-1$
times by the lines in (iii) since each $P_{i}$ has size at least $k-1$. Hence,
every nonzero point of $\Gamma$ is covered at least $k$ times, as required. ∎

We remark that the above construction can be generalised to higher dimensions
to show that, for any $n_{1}\times\dots\times n_{d}$ grid
$\Gamma(S_{1},\dots,S_{d})$ containing the origin, if $n_{1}\geq
n_{2}\geq\dots\geq n_{d}$ and
$n_{1}\geq\operatorname{cov}_{k-1}(\Gamma(S_{2},\dots,S_{d}))+1$, then the
Ball–Serra bound is tight for
$\operatorname{cov}_{k}(\Gamma(S_{1},\dots,S_{d}))$. Indeed, write
$S_{1}=\\{0,s_{1},\dots,s_{n_{1}-1}\\}$ and let
${\mathcal{H}}=\\{H_{1},\dots,H_{n_{1}-1}\\}$ be any collection of $n_{1}-1$
hyperplanes in $\mathbb{R}^{d-1}$ containing a $(k-1)$-cover of
$\Gamma(S_{2},\ldots,S_{d})$. We then form a $k$-cover of
$\Gamma(S_{1},S_{2},\ldots,S_{d})$ consisting of the following hyperplanes in
$\mathbb{R}^{d}$:

  * (i)

one copy of the hyperplane $x_{i}=t$ for all $i\in\\{2,\dots,d\\}$ and $t\in
S_{i}\setminus\\{0\\}$;

  * (ii)

$k-1$ copies of the hyperplane $x_{1}=s$ for all $s\in S_{1}\setminus\\{0\\}$;

  * (iii)

the hyperplane spanned by $\\{0\\}\times H_{i}$ and $(s_{i},0,\dots,0)$ for
all $i\in[n_{1}-1]$.

It is not difficult to check that this is indeed a $k$-cover of
$\Gamma(S_{1},\dots,S_{d})$, and it consists of
$\sum_{i=1}^{d}n_{i}+(k-1)n_{1}$ hyperplanes, which matches the Ball–Serra
lower bound (2). However, it is not clear how good the lower bound on $n_{1}$
is; that is, how large $n_{1}$ needs to be with respect to the other
dimensions $n_{i}$ in order to ensure that the Ball–Serra bound is tight.

In our next result, we show that the bound on $n_{1}$ in Theorem 1.1 is best
possible, since for generic grids that are slightly less wide, the Ball–Serra
bound is no longer tight. In fact, we a give a general lower bound for
$\operatorname{cov}_{k}(\Gamma)$ when $\Gamma$ is a generic $n\times m$ grid,
and prove that this bound is tight for infinitely many choices of $k$. While
we will not pursue this question further for higher dimensions in this paper,
we remark that it was shown in [14] that for the grid
$\\{0,\dots,n_{1}-1\\}\times\\{0,\dots,n_{2}-1\\}\times\\{0,\dots,n_{3}-1\\}$
with $n_{1}\geq n_{2}\geq n_{3}$, the Ball–Serra bound is already tight when
$n_{1}\geq(k-1)(n_{2}-1)+1$, which is an improvement on the bound given by the
above construction.

###### Proof of Theorem 1.2.

We wish to show that if $\Gamma=\Gamma(S_{1},S_{2})$ is a generic grid, where
$S_{1},S_{2}\subseteq\mathbb{R}$ satisfy $0\in S_{1}\cap S_{2}$ and
$|S_{1}|=n\geq m=|S_{2}|$, then we have $\operatorname{cov}_{k}(\Gamma)\geq
k(n-1)+\frac{k}{n+m-2}(m-1)^{2}$. Appealing to the linear programming
framework developed in Section 2, it suffices to show
$\Phi(\Gamma)\geq(n-1)+\frac{(m-1)^{2}}{n+m-2}$, which can be done by defining
a weighting on the nonzero points of $\Gamma$ with this total weight in which
every line in ${\mathcal{L}}$ has weight at most $1$.

To that end, define the weighting $w:\Gamma\setminus\\{(0,0)\\}\to\mathbb{R}$
by

$w((x,y))=\begin{cases}\frac{n-1}{n+m-2}&\textrm{if }y=0;\\\
\frac{m-1}{n+m-2}&\textrm{if }x=0;\\\
\frac{1}{n+m-2}&\textrm{otherwise}.\end{cases}$

We start by computing the total weight of the grid:

$\displaystyle w\left(\Gamma\setminus\\{(0,0)\\}\right)$
$\displaystyle=(n-1)\frac{n-1}{n+m-2}+(m-1)\frac{m-1}{n+m-2}+(n-1)(m-1)\frac{1}{n+m-2}$
$\displaystyle=(n-1)\frac{n-1+m-1}{n+m-2}+\frac{(m-1)^{2}}{n+m-2}$
$\displaystyle=n-1+\frac{(m-1)^{2}}{n+m-2},$

and so, provided this weighting is feasible, it gives the desired lower bound.

To establish its feasibility, let us consider a line
$\ell\in{\mathcal{L}}(\Gamma)$. First suppose $\ell$ contains two boundary
points, say $(x,0)$ and $(0,y)$. Since $\Gamma$ is generic, $\ell$ cannot
contain any other points, and hence
$w(\ell)=w((x,0))+w((0,y))=\frac{n-1}{n+m-2}+\frac{m-1}{n+m-2}=1$. Next,
suppose $\ell$ is a horizontal line of the form $y=s$ for some $s\in
S_{2}\setminus\\{0\\}$. The line $\ell$ then contains one point on the
$y$-axis and $n-1$ interior points, and thus
$w(\ell)=\frac{m-1}{n+m-1}+(n-1)\frac{1}{n+m-2}=1$. Finally, any other line
$\ell$ can contain at most one boundary point and at most $m-1$ interior
points $(x,y)$, one for each choice of $y\in S_{2}\setminus\\{0\\}$. For such
lines, we therefore have
$w(\ell)\leq\frac{n-1}{n+m-2}+(m-1)\frac{1}{n+m-2}=1$.

Hence, the weighting $w$ is indeed feasible for the dual linear program
${\mathcal{D}}(\Gamma)$, and has total weight $n-1+\frac{(m-1)^{2}}{n+m-2}$,
which proves $\operatorname{cov}_{k}(\Gamma)\geq
k(n-1)+\frac{k}{n+m-2}(m-1)^{2}$.

Now, given an arbitrary $n\times m$ grid $\Gamma=\Gamma(S_{1},S_{2})$, we
provide a construction of a $k$-cover of $\Gamma$ that matches the bound
proven above for an infinite sequence of multiplicities $k$, thereby
determining $\operatorname{cov}_{k}(\Gamma)$ for generic grids $\Gamma$ and
such multiplicities $k$.

Defining $a=\frac{n-1}{\gcd(n-1,m-1)}$ and $b=\frac{m-1}{\gcd(n-1,m-1)}$, we
are given that $k$ is divisible by $a+b$. We further define
$d_{1}=\frac{bk}{a+b}$ and $d_{2}=\frac{ak}{a+b}$, noting that our
divisibility assumption ensures these are integers and that $d_{1}+d_{2}=k$.
Let $B$ be an arbitrary biregular bipartite multigraph with parts
$S_{1}\setminus\\{0\\}$ and $S_{2}\setminus\\{0\\}$ with degrees $d_{1}$ in
the first part and $d_{2}$ in the second. Note that such a multigraph exists,
since $d_{1}(n-1)=d_{2}(m-1)$, and we can assign $d_{1}$ half-edges to each
$s_{1}\in S_{1}\setminus\\{0\\}$ and $d_{2}$ half-edges to each $s_{2}\in
S_{2}\setminus\\{0\\}$, and then take an arbitrary matching between the two
sets of half-edges.

Next, consider the following collection of lines:

  1. (i)

$d_{2}$ copies of the line $x=s_{1}$ for each $s_{1}\in
S_{1}\setminus\\{0\\}$;

  2. (ii)

$d_{1}$ copies of the line $y=s_{2}$ for each $s_{2}\in
S_{2}\setminus\\{0\\}$;

  3. (iii)

for each $\\{s_{1},s_{2}\\}\in E(B)$, a copy of the line connecting
$(s_{1},0)$ to $(0,s_{2})$.

To see that these lines form a $k$-cover of $\Gamma$, observe that every
interior point is covered by $d_{2}$ vertical lines from (i) and $d_{1}$
horizontal lines from (ii), and is thus covered $d_{1}+d_{2}=k$ times in
total. For the boundary points, a point of the form $(s_{1},0)$ for $s_{1}\in
S_{1}\setminus\\{0\\}$ is covered $d_{2}$ times by the lines in (i), while the
biregularity of the multigraph $B$ ensures it is covered $d_{1}$ times by the
lines in (iii). Similarly, each point of the form $(0,s_{2})$ for $s_{2}\in
S_{2}\setminus\\{0\\}$ is covered $d_{1}$ times by the lines in (ii) and
$d_{2}$ times by those in (iii). Thus, the boundary points are also each
covered $k$ times. Finally, none of the lines in our collection passes through
the origin.

We thus obtain our upper bound by calculating the size of this cover, which
yields

$\displaystyle\operatorname{cov}_{k}(\Gamma)$ $\displaystyle\leq
d_{2}(n-1)+d_{1}(m-1)+d_{1}(n-1)$
$\displaystyle=(d_{1}+d_{2})(n-1)+d_{1}(m-1)$
$\displaystyle=k(n-1)+\frac{bk}{a+b}(m-1)$
$\displaystyle=k(n-1)+\frac{k}{n+m-2}(m-1)^{2},$

as required. ∎

##  4 Square grids

In the previous section, we saw that the Ball–Serra bound is tight when the
grid is much wider than it is tall, and proved a lower bound for generic grids
that becomes much larger than the Ball–Serra bound as the dimensions grow
closer in size. Therefore, for the rest of this paper, we focus on $n\times n$
grids. In Section 4.1 we prove Theorem 1.3, which provides general lower and
upper bounds on $\operatorname{cov}_{k}(\Gamma)$ for arbitrary $n\times n$
grids $\Gamma$. In Section 4.2 we focus on the standard grid
$\Gamma_{n}=\Gamma\left(\\{0,1,\ldots,n-1\\},\\{0,1,\ldots,n-1\\}\right)$,
proving Theorems 1.4 and 1.5.

###  4.1 General results

We start by restating our general bounds for square grids.

See 1.3

We will prove the upper bound of (a) via an explicit construction of a
$k$-cover, and use the linear programming framework of Section 2 to establish
the lower bounds of (b) and (c).

###### Proof.

(a) Note that when $k$ is even, the upper bound
$\operatorname{cov}_{k}(\Gamma)\leq\tfrac{3}{2}k(n-1)$ follows from the upper
bound in Theorem 1.2 when $m=n$. We will obtain the upper bound for odd $k$
with some appropriate rounding, and present a unified construction below.

Let $\\{x_{1},x_{2},\ldots,x_{n-1}\\}$ be the nonzero elements of $S_{1}$, and
let $\\{y_{1},y_{2},\ldots,y_{n-1}\\}$ be the nonzero elements of $S_{2}$. We
form a $k$-cover of $\Gamma$ consisting of the following lines:

  1. (i)

$\left\lceil\frac{1}{2}k\right\rceil$ copies of the lines $x=x_{i}$ and
$y=y_{i}$, for each $i\in[n-1]$;

  2. (ii)

$\left\lfloor\frac{1}{2}k\right\rfloor$ copies of line connecting $(x_{i},0)$
to $(0,y_{i})$, for each $i\in[n-1]$.

There are $2\left\lceil\frac{1}{2}k\right\rceil(n-1)$ lines in (i) and
$\left\lfloor\frac{1}{2}k\right\rfloor$ lines in (ii), and hence we have a
total of $\left\lceil\frac{3}{2}k\right\rceil(n-1)$ lines, and it is evident
that none of these pass through the origin. To see that they form a $k$-cover,
observe first that each interior point is covered by
$\left\lceil\frac{1}{2}k\right\rceil$ horizontal lines and
$\left\lceil\frac{1}{2}k\right\rceil$ vertical lines, and is thus covered at
least $k$ times in total. Meanwhile, each boundary point is covered
$\left\lceil\frac{1}{2}k\right\rceil$ times by the lines in (i) and
$\left\lfloor\frac{1}{2}k\right\rfloor$ times by the lines in (ii), and so is
incident to exactly $k$ lines. These lines therefore indeed form a $k$-cover,
showing
$\operatorname{cov}_{k}(\Gamma)\leq\left\lceil\frac{3}{2}k\right\rceil(n-1)$.

(b) To prove lower bounds, we appeal to the dual linear program
${\mathcal{D}}(\Gamma)$. Our goal is to define a weighting $w$ of the nonzero
points of $\Gamma$ of large total weight in which no origin-avoiding line has
weight more than $1$. The key observation is that these lines can contain at
most two boundary points, and so we can hope to get away with assigning large
weights to the boundary points.

We shall first try a simple weighting $w^{\prime}$, where all boundary points
obtain a weight of $\alpha$, and all interior points a weight of $\beta$, for
$\alpha$ and $\beta$ to be chosen later. Unfortunately, this initial attempt
does not work. Indeed, we have
$w^{\prime}(\Gamma)=2(n-1)\alpha+(n-1)^{2}\beta=\left(2\alpha+(n-1)\beta\right)(n-1)$.
Since there could be lines containing two boundary points and $n-2$ interior
points, we must have $2\alpha+(n-2)\beta\leq 1$. Hence,
$w^{\prime}(\Gamma)\leq(1+\beta)(n-1)$. As lines parallel to the axes contain
an boundary point and $n-1$ interior points, we must also have
$\alpha+(n-1)\beta\leq 1$, which in particular implies
$\beta\leq\frac{1}{n-1}$. Thus, $w^{\prime}(\Gamma)\leq n$, and so the best
lower bound we can hope for from such a weighting is
$\operatorname{cov}_{k}(\Gamma)\geq kn$, which is worse than the Ball–Serra
bound (2) for $n\geq k+2$.

To salvage this idea, we will instead only assign weight to some of the
boundary points, with the aim of ensuring that any origin-avoiding line
containing two positively-weighted boundary points cannot contain too many
interior points. For this, we use the following claim, bounding the number of
points contained in certain lines.

######  Claim 4.1.

Suppose we enumerate the members of $S_{1}$ as $x_{1}<x_{2}<\ldots<x_{n}$ and
those of $S_{2}$ as $y_{1}<y_{2}<\ldots<y_{n}$, and suppose $i_{0}\in[n]$ is
such that $x_{i_{0}}=0$. Let $j\in[n]$ and $\ell$ be a line passing through
$(0,y_{j})$. If $\ell$ has positive slope, then $\ell$ contains at most
$n-|j-i_{0}|$ points of $\Gamma$. If $\ell$ has negative slope, then $\ell$
contains at most $n-|(n-j)-i_{0}|$ points of $\Gamma$.

###### Proof of 4.1.

Suppose first that $\ell$ is a line of positive slope passing through
$(0,y_{j})$. We define $S_{1}^{-}=\\{x\in S_{1}:x\leq 0\\}$ and
$S_{2}^{-}=\\{y\in S_{2}:y\leq y_{j}\\}$, observing that $|S_{1}^{-}|=i_{0}$
and $|S_{2}^{-}|=j$. Since $\ell$ is of positive slope, it follows that, if
$(x,y)\in\ell$ for any $x\in S_{1}^{-}$, we must have $y\in S_{2}^{-}$.

If $j\geq i_{0}$, then, since each value in $S_{1}^{-}$ can correspond to at
most one value in $S_{2}^{-}$, it follows that there will be at least
$j-i_{0}$ coordinates in $S_{2}^{-}$, and thus in $S_{2}$, that are not mapped
to by $\ell$, and so $\ell$ can contain at most $n-(j-i_{0})$ points of
$\Gamma$. Similarly, if $j<i_{0}$, since each value in $S_{2}^{-}$ corresponds
to at most one value from $S_{1}^{-}$, there will be at least $i_{0}-j$ values
in $S_{1}$ not covered by $\ell$, and so $\ell$ contains at most $n-(i_{0}-j)$
points from $\Gamma$. This shows that lines of positive slope through
$(0,y_{j})$ can contain at most $n-|j-i_{0}|$ points of $\Gamma$.

For lines of negative slope, we can reflect the grid in the $x$-axis,
considering $S_{2}^{\prime}=\\{-y:y\in S_{2}\\}$. This reverses the ordering
of the elements, so $y^{\prime}_{i}=-y_{n-i}$. The line $\ell$ then
corresponds to a line $\ell^{\prime}$ of positive slope passing through
$(0,y^{\prime}_{n-j})$, and thus contains at most $n-|(n-j)-i_{0}|$ points of
the grid. ∎

With this claim in mind, we now define an improved weighting of the points of
$\Gamma$. As in the claim, enumerate the elements of $S_{1}$ as
$x_{1}<x_{2}<\ldots<x_{n}$ and those of $S_{2}$ as $y_{1}<y_{2}<\ldots<y_{n}$,
and let $i_{0},j_{0}\in[n]$ be such that $x_{i_{0}}=0$ and $y_{j_{0}}=0$.
Given parameters $\alpha,\beta$ and $t$, to be chosen later, we define the
weights on $\Gamma\setminus\\{(0,0)\\}$ as follows:

$w((x_{i},y_{j}))=\begin{cases}\alpha&\textrm{if }i\neq i_{0}\textrm{ and
}j\neq j_{0};\\\ \beta&\textrm{if }j=j_{0}\textrm{, or if }i=i_{0}\textrm{ and
}\min\\{|j-i_{0}|,|n-j-i_{0}|\\}\geq t;\\\ 0&\textrm{otherwise}.\end{cases}$

That is, we assign weight $\alpha$ to all interior points and weight $\beta$
to all boundary points except those in intervals around $y_{i_{0}}$ and
$y_{n-i_{0}}$ on the $y$-axis.

For the weighting to be valid, we require that each origin-avoiding line have
weight at most $1$. If the line $\ell$ contains two boundary points with
positive weight, then let it pass through $(0,y_{j})$ on the $y$-axis. By
definition of $w$, we must have $|j-i_{0}|,|(n-j)-i_{0}|\geq t$, and so by
Claim 4.1, $\ell$ contains at most $n-t$ points of $\Gamma$, and hence at most
$n-t-2$ interior points. Thus, the weight of any such line is at most
$2\beta+(n-t-2)\alpha$.

Otherwise, the line $\ell$ can contain at most one weighted boundary point and
at most $n-1$ interior points, giving a total weight of not more than
$\beta+(n-1)\alpha$. Hence, our parameters must satisfy
$2\beta+(n-t-2)\alpha\leq 1$, $\beta+(n-1)\alpha\leq 1$, $\alpha,\beta\geq 0$,
and $t\in\mathbb{N}$.

With regards to the objective function, we note that there are at most
$2(2t-1)$ boundary points with weight zero, and thus $w(\Gamma)\geq
2(n-2t)\beta+(n-1)^{2}\alpha$, and we wish to maximise this quantity subject
to the constraints above. Some routine calculations then yield that we should
set $t=\left\lceil\tfrac{1}{2}\sqrt{(5n+1)(n-1)}-n\right\rceil$,
$\alpha=\frac{1}{n+t}$ and $\beta=\frac{t+1}{n+t}$, for which we have
$w(\Gamma)=\left(10-4\sqrt{5}+o(1)\right)(n-1)$. Proposition 2.1 gives the
desired lower bound:

$\operatorname{cov}_{k}(\Gamma)\geq k\Phi(\Gamma)\geq
kw(\Gamma)=\left(10-4\sqrt{5}+o(1)\right)k(n-1).$

(c) For the final part of the theorem, we assume the grid $\Gamma$ is
$\Delta$-generic, meaning that any line through two boundary points can
contain at most $\Delta$ interior points. In the framework of part (b), where
we assign a weight of $\alpha$ to all interior points, and a weight of $\beta$
to all boundary points, we then obtain the constraint $\beta+(n-1)\alpha\leq
1$ from the lines with at most one boundary point, and the constraint
$2\beta+\Delta\alpha\leq 1$ from the lines with two boundary points. The total
weight, which we seek to maximise, is $2(n-1)\beta+(n-1)^{2}\alpha$.

This optimisation problem is solved by taking
$\beta=1-\frac{n-1}{2(n-1)-\Delta}$ and $\alpha=\frac{1}{2(n-1)-\Delta}$. It
is readily verified that both constraints are then satisfied with equality,
and the total weight of the grid is
$\left[2-\frac{n-1}{2(n-1)-\Delta}\right](n-1)$, whence the result follows by
once again applying Proposition 2.1. ∎

A few remarks are in order at this point. First, we note that the lower bound
of part (b) can be improved if we have additional information about where the
origin is in the grid. For example, suppose the origin is in the lower-left
corner; that is, $\min S_{1}=\min S_{2}=0$. Then any line containing two
boundary points must be of negative slope, and hence when we apply Claim 4.1,
we see that it is enough to leave only the largest values on the $y$-axis
unweighted. When one solves the corresponding optimisation problem, we find
that $\operatorname{cov}_{k}(\Gamma)\geq\left(4-2\sqrt{2}+o(1)\right)k(n-1)$
for such grids $\Gamma$, a considerable improvement in the constant factor, as
$4-2\sqrt{2}\approx 1.1716$.

Second, as explained in the introduction, almost all grids $\Gamma$ are
generic, and parts (a) and (c) of Theorem 1.3 determine
$\operatorname{cov}_{k}(\Gamma)$ precisely when $k$ is even and asymptotically
when $k$ is odd and large. However, even when the grid $\Gamma$ is not generic
but only $\Delta$-generic, provided $\Delta=o(n)$, part (c) is robust enough
to resolve the problem asymptotically. We give some natural examples of this
below.

######  Corollary 4.2.

Given $n\in\mathbb{N}$, let $\Gamma_{\mathrm{exp},n}=\Gamma(E,E)$, where
$E=\\{0,1,2,4,\ldots,2^{n-2}\\}$, and let
$\Gamma_{\mathrm{quad},n}=\Gamma(S,S)$, where
$S=\\{0,1,4,\ldots,(n-1)^{2}\\}$. Then, if
$\Gamma\in\\{\Gamma_{\mathrm{exp},n},\Gamma_{\mathrm{quad},n}\\}$, we have
$\operatorname{cov}_{k}(\Gamma)=\left(\frac{3}{2}+o(1)\right)k(n-1)$ as
$k,n\to\infty$.

###### Proof.

By Theorem 1.3(a), we know
$\operatorname{cov}_{k}(\Gamma)\leq\left\lceil\frac{3}{2}k\right\rceil(n-1)$,
which is $\left(\frac{3}{2}+o(1)\right)k(n-1)$ as $k\to\infty$, and so we need
only demonstrate the lower bound. By Theorem 1.3(c), it suffices to show
$\Gamma$ is $\Delta$-generic for some $\Delta=o(n)$.

We begin with $\Gamma=\Gamma_{\mathrm{exp},n}$, and show that is $1$-generic.
Indeed, suppose $\ell$ is a line containing two boundary points of $\Gamma$,
say $(0,2^{i})$ and $(2^{j},0)$. It is then a straightforward calculation to
see that, for any $r$, the line $\ell$ passes through
$(2^{r},2^{i}-2^{i-j+r})$. In order for this to be an interior point of the
grid $\Gamma_{\mathrm{exp},n}$, we require that $2^{i}-2^{i-j+r}$ is a
positive power of $2$ strictly smaller than $2^{i}$, which only happens for
$r=j-1$. Thus, the line $\ell$ contains exactly one interior point, and hence
$\Gamma_{\mathrm{exp},n}$ is $1$-generic.

The quadratic grid $\Gamma_{\mathrm{quad},n}$ requires somewhat more delicate
treatment. Again, let us suppose $\ell$ is a line containing the boundary
points $(0,a^{2})$ and $(b^{2},0)$, and let $(r^{2},s^{2})$ be an interior
point lying on $\ell$. We then have
$s^{2}=a^{2}\left(1-\frac{r^{2}}{b^{2}}\right)$, or
$(ab)^{2}=(ar)^{2}+(bs)^{2}$. Thus, we can bound the number of interior points
on $\ell$ by the number of ways of writing $(ab)^{2}$ as a sum of squares.
Following Beiler [6], if $Q$ is the set of prime divisors of $ab$ that are
congruent to $1$ modulo $4$, and if $\beta_{q}$ is the multiplicity of $q\in
Q$ in the prime factorisation of $(ab)^{2}$, then there are $\prod_{q\in
Q}\left(\beta_{q}+1\right)$ ways to write $(ab)^{2}$ as a sum of squares.

To simplify the notation in the calculation below, we shall assume $q=5,13$
and $17$ are included in $Q$, setting $\beta_{q}=0$ in case they do not divide
$ab$. Now observe that we have

$\displaystyle\sum_{q\in Q}\left(\beta_{q}+1\right)$
$\displaystyle=3+\beta_{5}+\beta_{13}+\beta_{17}+\sum_{q\in Q,q\geq
29}\left(\beta_{q}+1\right)$ $\displaystyle\leq
3+\beta_{5}+\beta_{13}+\beta_{17}+\sum_{q\in Q,q\geq 29}2\beta_{q}$
$\displaystyle\leq 3+\sum_{q\in
Q}\beta_{q}\log_{5}q=3+\log_{5}\left(\prod_{q\in Q}q^{\beta_{q}}\right)\leq
3+\log_{5}\left((ab)^{2}\right),$

and so $\sum_{q\in Q}(\beta_{q}+1)\leq 3+4\log_{5}n$.

Now, given some natural numbers $m_{i}$, it is simple to show that
$\prod_{i}m_{i}\leq 3^{\tfrac{1}{3}\sum_{i}m_{i}}$, and hence the number of
ways to express $(ab)^{2}$ as a sum of squares is at most
$3^{\tfrac{1}{3}\sum_{q\in Q}(\beta_{q}+1)}\leq 3\cdot
3^{\tfrac{4}{3}\log_{5}n}=3n^{\tfrac{4}{3}\log_{5}3}$. It thus follows that
$\Gamma_{\mathrm{quad},n}$ is $\Delta$-generic for
$\Delta=3n^{\tfrac{4}{3}\log_{5}3}=o(n)$. ∎

###  4.2 Standard grids

While the results of Section 4.1 resolve the problem asymptotically for very
many grids, there is no questioning the fact that the most natural case to
consider is that of the standard grid $\Gamma(S,S)$, where
$S=\\{0,1,\ldots,n-1\\}$. For convenience, we denote this grid by
$\Gamma_{n}$. By considering the line $x+y=n-1$, we see that $\Gamma_{n}$ is
not $\Delta$-generic for any $\Delta<n-2$, which means the lower bound of
Theorem 1.3(c) is worse than the Ball–Serra bound for $n>k$. By tailoring our
methods for this specific grid, though, we will obtain much better bounds. We
begin by showing that a strict $k$-cover of the standard grid requires far
fewer lines than the upper bound given by 1.3, which, as shown in the previous
subsection, is asymptotically tight for most grids.

###### Proof of 1.4 (upper bound).

We construct a $k$-cover of $\Gamma_{n}$ of size $(\sqrt{2}+o(1))k(n-1)$. Let
$t\in[n-1]$ be a parameter, to be determined later, and consider the following
collection of lines:

  1. (i)

$\left\lceil\frac{i}{n+t-1}k\right\rceil$ copies of the lines $x=i$ and $y=i$
for each $i\in[n-1]$;

  2. (ii)

$k-\left\lceil\frac{i}{n+t-1}k\right\rceil$ copies of the line $x+y=i$ for
every $1\leq i<n+t-1$.

We begin by showing that the above collection of lines gives a $k$-cover of
$\Gamma_{n}$. First, it is clear that no line passes through the origin. Now
consider a point $(s_{1},s_{2})\in\Gamma_{n}\setminus\\{(0,0)\\}$. If
$s_{1}+s_{2}<n+t-1$, then $(s_{1},s_{2})$ is covered
$\left\lceil\frac{s_{1}}{n+t-1}k\right\rceil+\left\lceil\frac{s_{2}}{n+t-1}k\right\rceil$
times by the lines in (i) and another
$k-\left\lceil\frac{s_{1}+s_{2}}{n+t-1}k\right\rceil$ times by those in (ii),
and thus at least $k$ times in total. On the other hand, if $s_{1}+s_{2}\geq
n+t-1$, then lines in (i) alone cover the point
$\left\lceil\frac{s_{1}}{n+t-1}k\right\rceil+\left\lceil\frac{s_{2}}{n+t-1}k\right\rceil\geq
k$ times, as required. Calculating the size of this $k$-cover, we obtain

$\displaystyle\operatorname{cov}_{k}(\Gamma_{n})$ $\displaystyle\leq
2\sum\limits_{i=1}^{n-1}\left\lceil\frac{i}{n+t-1}k\right\rceil+\sum\limits_{i=1}^{n+t-2}\left(k-\left\lceil\frac{i}{n+t-1}k\right\rceil\right)$
$\displaystyle\leq
k\left[2\sum\limits_{i=1}^{n-1}{\frac{i}{n+t-1}}+\sum\limits_{j=1}^{n+t-2}{\frac{j}{n+t-1}}\right]+2n$
$\displaystyle\leq
k\left[\frac{2}{n+t-1}\binom{n}{2}+\frac{1}{n+t-1}\binom{n+t-1}{2}\right]+2n$
$\displaystyle=k\left[\frac{n(n-1)}{n+t-1}+\frac{n+t-2}{2}\right]+2n.$ (7)

The upper bound given by (7) is valid for any $t\in[n-1]$; we now want to
choose a value of $t$ that makes the right-hand side as small as possible. The
function $g(t)=\frac{n(n-1)}{n+t-1}+\frac{n+t-2}{2}$ has its minimum at
$t_{0}=\sqrt{2(n-1)n}-(n-1)$. Since our parameter must be an integer, we
choose $t=\left\lceil\sqrt{2(n-1)n}-(n-1)\right\rceil=(\sqrt{2}-1+o(1))(n-1)$,
and substituting this value of $t$ into (7) yields the claimed upper bound of
$(\sqrt{2}+o(1))k(n-1)$ on $\operatorname{cov}_{k}(\Gamma_{n})$. ∎

We now turn our attention to the lower bound.

###### Proof of 1.4 (lower bound).

By 2.1, it suffices to find a feasible solution to the dual linear program
${\mathcal{D}}(\Gamma_{n})$, that is, a weighting of the nonzero points of
$\Gamma_{n}$ in which every origin-avoiding line has weight at most 1, that
has total weight at least $(2-e^{-1/2}+o(1))(n-1)$.

Let $t$ be the largest integer such that
$\sum_{i=1}^{t}\frac{1}{n-i}\leq\tfrac{1}{2}$ and consider the following
weighting on the points of $\Gamma_{n}\setminus\\{(0,0)\\}$:

$w((x,y))=\begin{cases}\frac{1}{2}&\textrm{if }xy=0;\\\
\frac{1}{n-i}&\textrm{if }x+y=n-1+i\textrm{ for some }i\in[t];\\\
0&\textrm{otherwise}.\end{cases}$

We first show that $(w((x,y)):(x,y)\in\Gamma_{n})$ gives a feasible solution
to the dual linear program ${\mathcal{D}}(\Gamma_{n})$. Clearly $w((x,y))\geq
0$ for all $(x,y)\in\Gamma_{n}\setminus\\{(0,0)\\}$. Now, let
$\ell\in\mathcal{L}$ be any line. If $\ell$ contains two boundary points, then
any interior point $(x,y)$ on $\ell$ satisfies $x+y\leq n-1$, and thus has
weight zero. It follows that $w(\ell)=1$. Otherwise, if $(x,y)\mapsto x+y$ is
constant on $\ell$, then $\ell=\\{(x,y):x+y=n-1+i\\}$ for some $i\in[n-1]$.
Then all points on $\ell$ have weight zero, unless $1\leq i\leq t$, in which
case $\ell$ contains $n-i$ points of weight $\tfrac{1}{n-i}$ each. Thus
$w(\ell)\leq 1$ in this case. Finally, if $(x,y)\mapsto x+y$ is not constant
on $\ell$, it must be injective. Then, $\ell$ contains at most one boundary
point, which has weight $\frac{1}{2}$, and the weight from the remaining
points is at most $\sum_{i=1}^{t}\tfrac{1}{n-i}$, which by the choice of $t$
is at most $\tfrac{1}{2}$. So in total we again have $w(\ell)\leq 1$.

To compute the total weight of the grid, observe that each diagonal line of
the form $x+y=i$ has weight one if $1\leq i\leq n-1+t$ and zero otherwise.
Thus, the total weight of the grid is $n-1+t$.

It remains to estimate $t$. Note that $t\leq\tfrac{n}{2}$, since
$\sum_{i=1}^{t}\tfrac{1}{n-i}\geq\sum_{i=1}^{t}\tfrac{1}{n}=\tfrac{t}{n}$, and
so both $n-1$ and $n-1-t$ go to infinity linearly with $n$. It is well known
that, as $m\to\infty$, the partial sums $H_{m}$ of the Harmonic series satisfy
$H_{m}=\sum_{j=1}^{m}\tfrac{1}{j}=\log m+\gamma+o(1)$, where $\gamma$ is a
constant. Hence,

$\displaystyle\sum_{i=1}^{t}\frac{1}{n-i}$
$\displaystyle=H_{n-1}-H_{n-1-t}=\log\left(\frac{n-1}{n-1-t}\right)+o(1).$

Thus, we must have $\log\left(\frac{n-1}{n-1-t}\right)=\tfrac{1}{2}+o(1)$, or
$\log\left(1-\frac{t}{n-1}\right)=-\tfrac{1}{2}+o(1)$. This gives
$1-\tfrac{t}{n-1}=e^{-1/2}+o(1)$, or $t=\left(1-e^{-1/2}+o(1)\right)(n-1)$,
which results in the claimed bound. ∎

The cover we constructed for the upper bound only uses lines of slope $0$,
$\infty$, and $-1$. This may seem rather limited, and it is natural to wonder
if one can do better by making use of other lines as well. However, we
verified by computer search that for small values of $n$ and $k$, one is
always able to build an optimal $k$-cover consisting only of these three types
of lines. This motivated us to further study this restricted class of
$k$-covers, and in our final result we prove that the smallest $k$-cover of
this form has size $\left(\sqrt{2}+o(1)\right)k(n-1)$.

###### Proof of 1.5.

For convenience, we will hereon call lines of slope $-1$ _diagonals_. Since
the cover constructed for the upper bound in 1.4 only uses horizontal,
vertical, and diagonal lines, it also provides the same upper bound of
$\left(\sqrt{2}+o(1)\right)k(n-1)$ in this restricted setting.

To obtain a matching lower bound, we will again appeal to the linear
programming approach. Recall that previously we obtained lower bounds by
assigning weights to the points, whose sum was as large as possible, provided
that the total weight along every origin-avoiding line was at most $1$. In
this restricted setting, since we are only able to use horizontal, vertical,
and diagonal lines, the dual linear program only has constraints on the
weights along these lines. This gives us much more freedom in choosing the
weights, and thus we may hope to find a feasible weighting with a larger sum.

Observe that in our search for an optimal weighting, we have $n^{2}-1$ degrees
of freedom (the weights of the individual nonzero points) but only $4(n-1)$
constraints (the horizontal, vertical, and diagonal lines). In order to reduce
the search space and simplify our task, we shall impose the following
additional conditions on the weighting $w$.

  * •

The weighting is symmetric across the main diagonal; that is, $w(x,y)=w(y,x)$
for all $(x,y)\in\Gamma_{n}\setminus\\{(0,0)\\}$.

  * •

On each diagonal, every interior point has the same weight.

  * •

Every vertical line avoiding the origin has weight one (and hence so does
every horizontal line).

  * •

There is some $t\in[n-1]$ such that the weight of the diagonal $x+y=i$ is $1$
if $1\leq i\leq n+t-1$, is at most $1$ if $i=n+t$, and is $0$ if $i\geq
n+t+1$.

Some remarks are in order now. First, note that the requirement of symmetry is
without loss of generality, since if $w$ is any feasible weighting, then
$w^{\prime}$ defined by
$w^{\prime}(x,y)=\tfrac{1}{2}\left(w(x,y)+w(y,x)\right)$ is a symmetric
feasible weighting of the same total weight.

With regards to the total weight, by summing along the diagonals, we see that
$w(\Gamma_{n}\setminus\\{(0,0)\\})$ is at least $n+t-1$ and at most $n+t$.
Thus, our goal is to maximise the value of $t$ for which we can find such a
feasible weighting.

Now, for some fixed $t$, observe that the weights of approximately half the
points are already determined by the conditions. Since the diagonals $x+y=i$,
for $i\geq n+t+1$, have weight $0$, we must have $w(x,y)=0$ whenever
$x+y>n+t$. On the other hand, if $n\leq i\leq n+t-1$, then we know the
diagonal has weight $1$. Since the diagonal consists entirely of $2n-1-i$
internal points, all of which must have the same weight, we have
$w(x,y)=\frac{1}{2n-1-(x+y)}$ whenever $n\leq x+y\leq n+t-1$. Finally, when
$x+y=n+t$, we must have $w(x,y)=z$ for some $0\leq z\leq\frac{1}{n-t-1}$ to
ensure the diagonal has weight at most $1$.

We now turn our attention to the lower triangular points of the grid; that is,
$(x,y)$ with $1\leq x+y\leq n-1$. In our previous weighting, we assigned
weight $\tfrac{1}{2}$ to the boundary points and left the interior points
unweighted. Now that we have some more freedom, we will look to spread the
weight throughout the grid. With that in mind, we introduce parameters
$\alpha_{i}$, $1\leq i\leq n-1$, such that
$w(i,0)=w(0,i)=\tfrac{1}{2}-\alpha_{i}$. Since the diagonal $x+y=i$ has total
weight $1$, it follows that $w(x,y)=\frac{2\alpha_{x+y}}{x+y-1}$ for the
$x+y-1$ interior points $(x,y)$ with $x+y=i$, $x,y\neq 0$.

Thus, using the symmetry and the conditions along the diagonals, we have shown
that our weighting takes the form

$w((x,y))=\begin{cases}\frac{1}{2}-\alpha_{x+y}&\textrm{if }x=0\textrm{ or
}y=0;\\\ \frac{2\alpha_{x+y}}{x+y-1}&\textrm{if }x,y\neq 0\textrm{ and }1\leq
x+y\leq n-1;\\\ \frac{1}{2n-1-i}&\textrm{if }x+y=i\textrm{ for some }n\leq
i\leq n+t-1;\\\ z&\textrm{if }x+y=n+t;\\\ 0&\textrm{if }x+y\geq
n+t+1.\end{cases}$

for some parameters $\alpha_{1},\ldots,\alpha_{n-1},z\in\mathbb{R}_{\geq 0}$.
To finish, we will use the condition that the vertical lines have total weight
$1$ to solve for $\alpha_{i}$.

Indeed, by considering the line $x=n-1$, we have
$\tfrac{1}{2}-\alpha_{n-1}+\sum_{i=n}^{n+t-1}\frac{1}{2n-1-i}+z=1$, which
yields

$\alpha_{n-1}=\sum\limits_{i=n}^{n+t-1}\frac{1}{2n-1-i}+z-\frac{1}{2}.$ (8)

Now compare the weights of the points on the lines $x=n-2$ and $x=n-1$. Since
the diagonals are constant along their interior points, we have
$w(n-2,y)=w(n-1,y-1)$ for all $2\leq y\leq n-1$. Hence the differences are
that $w(n-2,0)$ and $w(n-2,1)$ replace $w(n-1,0)$ and $w(n-1,n-1)$. Thus,

$\displaystyle
w\left(\left\\{x=n-2\right\\}\right)-w\left(\left\\{x=n-1\right\\}\right)$
$\displaystyle=w(n-2,0)+w(n-2,1)-w(n-1,0)-w(n-1,n-1)$
$\displaystyle=\tfrac{1}{2}-\alpha_{n-2}+\frac{2\alpha_{n-1}}{n-2}-\left(\tfrac{1}{2}-\alpha_{n-1}\right)-0,$

and since both vertical lines have weight $1$, this gives
$\alpha_{n-2}=\left(1+\frac{2}{n-2}\right)\alpha_{n-1}$. Repeating this
argument for the lines $x=i-1$ and $x=i$ for each $2\leq i\leq n-1$, we obtain
the following recurrence relation:

$\alpha_{i-1}=\left(1+\frac{2}{i-1}\right)\alpha_{i}-z\mathbf{1}_{i=t+1}-\frac{1}{n-i}\mathbf{1}_{i\leq
t},$ (9)

where $\mathbf{1}_{A}$ is the indicator function of the event $A$ defined as

$\mathbf{1}_{A}=\begin{cases}1&\textrm{if $A$ is true};\\\ 0&\textrm{if $A$ is
false}.\\\ \end{cases}$

For the initial condition, observe that the line $x+y=1$ has no interior
points, and so for it to have weight $1$, we must have $\alpha_{1}=0$.
Combining this with (9), we obtain:

$\alpha_{i}=\frac{1}{i(i+1)}\sum\limits_{j=1}^{\min\\{t,i\\}}\frac{j(j-1)}{n-j}+\mathbf{1}_{i\geq
t+1}\frac{t(t+1)}{i(i+1)}z\quad\text{ for all }2\leq i\leq n-1.$ (10)

Substituting the value of $\alpha_{n-1}$ from (10) into (8), we can then solve
for $z$ to obtain:

$\displaystyle
z=\left(\frac{1}{2}-\sum\limits_{j=1}^{t}\frac{1}{n-j}\left(1-\frac{j(j-1)}{(n-1)n}\right)\right)\frac{n(n-1)}{n(n-1)-t(t+1)}$
(11)
$\displaystyle=\frac{(n-1)n\left(\frac{1}{2}-\frac{t(2n+t-1)}{2(n-1)n}\right)}{(n-1)n-t(t+1)},$
(12)

where the second equality is due to the fact that

$\sum\limits_{j=1}^{t}\frac{1}{n-j}\left(1-\frac{j(j-1)}{(n-1)n}\right)=\frac{1}{n(n-1)}\sum\limits_{j=1}^{t}(n+j-1)=\frac{t(2n+t-1)}{2n(n-1)}.$

Recall that feasibility dictates $0\leq z\leq\frac{1}{n-t-1}$. If $n>1$, we
have $z\geq 0$ when $0\leq
t\leq\frac{1}{2}\left(\sqrt{8n^{2}-8n+1}-2n+1\right)$ and
$z\leq\frac{1}{n-t-1}$ for
$\frac{1}{2}\left(\sqrt{8n^{2}-8n+1}-2n-1\right)\leq t<n-1$. Taking $t$ to be
an integer satisfying $\frac{1}{2}\left(\sqrt{8n^{2}-8n+1}-2n-1\right)\leq
t\leq\frac{1}{2}\left(\sqrt{8n^{2}-8n+1}-2n+1\right)$, we have
$t=(\sqrt{2}-1+o(1))(n-1)$. It follows that the total weight of the grid is
$\left(\sqrt{2}+o(1)\right)(n-1)$.

We are not quite done, as there is one final condition to verify — to ensure
that all our weights are non-negative, we must have
$0\leq\alpha_{i}\leq\frac{1}{2}$ for all $1\leq i\leq n-1$. From (9) we have:

$\displaystyle\alpha_{i}$
$\displaystyle=\frac{i-1}{i+1}\left(\alpha_{i-1}+\frac{1}{n-i}\right)$
$\displaystyle\text{if }2\leq i\leq t.$ $\displaystyle\alpha_{i}$
$\displaystyle=\frac{i-1}{i+1}(\alpha_{i-1}+z)\leq\frac{i-1}{i+1}\left(\alpha_{i-1}+\frac{1}{n-i}\right)$
$\displaystyle\text{if }i=t+1$ $\displaystyle\alpha_{i}$
$\displaystyle=\frac{i-1}{i+1}\alpha_{i-1}<\alpha_{i-1}$
$\displaystyle\text{if }t+2\leq i\leq n-1$

Thus, it suffices to show that $\alpha_{i}\leq\frac{1}{2}$ for all $2\leq
i\leq t+1$. We will do so by showing that for $1\leq i\leq t+1$, we have
$\alpha_{i}\leq\frac{i-1}{2(n-i-1)}$ by induction on $i$. We know that
$\alpha_{1}=0$, so the base case is clear. Let $i>1$ and assume the induction
hypothesis; then

$\alpha_{i}\leq\frac{i-1}{i+1}\left(\alpha_{i-1}+\frac{1}{n-i}\right)\leq\frac{i-1}{i+1}\left(\frac{i-2}{2(n-i)}+\frac{1}{n-i}\right)\leq\frac{i-1}{2(n-i-1)}.$

We have $\frac{i-1}{2(n-i-1)}\leq\frac{1}{2}$ whenever $i\leq n-i$, which is
true since $i\leq t+1=(\sqrt{2}-1+o(1))(n-1)$.

Hence our weighting is indeed feasible and
$w\left(\Gamma_{n}\setminus\left\\{(0,0)\right\\}\right)=\left(\sqrt{2}+o(1)\right)(n-1)$.
It thus follows that any $k$-cover of $\Gamma_{n}$ using only horizontal,
vertical, and diagonal lines must have size at least
$\left(\sqrt{2}+o(1)\right)k(n-1)$. ∎

##  5 Conclusion

In this paper, we studied line coverings with multiplicities for two-
dimensional real grids. We determined the minimum size of a cover in several
cases, but some natural and interesting questions remain open, and we
highlight them below.

In Section 3, we investigated for which grids the Ball–Serra bound is tight.
We proved that, when $n$ is sufficiently large with respect to $m$ and $k$,
the Ball–Serra bound is tight for any $n\times m$ grid. Moreover, we showed
that the threshold value for $n$ given by 1.1 is tight for _most_ grids. It
can be shown, however, that this bound on $n$ is not best possible for _all_
grids. For example, for the grid $\Gamma(S_{1},S_{2})$, where
$S_{1}=\\{0,1,2,\dots,n-1\\}$ and $S_{2}=\\{-1,0,1\\}$, and any $k\geq 3$, we
can show that the Ball–Serra bound is tight already for $n=2(k-1)$, as opposed
to the lower bound $n\geq 2k-1$ of 1.1. However, in this grid the omitted
point $(0,0)$ is not a corner point, while, as in the square grid setting, it
is more natural to consider grids in which $(0,0)$ is a corner. For such
grids, one could investigate when the Ball–Serra bound holds.

######  Question 5.1.

Let $\Gamma$ be the grid $\\{0,1,2,\dots,n-1\\}\times\\{0,1,2,\dots,m-1\\}$
and $k\geq 2$ be an integer. How large must $n$ be with respect to $m$ and $k$
to have $cov(\Gamma)=k(n-1)+(m-1)$?

Our main result for standard grids establishes reasonably good asymptotic
lower and upper bounds on $\operatorname{cov}_{k}(\Gamma_{n})$. It would be of
interest to close the remaining gap.

######  Question 5.2.

What is the true asymptotic value of $\operatorname{cov}_{k}(\Gamma_{n})$?

We tend to believe that
$\operatorname{cov}_{k}(\Gamma_{n})=(\sqrt{2}+o(1))k(n-1)$. In 1.5, we showed
this to be the case when we only use lines of slope $0$, $\infty$, and $-1$.
However, for the weighting we used to establish the lower bound, one can show
that lines of slope $1$ near the origin (e.g., $y=x+1$) have weight larger
than $1$ when $n$ is large. We believe that these are the only problematic
lines, and so as an intermediate step one could attempt to verify that our
weighting remains feasible if one only forbids lines of slope $1$. This would
imply that any $k$-cover of $\Gamma_{n}$ of size smaller than
$\left(\sqrt{2}+o(1)\right)k(n-1)$ must contain many lines of slope $1$. To
show that such a construction is unlikely to exist, it might be helpful to
consider what happens if we restrict ourselves to lines of slope $0$,
$\infty$, $-1$, and $1$.

In our work thus far we observed that the standard grid $\Gamma_{n}$ requires
many fewer lines to cover than any other $n\times n$ grid we considered. Our
general lower bound from 1.3(b) (and the improvement for grids in which
$(0,0)$ is a corner discussed after the proof) is not strong enough to
establish this fact, and we propose the following problem.

######  Question 5.3.

Is it true that
$\operatorname{cov}_{k}(\Gamma_{n})\leq\operatorname{cov}_{k}(\Gamma)$ for any
$n\times n$ grid $\Gamma$ in which $(0,0)$ is a corner?

More broadly, it would be of interest to improve the lower bound from 1.3(b),
which we do not believe to be best possible.

Another direction that might lead to interesting findings is to consider
translates of the standard grid in which the omitted point is not in the
lower-left corner. How does the position of the origin then affect the value
of $\operatorname{cov}_{k}(\Gamma)$? For instance, what are the asymptotics of
$\operatorname{cov}_{k}(\Gamma)$, where $\Gamma=\Gamma(\\{-\lfloor
n/2\rfloor,\dots,\lceil n/2\rceil\\},\\{-\lfloor n/2\rfloor,\dots,\lceil
n/2\rceil\\})$?

While we mainly focused on two-dimensional real grids, it would be natural to
investigate the problem in higher dimensions as well. For example, in Section
3, we remarked that the Ball–Serra bound can be tight for higher-dimensional
grids as well, provided that one of the sides is much longer than the others.
How much longer does that side need to be for the bound to be attained? Some
first results in this direction were shown in the bachelor’s thesis of the
fourth author [14]. Once again, it would be particularly interesting to
investigate $\operatorname{cov}_{k}(\Gamma_{n}^{(d)})$ for the standard
$d$-dimensional grid $\Gamma_{n}^{(d)}=\\{0,\dots,n-1\\}^{d}$.

Finally, while all of our results are stated for grids over $\mathbb{R}$, the
questions we considered and our general framework extend to grids over any
field. Some of our results, for example Theorem 1.1, extend to arbitrary
fields. It will be interesting to prove similar results for other fields, and
in particular for fields of positive characteristic.

## References

  * [1] G. N. Alfarano, M. Borello and A. Ravagnani,  Three Combinatorial Perspectives on Minimal Codes,  SIAM J. on Discrete Math. 36(1), (2022), 461–489.
  * [2] N. Alon,  Combinatorial Nullstellensatz,  Combin. Probab. Comput. 8 (1999), 7–29.
  * [3] N. Alon and Z. Füredi,  Covering the cube by affine hyperplanes,  European J. Combin. 14(2) (1993), 79–83.
  * [4] S. Ball,  On intersection sets in Desarguesian affine spaces,  European J. Combin. 21(3) (2000), 441–446.
  * [5] S. Ball and O. Serra,  Punctured Combinatorial Nullstellensätze,  Combinatorica 29 (2009), 511–522.
  * [6] A. H. Beiler,  Recreations in the Theory of Numbers: The Queen of Mathematics Entertains,  New York: Dover, 1996.
  * [7] A. Bishnoi, P. L. Clark, A. Potukuchi and J. R. Schmitt,  On zeros of a polynomial in a finite grid,  Comb. Prob. Comput. 27(3) (2018), 310–333.
  * [8] A. Bishnoi, S. Boyadzhiyska, S. Das and T. Mészáros,  Subspace coverings with multiplicities,  arXiv preprint arXiv:2101.11947 (2021).
  * [9] A. Blokhuis, A. E. Brouwer and T. Szőnyi,  Covering all points except one,  J. Algebraic Comb. 32 (2010), 59-66.
  * [10] B. Bosek, J. Grytczuk, G. Gutowski, O. Serra and M. Zajac,  Graph polynomials and group coloring of graphs,  European J. Combin., 102, (2022), 103505.
  * [11] A. E. Brouwer and A. Schrijver,  The blocking number of an affine space,  J. Combin. Theory Ser. A 24(2) (1978), 251–253.
  * [12] A. A. Bruen,  Polynomial multiplicities over finite fields and intersection sets,  J. Combin. Theory Ser. A 60(1) (1992), 19-33.
  * [13] A. Clifton and H. Huang,  On almost $k$-covers of hypercubes,  Combinatorica 40 (2020), 511–526.
  * [14] Y. M. den Bakker,  Hyperplane covering problems,  Bachelor’s Thesis, Technische Universiteit Delft, (2021).
  * [15] S. Glock and D. Munhá Correia and B. Sudakov,  The $n$-queens completion problem,  Research in the Mathematical Sciences, 9(3) (2022). 1–20.
  * [16] L. Guth,  Polynomial methods in combinatorics, Vol. 64,  American Mathematical Soc., (2016).
  * [17] R. E. Jamison,  Covering finite fields with cosets of subspaces,  J. Combin. Theory Ser. A 22(3) (1977), 253–266.
  * [18] P. Komjáth,  Partitions of vector spaces,  Period. Math. Hungar. 28 (1994), 187–193.
  * [19] I. Landjev and A. Rousseva,  On the sharpness of Bruen’s bound for intersection sets in Desarguesian affine spaces,  Designs, codes and cryptography 72(3) (2014), 551–558.
  * [20] J. Matoušek and B. Gärtner,  Understanding and using linear programming,  Springer Berlin, Heidelberg (2007)
  * [21] L. Sauermann and Y. Wigderson,  Polynomials that vanish to high order on most of the hypercube,  J. London Math. Soc., t 106(3) (2022), 2379-2402.
  * [22] C. Zanella,  Intersection sets in $\mathrm{AG}(n,q)$ and a characterization of hyperbolic quadric in $\mathrm{PG}(3,q)$,  Discrete Math. 255 (2002), 381–386.


# A simple Havel–Hakimi type algorithm to realize graphical degree sequences
of directed graphs††thanks:  PLE was partly supported by OTKA (Hungarian NSF),
under contract Nos. AT048826 and K 68262. IM was supported by a Bolyai
postdoctoral stipend and OTKA (Hungarian NSF) grant F61730. ZT was supported
in part by the NSF BCS-0826958, HDTRA 201473-35045 and by Hungarian
Bioinformatics MTKD-CT-2006-042794 Marie Curie Host Fellowships for Transfer
of Knowledge.

Péter L. Erdős and István Miklós
A. Rényi Institute of Mathematics, Hungarian Academy of
Sciences, Budapest, PO Box 127, H-1364, Hungary
{elp}<EMAIL_ADDRESS>Zoltán Toroczkai
Interdisciplinary Center for Network Science and Applications
and Department of Physics University of Notre Dame
Notre Dame, IN, 46556, USA
<EMAIL_ADDRESS>
###### Abstract

One of the simplest ways to decide whether a given finite sequence of positive
integers can arise as the degree sequence of a simple graph is the greedy
algorithm of Havel and Hakimi. This note extends their approach to directed
graphs. It also studies cases of some simple forbidden edge-sets. Finally, it
proves a result which is useful to design an MCMC algorithm to find random
realizations of prescribed directed degree sequences.

AMS subject classification[2000]. 05C07 05C20 90B10 90C35
Keywords. network modeling; directed graphs; degree sequences; greedy
algorithm

##  1 Introduction

The systematic study of graphs (or more precisely the tlinear graphs, as it
was called in that time) began sometimes in the late forties, through seminal
works by P. Erdős, P. Turán, W.T. Tutte, and others. One problem which
received considerable attention was the existence of certain subgraphs of a
given graph. For example such subgraph could be a perfect matching in a (not
necessarily bipartite) graph, or a Hamiltonian cycle through all vertices,
etc. Generally these substructures are called factors. The first couple of
important results of this kind are due to W.T. Tutte who gave necessary and
sufficient conditions for the existence of 1-factors and $f$-factors.

In the case of complete graphs, the existence problem of such factors is
considerably easier. In particular, the existence problem of (sometimes
simple) undirected graphs with given degree sequences even admits simple
greedy algorithms for its solution.

Subsequently, the theory was extended for factor problems of directed graphs
as well, but the greedy type algorithm mentioned above, to the best knowledge
of the authors, is missing even today.

In this paper we fill this gap: after giving a short and comprehensive (but
definitely not exhausting) history of the $f$-factor problem (Section 2), we
describe a greedy algorithm to decide the existence of a directed simple graph
possessing the prescribed degree sequence (Section 3). In Section 4 we prove a
consequence of the previous existence theorem, which is a necessary ingredient
for the construction of edge-swap based Markov Chain Monte Carlo (MCMC)
methods to sample directed graphs with prescribed degree sequence. Finally in
Section 5 we discuss a slightly harder existence problem of directed graphs
with prescribed degree sequences where some vertex-pairs are excluded from the
constructions. This result can help to efficiently generate all possible
directed graphs with a given degree sequence.

##  2 A brief history (of $f$-factors)

For a given function $f:V(G)\rightarrow\mathbb{N}\cup\\{0\\}$, an $f$-factor
of a given simple graph $G(V,E)$ is a subgraph $H$ such that $d_{H}(v)=f(v)$
for all $v\in V.$ One of the very first key results of modern graph theory is
due to W.T. Tutte: in 1947 he gave a complete characterization of simple
graphs with an $f$-factor in case of $f\equiv 1$ (Tutte’s 1-factor theorem,
[14]). Tutte later solved the problem of the existence of $f$-factors for
general $f$’s (Tutte’s $f$-factor theorem, [15]). In 1954 he also found a
beautiful graph transformation to handle $f$-factor problems via perfect
matchings in bipartite graphs [16]. This also gave a clearly polynomial time
algorithm for finding $f$-factors.

In cases where $G$ is a complete graph, the $f$-factor problem becomes easier:
then we are simply interested in the existence of a graph with a given degree
sequence (the exact definitions will come in Section 3). In 1955 P. Havel
developed a simple greedy algorithm to solve the degree sequence problem for
simple undirected graphs ([8]). In 1960 P. Erdős and T. Gallai studied the
$f$-factor problem for the case of a complete graph $G$, and proved a simpler
Tutte-type result for the degree sequence problem (see [3]). As they already
pointed out, the result can be derived directly form the original $f$-factor
theorem, taking into consideration the special properties of the complete
graph $G$, but their proof was independent of Tutte’s proof and they referred
to Havel’s theorem.

In 1962 S.L. Hakimi studied the degree sequence problem in undirected graphs
with multiple edges ([6]). He developed an Erdős-Gallai type result for this
much simpler case, and for the case of simple graphs he rediscovered the
greedy algorithm of Havel. Since then this algorithm is referred to as the
Havel–Hakimi algorithm.

For directed graphs the analogous question of recognizability of a bi-
graphical-sequence comes naturally. In this case we are given two $n$-element
vectors $\mathbf{d^{+},d^{-}}$ of non-negative integers. The problem is the
existence of a directed graph on $n$ vertices, such that the first vector
represents the out-degrees and the second one the in-degrees of the vertices
in this graph. In 1957 D. Gale and H. J. Ryser independently solved this
problem for simple directed graphs (there are no parallel edges, but loops are
allowed), see [5, 13]. In 1958 C. Berge generalized these results for
$p$-graphs where at most $p$ parallel edges are allowed ([1]). (Berge calls
the out-degree and in-degree together the demi-degrees.) Finally in 1973, the
revised version of his book Graphs ([2]) gives a solution for the $p$-graph
problem, loops excluded. To show some of the afterlife of these results: D.
West in his renowned recent textbook ([17]), discusses the case of simple
directed graphs with loops allowed.

The analog of $f$-factor problems for directed graphs has a sparser history.
Øystein Ore started the systematic study of that question in 1956 (see [11,
12]). His method is rather algebraic, and the finite and infinite cases - more
or less - are discussed together. The first part developed the tools and
proved the directly analog result of Tutte’s $f$-factor problem for finite
directed graphs (with loops), while the second part dealt with the infinite
case.

In 1962 L.R. Ford and D.R. Fulkerson studied, generalized and solved the
“original” $f$-factor problem for a directed graph $\vec{G}$ ([4]). Here lower
and upper bounds were given for both demi-degrees of the desired subgraph (no
parallel edges, no loops) with the original question naturally corresponding
to equal lower and upper bounds. The solutions (as well as in Berge’s cases)
are based on network flow theory.

Finally, in a later paper Hakimi also proves results for bi-graphical
sequences, however, without presenting a directed version of his original
greedy algorithm (see [7]).

##  3 A greedy algorithm to realize bi-graphical sequences

A sequence $\mathbf{d}=\\{d_{1},d_{2},\ldots,d_{n}\\}$ of nonnegative integers
is called a graphical sequence if a simple graph $G(V,E)$ exists on $n$ nodes,
$V=\\{v_{1},v_{2},\ldots,v_{n}\\}$, whose degree sequence is $\mathbf{d}$. In
this case we say that $G$ realizes the sequence $\mathbf{d}$. For simplicity
of the notation we will consider only sequences of strictly positive integers
($d_{n}>0$) to avoid isolated points. The following, well-known result, was
proved independently by V. Havel and S.L. Hakimi.

######  Theorem 1 (Havel [8], Hakimi [6])

There exists a simple graph with degree sequence $d_{1}>0,$
$d_{2}\geq\cdots\geq d_{n}>0$ ($n\geq 3$) if and only if there exists one with
degree sequence $d_{2}-1,\ldots,d_{d_{1}+1}-1,d_{d_{1}+2},\ldots,d_{n}$. (Note
that there is no prescribed ordering relation between $d_{1}$ and the other
degrees.)

This can be proved using a recursive procedure, which transforms any
realization of the degree sequence into the form described in the Theorem 1,
by a sequence of two-edge swaps.

A bi-degree-sequence (or BDS for short)
$\mathbf{(d^{+},d^{-})}=(\\{d^{+}_{1},d^{+}_{2},\ldots,d^{+}_{n}\\},\\{d^{-}_{1},d^{-}_{2},$
$\ldots,d^{-}_{n}\\})$ of nonnegative integers is called a bi-graphical
sequence if there exists a simple directed graph (digraph)
$\vec{G}(V,\vec{E})$ on $n$ nodes, $V=\\{v_{1},v_{2},\ldots,v_{n}\\}$, such
that the out-degree and in-degree sequences together form
$\mathbf{(d^{+},d^{-})}$. (That is the out-degree of vertex $v_{j}$ is
$d^{+}_{j}$ and its in-degree is $d^{-}_{j}.$) In this case we say that
$\vec{G}$ realizes our BDS. For simplicity, we will consider only sequences of
strictly positive integer BDS’s, that is each degree is $\geq 0$ and
$d^{+}_{j}+d^{-}_{j}>0$, to avoid isolated points.

Our goal is to prove a Havel–Hakimi type algorithm to realize bi-graphical
sequences. To that end we introduce the notion of normal order: we say that
the BDS is in normal order if the entries satisfy the following properties:
for each $i=1,\ldots,n-2$ we either have $d^{-}_{i}>d^{-}_{i+1}$ or
$d^{-}_{i}=d^{-}_{i+1}$ and $d^{+}_{i}\geq d^{+}_{i+1}$. Clearly, all BDS-s
can be arranged into normal order. Note that we made no ordering assumption
about node $v_{n}$ (the pair $d^{+}_{n},d^{-}_{n}$).

###### Theorem 2

Assume that the BDS $\mathbf{(d^{+},d^{-})}$ $($with $d^{+}_{j}+d^{-}_{j}>0$,
$j\in[1,n])$ is in normal order and $d_{n}^{+}>0$ (recall: the out-degree of
the last vertex is positive). Then $\mathbf{(d^{+},d^{-})}$ is bi-graphical if
and only if the BDS

$\displaystyle\Delta^{+}_{k}=\left\\{\begin{array}[]{lll}d^{+}_{k}&\quad\mbox{if
}&k\neq n\\\ 0&\quad\mbox{if}&k=n\;,\end{array}\right.$ (3)
$\displaystyle\Delta^{-}_{k}=\left\\{\begin{array}[]{lll}d^{-}_{k}-1&\quad\mbox{if
}&k\leq d^{+}_{n}\\\ d^{-}_{k}&\quad\mbox{if
}&k>d^{+}_{n}\;\;\;,\end{array}\right.$ (6)

with zero elements removed (those $j$ for which
$\Delta^{+}_{j}=\Delta^{-}_{j}=0$) is bi-graphical.

Before starting the proof, we emphasize the similarity between this result and
the original HH-algorithm. As in the undirected case, using Theorem 2, we can
find in a greedy way a proper realization of graphical bi-degree sequences.

Indeed: choose any vertex $v_{n}$ with non-zero out-degree from the sequence,
arrange the rest in normal order, then make $d_{n}^{-}$ connections from
$v_{n}$ to nodes with largest in-degrees, thus constructing the out-
neighborhood of $v_{n}$ in the (final) realization. Next, remove the vertices
(if any) from the remaining sequence that have lost both their in- and out-
degrees in the process, pick a node with non-zero out-degree, then arrange the
rest in normal order. Applying Theorem 2 again, we find the final out-
neighborhood of our second chosen vertex. Step by step we find this way the
out-neighborhood of all vertices, while their in-neighborhoods get defined
eventually (being exhausted by incoming edges). Note, that every vertex in
this process is picked at most once, namely, when its out-neighborhood is
determined by the Theorem, and never again after that.

Our forthcoming proof is not the simplest, however, we use a more general
setup to shorten the proofs of later results.

First, we define the partial order $\preceq$ among $k$-element vectors of
increasing positive integers: we say $\mathbf{a}\preceq\mathbf{b}$ iff for
each $j=1,\ldots,k$ we have $a_{j}\leq b_{j}.$

A possible out-neighborhood (or PON for short) of vertex $v_{n}$ is a
$d^{+}_{n}$-element subset of $V\setminus\\{v_{n}\\}$ which is a candidate for
an out-neighborhood of $v_{n}$ in some graphical representation. (In essence,
a PON can be any $d^{+}_{n}$-element subset of $V\setminus\\{v_{n}\\}$ but
later on we may consider some restrictions on it.) Let $A$ be a PON of
$v_{n}.$ Then denote by $\bm{i}(A)$ the vector of the increasingly ordered
subscripts of the elements of $A$. (For example, if
$A=\\{v_{2},v_{4},v_{9}\\}$, then $\bm{i}(A)=(2,4,9)$.) Let $A$ and $B$ be two
PONs of $v_{n}.$ We write:

$B\preceq A\quad\Leftrightarrow\quad\bm{i}_{B}\preceq\bm{i}_{A}\;.$ (7)

In this case we also say that $B$ is to the left of $A$. (For example,
$B=\\{v_{1},v_{2},v_{6},v_{7}\\}$ is to the left of
$A=\\{v_{2},v_{4},v_{6},v_{9}\\}$.)

###### Definition 3

Consider a bi-graphical BDS sequence $(\mathbf{d^{+},d^{-}})$ and let $A$ be a
PON of $v_{n}$. The $A$-reduced BDS
$\left(\mathbf{d^{+}}\big{|}_{A},\mathbf{d^{-}}\big{|}_{A}\right)$ is defined
as:

$\displaystyle d^{+}_{k}\big{|}_{A}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{lll}d^{+}_{k}&\quad\mbox{if }&k\neq n\\\
0&\quad\mbox{if}&k=n\;,\end{array}\right.$ (10) $\displaystyle
d^{-}_{k}\big{|}_{A}$ $\displaystyle=$
$\displaystyle\left\\{\begin{array}[]{lll}d^{-}_{k}-1&\quad\mbox{if
}&k\in\bm{i}(A)\\\ d^{-}_{k}&\quad\mbox{if
}&k\not\in\bm{i}(A).\end{array}\right.$ (13)

In other words, if $A$ is a PON in a BDS, then the reduced degree sequence
$\left(\mathbf{d^{+}}\big{|}_{A},\mathbf{d^{-}}\big{|}_{A}\right)$ is obtained
by removing the out-edges of node $v_{n}$ (according to the possible out-
neighborhood $A$). As usual, if for one subscript $k$ in the $A$-reduced BDS
we have $d^{+}_{k}\big{|}_{A}=d^{-}_{k}\big{|}_{A}=0$ then the vertex with
this index is to be removed from the bi-degree sequence.

###### Lemma 4

Let $(\mathbf{d^{+},d^{-}})$ be a BDS, and let $A$ be a possible out-
neighborhood of $v_{n}.$ Furthermore let $B$ be another PON with
$B=A\setminus\\{v_{k}\\}\cup\\{v_{i}\\}$ where $d^{-}_{i}\geq d^{-}_{k}$ and
in case of $d^{-}_{i}=d^{-}_{k}$ we have $d^{+}_{i}\geq d^{+}_{k}.$ Then if
$\mathbf{(D^{+},D^{-})}:=\left(\mathbf{d^{+}}\big{|}_{A},\mathbf{d^{-}}\big{|}_{A}\right)$
is bi-graphical, so is
$\left(\mathbf{d^{+}}\big{|}_{B},\mathbf{d^{-}}\big{|}_{B}\right)$.

Proof. Since our $A$-reduced BDS $\mathbf{(D^{+},D^{-})}$ is bi-graphical,
there exists a directed graph $\vec{G}$ which realizes the bi-degree sequence
$\mathbf{(D^{+},D^{-})}$. We are going to show that in this case there exists
a directed graph $\vec{G}^{\prime}$ which realizes the BDS
$\left(\mathbf{d^{+}}\big{|}_{B},\mathbf{d^{-}}\big{|}_{B}\right)$. In the
following, $v_{a}v_{b}$ will always mean a directed edge from node $v_{a}$ to
node $v_{b}$. Let us now construct the directed graph $\vec{G}_{1}$ by adding
$v_{n}v$ directed edges for each $v\in A.$ (Since according to (10), in
$\mathbf{(D^{+},D^{-})}$ the out-degree of $v_{n}$ is equal to zero, no
parallel edges are created.) The bi-degree-sequence of $\vec{G}_{1}$ is
$(\mathbf{d^{+},d^{-}}).$ Our goal is to construct another realization
$\vec{G}_{1}^{\prime}$ of $(\mathbf{d^{+},d^{-}})$ such that the deletion of
the out-edges of $v_{n}$ in the latter produces the BDS
$\left(\mathbf{d^{+}}\big{|}_{B},\mathbf{d^{-}}\big{|}_{B}\right)$.

By definition we have $v_{n}v_{k}\in\vec{E}_{1},$ (the edge set of
$\vec{G}_{1}$) but $v_{n}v_{i}\not\in\vec{E}_{1}$. At first assume that there
exists a vertex $v_{\ell}$ ($\ell\neq i,k,n$), such that
$v_{\ell}v_{i}\in\vec{E}_{1}$ but $v_{\ell}v_{k}\not\in\vec{E}_{1}$. (When
$d^{-}_{i}>d^{-}_{k}$ then this happens automatically, however if
$d^{-}_{i}=d^{-}_{k}$ and $v_{k}v_{i}\in\vec{E}_{1}$ then it is possible that
the in-neighborhood of $v_{i}$ and $v_{k}$ are the same - except of course
$v_{k}$, $v_{i}$ themselves and $v_{n}$.) This means that now we can swap the
edges $v_{n}v_{k}$ and $v_{\ell}v_{i}$ into $v_{n}v_{i}$ and $v_{\ell}v_{k}$.
(Formally we create the new graph
$\vec{G}_{1}^{\prime}=(V,\vec{E}_{1}^{\prime})$ such that
$\vec{E}_{1}^{\prime}=\vec{E}_{1}\setminus\\{v_{n}v_{k},v_{\ell}v_{i}\\}\cup\\{v_{n}v_{i},v_{\ell}v_{k}\\}.$)
This achieves our wanted realization.

Our second case is when $d^{-}_{i}=d^{-}_{k},$ $v_{k}v_{i}\in\vec{E}_{1}$, and
furthermore

$\mbox{for each }\ell\neq i,k,n\quad\mbox{we have}\quad
v_{\ell}v_{i}\in\vec{E}_{1}\Leftrightarrow v_{\ell}v_{k}\in\vec{E}_{1}.$ (14)

It is important to observe that in this case $v_{i}v_{k}\not\in\vec{E}_{1}:$
otherwise some $v_{\ell}$ would not satisfy (14) (in order to keep
$d^{-}_{i}=d^{-}_{k}$).

Now, if there exists a subscript $m$ (different from $k,i,n$) such that
$v_{i}v_{m}\in\vec{E}_{1}$ but $v_{k}v_{m}\not\in\vec{E}_{1},$ then we create
the required new graph $\vec{G}_{1}^{\prime}$ by applying the following triple
swap (or three-edge swap): we exchange the directed edges
$v_{n}v_{k},v_{k}v_{i}$ and $v_{i}v_{m}$ into $v_{n}v_{i},v_{i}v_{k}$ and
$v_{k}v_{m}$.

By our assumption we have $d^{+}_{i}\geq d^{+}_{k}$. On one hand side if
$d^{+}_{i}>d^{+}_{k}$ holds then due to the properties $v_{k}v_{i}\in\vec{E}$
and $v_{i}v_{k}\not\in\vec{E},$ there exist at least two subscripts
$m_{1},m_{2}\neq i,k$ such that $v_{i}v_{m_{j}}\in\vec{E}$ but
$v_{k}v_{m_{j}}\not\in\vec{E}$ and at least one of them differs from $n$.
Thus, when $d^{+}_{i}>d^{+}_{k}$, we do find such an $m$ for which the triple
swap above can be performed.

The final case is when $d^{-}_{i}=d^{-}_{k}$ and $d^{+}_{i}=d^{+}_{k}$. If
vertex $v_{m}$ does not exist, then we must have $v_{i}v_{n}\in\vec{E}_{1}$
(to keep $d^{+}_{i}=d^{+}_{k}$), and in this case clearly,
$v_{k}v_{n}\notin\vec{E}_{1}$. Therefore, in this (final) case the graphical
realization $\vec{G}_{1}$ has the properties
$v_{n}v_{k},v_{k}v_{i},v_{i}v_{n}\in\vec{E}_{1}$ and
$v_{n}v_{i},v_{i}v_{k},v_{k}v_{n}\not\in\vec{E}_{1}$. Then the triple swap

$\vec{E}_{1}^{\prime}:=\vec{E}_{1}\setminus\left\\{v_{n}v_{k},v_{k}v_{i},v_{i}v_{n}\right\\}\cup\left\\{v_{n}v_{i},v_{i}v_{k},v_{k}v_{n}\right\\}$
(15)

will produce the required new graphical realization $\vec{G}_{1}^{\prime}$.
$\Box$

###### Observation 5

For later reference it is important to recognize that in all cases above, the
transformations from one realization to the next one happened with the use of
two-edge or three-edge swaps.

###### Lemma 6

Let $(\mathbf{d^{+},d^{-}})$ be an BDS and let $A$ and $C$ be two possible
out-neighborhoods of $v_{n}.$ Furthermore assume that $C\preceq A$, that is
$C$ is to the left of $A$. Finally assume that vertices in $A\cup C$ are in
normal order. Then if
$\left(\mathbf{d^{+}}\big{|}_{A},\mathbf{d^{-}}\big{|}_{A}\right)$ is bi-
graphical, so is
$\left(\mathbf{d^{+}}\big{|}_{C},\mathbf{d^{-}}\big{|}_{C}\right)$.

Proof. Since $C$ is to the left of $A$ therefore, there is a (unique)
bijection $\phi:C\setminus A\rightarrow A\setminus C$ such that $\forall c\in
C\setminus A$ : $\bm{i}(\\{c\\})<\bm{i}(\\{\phi(c)\\})$ (the subscript of
vertex $c$ is smaller than the subscript of vertex $\phi(c)$). (For example,
if $A=\\{v_{4},v_{5},v_{6},v_{7},v_{8},v_{9}\\}$ and
$C=\\{v_{1},v_{2},v_{3},v_{5},v_{7},v_{8}\\}$, then $C\setminus
A=\\{v_{1},v_{2},v_{3}\\}$, $A\setminus C=\\{v_{4},v_{6},v_{9}\\}$, and $\phi$
is the map $\\{v_{1}\leftrightarrow v_{4},v_{2}\leftrightarrow
v_{6},v_{3}\leftrightarrow v_{9}\\}$).

To prove Lemma 6 we apply Lemma 4 recursively for each $c\in C\setminus A$ (in
arbitrary order) to exchange $\phi(c)\in A$ with $c\in C$, preserving the
graphical character at every step. After the last step we find that the
sequence reduced by $C$ is graphical. $\Box$

Proof of Theorem 2: We can easily achieve now the required graphical
realization of $(\mathbf{d^{+},d^{-}})$ if we use Lemma 6 with the current
$A$, and $C=\\{v_{1},\ldots,v_{d^{+}_{n}}\\}.$ We can do that since
$(\mathbf{d^{+},d^{-}})$ is in normal order, therefore the assumptions of
Lemma 6 always hold. $\Box$

##  4 A simple prerequisite for MCMC algorithms to sample directed graphs with
given BDS

In practice it is often useful to choose uniformly a random element from a set
of objects. A frequently used tool for that task is a well-chosen Markov-Chain
Monte-Carlo method (MCMC for short). To that end, a graph is established on
the objects and random walks are generated on it. The edges represent
operations which can transfer one object to the other. If the Markov chain can
step from an object $x$ to object $y$ with non-zero probability, then it must
be able to jump to $x$ from $y$ with non-zero probability (reversibility). If
the graph is connected, then applying the well-known Metropolis-Hastings
algorithm, it will yield a random walk converging to the uniform distribution
starting from an arbitrary (even fixed) object.

To be able to apply this technique we have to define our graph (the Markov
chain) $\mathcal{G}(\mathbf{d^{+}},\mathbf{d^{-}})=(\mathcal{V},\mathcal{E})$.
The vertices are the different possible realizations of the bi-graphical
sequence $(\mathbf{d^{+}},\mathbf{d^{-}}).$ An edge represents an operation
consisting of a two or three-edge swap which transforms the first realization
into the second one. (For simplicity, sometimes we just say swap for any of
them.) We will show:

###### Theorem 7

Let $\vec{G}_{1},\vec{G}_{2}$ be two realizations of the same bi-graphical
sequence $(\mathbf{d^{+}},\mathbf{d^{-}}).$ Then there exists a sequence of
swaps which transforms $\vec{G}_{1}$ into $\vec{G}_{2}$ through different
realizations of the same bi-graphical sequence.

Remark: In the case of undirected graphs the (original) analogous observation
(needing only two-edges swaps) was proved by H.J. Ryser ([13]).

Proof. We prove the following stronger statement:

  * (✠)

there exists a sequence of at most $2e$ swaps which transform $\vec{G}_{1}$
into $\vec{G}_{2}$, where $e$ is the total number of out-edges in
$(\mathbf{d^{+}},\mathbf{d^{-}})$

by induction on $e$. Assume that $(\maltese)$ holds for $e^{\prime}<e$. We can
assume that our bi-graphical sequence is in normal order on the first $n-1$
vertices and $d^{+}_{n}>0.$ By Theorem 2 there is a sequence $T_{1}$ ($T_{2}$)
of $d=d^{+}_{n}$ many swaps which transforms $\vec{G}_{1}$ ($\vec{G}_{2}$)
into a $\vec{G}^{\prime}_{1}$ ($\vec{G}^{\prime}_{2}$) such that
$\Gamma^{+}_{\vec{G}_{1}^{\prime}}(v_{n})=\\{v_{1},\dots,v_{d}\\}$
($\Gamma^{+}_{\vec{G}_{2}^{\prime}}(v_{n})=\\{v_{1},\dots,v_{d}\\}$).

We consider now the directed graphs $\vec{G}_{1}^{\prime\prime}$
($\vec{G}_{2}^{\prime}$) derived from directed graph $\vec{G}_{1}^{\prime}$
(directed graph $\vec{G}_{2}^{\prime}$) by deleting all out-neighbors of
$v_{n}.$ Then both directed graphs realize the bi-graphical sequence
$(\Delta^{+},\Delta^{-})$ which, in turn, satisfies relations (3) and (6).
Therefore the total number of out-degrees is $e-d$ in both directed graphs,
and by the inductive assumption there is a sequence $T$ of $2(e-d)$ many swaps
which transforms $\vec{G}^{\prime\prime}_{1}$ into
$\vec{G}_{2}^{\prime\prime}$.

Now observe that if a swap transforms $\vec{H}$ into $\vec{H}^{\prime}$, then
the “inverse swap” (choosing the same edges and non-edges and swap them)
transforms $\vec{H}^{\prime}$ into $\vec{H}$. So the swap sequence $T_{2}$ has
an inverse $T_{2}^{\prime}$ which transforms $\vec{G}_{2}^{\prime}$ into
$\vec{G}_{2}$. Hence the sequence $T_{1}TT_{2}^{\prime}$ is the required swap
sequence: it transforms $\vec{G}_{1}$ into $\vec{G}_{2}$ and its length is at
most $d+2(e-d)+d=2e$. $\Box$

##  5 Is a BDS bi-graphical when one of its vertex’s out-neighborhood is
constrained?

In network modeling of complex systems (for a rather general reference see
[10]) one usually defines a (di)graph with components of the system being
represented by the nodes, and the interactions (usually directed) amongst the
components being represented as the edges of this digraph. Typical cases
include biological networks, such as the metabolic network, signal
transduction networks, gene transcription networks, etc. The graph is usually
inferred from empirical observations of the system and it is uniquely
determined if one can specify all the connections in the graph. Frequently,
however, the data available from the system is incomplete, and one cannot
uniquely determine this graph. In this case there will be a set
${\mathcal{D}}$ of (di)graphs satisfying the existing data, and one can be
faced with:

  1. (i)

finding a typical element of the class ${\mathcal{D}},$

  2. (ii)

or generating all elements of the class ${\mathcal{D}}$.

(A more complete analysis of this phenomenon can be found in [9].) In Section
4 we already touched upon problem (i) when ${\mathcal{D}}$ is the class of all
directed graphs of a given BDS. The analogous Problem (ii) for undirected
graphs was recently addressed in [9] which provides an economical way of
constructing all elements from ${\mathcal{D}}$. In this Section we give a
prescription based on the method from [9], to solve (ii) for the case of all
directed graphs with prescribed BDS. This is particularly useful from the
point of view of studying the abundance of motifs in real-world networks: one
needs to know first all the (small) subgraphs, or motifs, before we study
their statistics from the data.

Before we give the details, it is perhaps worth making the following remark:
Clearly, one way to solve problem (i) would be to first solve problem (ii),
then choose uniformly from ${\mathcal{D}}$. However, in (those very small)
cases when reasonable answers can be expected for problem (ii), problem (i) is
rather uninteresting. In general, however, (i) cannot be solved efficiently by
the use of (ii).

We start the discussion of problem (ii) with pointing out that our new,
directed Havel–Hakimi type algorithm is unable to generate all realization of
a prescribed DBS (see Figure 1).

Figure 1: This graph cannot be obtained by the directed Havel–Hakimi
procedure. The integers indicate node degrees.

The situation is very similar to the non-directed case, see [9]. The directed
HH-algorithm must start with a vertex with degree-pair $(2,1)$, therefore the
two vertices of degree-pair $(0,3)$ must be out-neighbors of the same vertex -
not for the graph in the Figure.

One possible way to overstep this shortage is to discover systematically all
possible out-connections from a given vertex $v$ in all realizations of the
prescribed graphical BDS.

We do not know a greedy algorithm to achieve this. The next best thing we can
do is to develop a greedy algorithm to decide whether a given (sub)set of
prescribed out-neighbors of $v$ would prevent to find a realization of the BDS
containing those prescribed out-neighbors. In the following, we describe such
a greedy algorithm. (It is perhaps interesting to note that this latter
problem can be considered as a very special directed $f$-factor problem.)

To start, we consider a $\mathbf{(d^{+},d^{-})}$ bi-degree sequence together
with a forbidden vertex set $F$ whose elements are not allowed to be out-
neighbors of vertex $v_{n}.$ (Or, just oppositely, we can imagine that we
already have decided that those vertices will become out-neighbors of $v_{n}$
and the BDS is already updated accordingly. The forbidden vertex set governs
only the out-neighbors, since in the process the in-neighbors are born
“automatically”.) It is clear that $|F|+1+d^{-}_{n}\leq n$ must hold for the
existence of a graphical realization of this $F$-restricted BDS.

Assume that the vertices are enumerated in such a way that subset $F$ consists
of vertices $v_{n-|F|},\ldots,v_{n-1}$ and vertices
$V^{\prime}=\\{v_{1},\ldots,v_{n-|F|-1}\\}$ are in normal order. (We can also
say that we apply a permutation on the subscripts accordingly.) Then we say
that the BDS is in $F$-normal order.

###### Definition 8

Consider a bi-graphical BDS sequence $(\mathbf{d^{+},d^{-}})$ in $F$-normal
order, and let $A$ be a PON. The $A$-reduced BDS
$\left(\mathbf{d^{+}}\big{|}_{A},\mathbf{d^{-}}\big{|}_{A}\right)$ is defined
as in (10) and (13), while keeping in mind the existence of an $F$ set to the
right of $A$.

In other words, if $A$ is a PON in an $F$-restricted BDS, then the reduced
degree sequence
$\left(\mathbf{d^{+}}\big{|}_{A},\mathbf{d^{-}}\big{|}_{A}\right)$ is still
obtained by removing the out-edges of node $v_{n}$ (according to the possible
out-neighborhood $A$).

Finally, one more notation: let $(\mathbf{d^{+},d^{-}})$ be a BDS, $F$ a
forbidden vertex subset of $V$ and denote by $F[k]$ the set of the first $k$
vertices in the $F$-normal order.

###### Theorem 9

Let $A$ be any PON in the $F$-restricted $(\mathbf{d^{+},d^{-}})$ BDS, which
is in $F$-normal order. Then if the $A$-reduced BDS
$\left(\mathbf{d^{+}}\big{|}_{A},\mathbf{d^{-}}\big{|}_{A}\right)$ is
graphical, then the $F[d^{+}_{n}]$-reduced BDS
$\left(\mathbf{d^{+}}\big{|}_{F[d^{+}_{n}]},\mathbf{d^{-}}\big{|}_{F[d^{+}_{n}]}\right)$
is graphical as well.

Proof. It is immediate: Lemma 6 applies. $\Box$

This statement gives us indeed a greedy way to check whether there exists a
graphical realization of the $F$-restricted bi-degree sequence
$(\mathbf{d^{+},d^{-}})$: all we have to do is to check only whether the
$F[d^{+}_{n}]$-reduced BDS
$\left(\mathbf{d^{+}}\big{|}_{F[d^{+}_{n}]},\mathbf{d^{-}}\big{|}_{F[d^{+}_{n}]}\right)$
is graphical.

Finally, we want to remark that, similarly to the indirected case, Theorem 9
is suitable to speed up the generation of all possible graphical realizations
of a BDS. The details can be found in [9] which is a joint work of these
authors with Hyunju Kim and László A. Székely.

### Acknowledgements

The authors acknowledge useful discussions with Gábor Tusnády, Éva Czabarka
and László A. Székely and Hyunju Kim. ZT would also like to thank for the kind
hospitality extended to him at the Alfréd Rényi Institute of Mathematics,
where this work was completed. Finally we want to express our gratitude to
Antal Iványi for his editorial help.

## References

  * [1] C. Berge: The Theory of Graphs, Methuen & Co Ltd. London (1962), Chapter 9.
  * [2] C. Berge: Graphs and Hypergraphs, North Holland Pub. Company, Amsterdam (1973), Chapter 6.
  * [3] P. Erdős - T. Gallai: Gráfok előírt fokú pontokkal (Graphs with prescribed degree of vertices), Mat. Lapok, 11 (1960), 264–274. (in Hungarian)
  * [4] L.R. Ford - D.R. Fulkerson: Flows in Networks, RAND Corporation R-375-PR (1962) Chapter 2 Section 11.
  * [5] D. Gale: A theorem on flows in networks, Pacific J. Math. 7 (2) (1957), 1073–1082.
  * [6] S.L. Hakimi: On the realizability of a set of integers as degrees of the vertices of a simple graph. J. SIAM Appl. Math. 10 (1962), 496–506.
  * [7] S.L. Hakimi: On the degrees of the vertices of a directed graph, J. Franklin Institute 279 (4) (1965), 290–308.
  * [8] V. Havel: A remark on the existence of finite graphs. (Czech), Časopis Pěst. Mat. 80 (1955), 477–480.
  * [9] Hyunju Kim - Z. Toroczkai - P.L. Erdős - I. Miklós - L.A. Székely: Degree-based graph construction, submitted Journal of Physics A (2009), 1–12.
  * [10] M.E.J. Newman - A.L. Barabási - D.J. Watts: The Structure and Dynamics of Networks (Princeton Studies in Complexity, Princeton UP) (2006), 624 pp.
  * [11] Ø. Ore: Studies on directed graphs, I, Annals of Math. (Second Series) 63 (3) (1956), 383–406.
  * [12] Ø. Ore: Studies on directed graphs, II, Annals of Math. (Second Series) 64 (3) (1956), 142–153.
  * [13] H.J. Ryser: Combinatorial properties of matrices of zeros and ones, Canad. J. Math. 9 (1957), 371–377.
  * [14] W.T. Tutte: The factorization of linear graphs, J. London Math. Soc. 22 (1947), 107–111.
  * [15] W.T. Tutte: The factors of graphs, Canad. J. Math. 4 (1952), 314–328.
  * [16] W.T. Tutte: A short proof of the factors theorem for finite graphs, Canad. J. Math. 6 (1954), 347–352.
  * [17] D.B. West: Introduction to Graph Theory, Prentice Hall, Upper Sadle River, US, (2001), Section 1.4.