# Incidence-free sets and edge domination in incidence graphs

Sam Spiro111The ordering of the authors is done for purely aesthetic reasons
and is independent of the significance of each of their contributions to this
paper. 222Department of Mathematics, Rutgers University, Piscataway, NJ 08854.
<EMAIL_ADDRESS>This material is based upon work supported by
the National Science Foundation Mathematical Sciences Postdoctoral Research
Fellowship under Grant No. DMS-2202730 Sam Adriaensen Sam Mattheus Department
of Mathematics and Data Science, Vrije Universiteit Brussel, Pleinlaan 2 1050
Brussels, Belgium<EMAIL_ADDRESS>of Mathematics, University
of California, San Diego, La Jolla, CA, 92093-0112<EMAIL_ADDRESS>
###### Abstract

A set of edges $\Gamma$ of a graph $G$ is an edge dominating set if every edge
of $G$ intersects at least one edge of $\Gamma$, and the edge domination
number $\gamma_{e}(G)$ is the smallest size of an edge dominating set.
Expanding on work of Laskar and Wallis, we study $\gamma_{e}(G)$ for graphs
$G$ which are the incidence graph of some incidence structure $D$, with an
emphasis on the case when $D$ is a symmetric design. In particular, we show in
this latter case that determining $\gamma_{e}(G)$ is equivalent to determining
the largest size of certain incidence-free sets of $D$. Throughout, we employ
a variety of combinatorial, probabilistic and geometric techniques,
supplemented with tools from spectral graph theory.

Keywords: edge domination, design, incidence structure, matching, incidence-
free sets.
MSC2020 Classification: 05B05, 05C70.

##  1 Introduction

Roughly speaking, the area of extremal combinatorics centres around problems
which ask how large or small a given combinatorial object can be under certain
restrictions. For example, Mantel’s theorem states that the maximum number of
edges of an $n$-vertex triangle-free graph is $\left\lfloor
n^{2}/4\right\rfloor$. In this paper, the extremal questions we consider are
domination-type problems, which roughly involves studying the minimum number
of vertices or edges one needs to “cover” a graph $G$. Below we recall the
basic definitions for domination, and we refer the interested reader to the
book by Haynes, Hedetniemi, and Slater [HHS98] for more on this subject.

A _dominating set_ in a graph $G=(V,E)$ is a set of vertices $S\subseteq V$
such that each vertex is either contained in $S$, or has a neighbour in $S$.
The size of the smallest dominating set is called the _domination number_ of
$G$ and is denoted as $\gamma(G)$. A large body of work is dedicated to
studying $\gamma(G)$ as well as its many variants such as roman domination
[CDJHH04] and total domination [HY13].

A related concept is an _edge dominating set_ in a graph $G=(V,E)$. This is a
subset $\Gamma\subseteq E$ of edges, such that for each edge $e\in E$, there
exists an edge $e^{\prime}\in\Gamma$ with $e^{\prime}\cap e\neq\emptyset$. We
note that this could be equivalently defined as a dominating set in the line
graph of $G$.

The _edge domination number_ of $G$ is defined as the size of the smallest
edge dominating set, and will be denoted by $\gamma_{e}(G)$. Again a large
body of work is dedicated to studying $\gamma_{e}(G)$, see for example [HK93,
YG80].

In this paper we study domination type problems for graphs which come from
incidence structures. An _incidence structure_ is a pair
$D=(\mathcal{P},\mathcal{B})$, such that $\mathcal{B}$ is a collection of
subsets of $\mathcal{P}$. We say that $P\in\mathcal{P}$ and $B\in\mathcal{B}$
are _incident_ if $P\in B$. The elements of $\mathcal{P}$ and $\mathcal{B}$
are called _points_ and _blocks_ respectively. We say that $D$ is of _type_
$(v,b,k,r,\lambda)$ if

  * •

$|\mathcal{P}|=v$, and $|\mathcal{B}|=b$,

  * •

every block is incident with $k$ points, every point is incident with $r$
blocks,

  * •

$\lambda\geq 1$ is the maximum number such that there exist two distinct
points $P$ and $Q$ which have $\lambda$ blocks incident with both $P$ and $Q$.

The convention $\lambda\geq 1$ is somewhat non-standard and is adopted to
exclude trivial incidence structures. From these conditions, we have $vr=bk$
and $(v-1)\lambda\geq r(k-1)$. If $v=b$ (which implies $r=k$), and if
$\lambda$ is also the maximum number of points incident with two distinct
blocks, then we call $D$ a _symmetric incidence structure_ , abbreviated SIS,
of type $(v,k,\lambda)$.

If any two distinct points of an incidence structure are incident with exactly
$\lambda$ blocks, then we call $D$ a $(v,k,\lambda)$-_design_ , and in this
case

$\displaystyle vr=bk,$ $\displaystyle(v-1)\lambda=r(k-1).$ (1)

Fisher’s inequality states that in this case we always have $v\leq b$. In case
of equality, i.e. if $D$ is a design with $v=b$, then any two blocks of $D$
intersect in exactly $\lambda$ points, and $D$ is called a _symmetric design_.
We refer the reader to [CD06] for proofs of these statements and other
background on designs.

The _incidence graph_ $I(D)$, also called the _Levi graph_ , of an incidence
structure $D=(\mathcal{P},\mathcal{B})$ is the bipartite graph with
bipartition $\mathcal{P}$ and $\mathcal{B}$, where a point $P$ and a block $B$
are adjacent if and only if they are incident.

It turns out that the problem of determining the domination number of $I(D)$
is closely related to studying the smallest blocking sets and covers in $D$.
Partially because of this, there have been several papers in recent years
investigating the domination number of incidence graphs of block designs and
other incidence structures. See, for example, [GRM14, TZC19] for incidence
graphs of designs, [HN17] for incidence graphs of projective planes, and
[HHL20] for incidence graphs of generalised quadrangles.

Some work for edge domination numbers of incidence graphs of projective planes
was done by Laskar and Wallis [LW99], but outside of this very little is known
about edge domination numbers of incidence graphs. Our goal for this paper is
to expand upon this literature by focusing on the following problem:

Given an incidence structure $D$, determine the edge domination number of its
incidence graph $I(D)$.

For convenience’s sake, we will denote this quantity by $\gamma_{e}(D)$
instead of $\gamma_{e}(I(D))$.

We prove a number of general bounds for $\gamma_{e}(D)$ for incidence
structures throughout this paper. We highlight one such result below, which
shows that for symmetric designs $D$, determining $\gamma_{e}(D)$ is
equivalent to determining the maximum size of certain incidence-free sets.

######  Definition 1.1.

Let $X\subseteq\mathcal{P}$ and $Y\subseteq\mathcal{B}$ be such that there are
no incidences between points in $X$ and blocks in $Y$. In this case the pair
$(X,Y)$ will be called _incidence-free_. If $|X|=|Y|$ we will say that the
pair is _equinumerous_ and refer to $|X|$ as its size.

We note that the problem of determining the size of large incidence-free
subsets of incidence structures is a well-studied problem, see for example
[DWSV12, MPS19, MW07, Sti13]. As such, the following connection to
$\gamma_{e}(D)$ and incidence-free sets is of particular interest.

######  Theorem 1.2.

Let $D=(\mathcal{P},\mathcal{B})$ be a symmetric $(v,k,\lambda)$-design with
$k\geq 100$. Then

$\gamma_{e}(D)=v-\alpha,$

where $\alpha$ is the maximum size of an equinumerous incidence-free pair
$(X,Y)$.

The bound $k\geq 100$ can easily be improved, but we do not optimise this
value since, in particular, Equation 1 implies there exist only a finite
number of symmetric $(v,k,\lambda)$-designs with $k<100$. It is easy to show
that 1.2 can not be strengthened to hold for arbitrary SIS’s, but a somewhat
analogous statement does hold if one assumes some extra mild conditions on an
SIS; see 5.8 for more on this.

###  1.1 Organisation

The rest of the paper is organised as follows. The first half of the paper is
dedicated to general techniques and results, with preliminaries established in
Section 2, lower bounds in Section 3, upper bounds in Section 4, and a proof
of 1.2 in Section 5.

The last half of the paper, Section 6, establishes bounds on specific classes
of incidence structures, both by applying results from the first half of the
paper and by utilising algebraic structures and symmetries particular to the
individual incidence structures. Some specific classes of designs we look at
include those coming from projective planes and Hadamard matrices, and in many
of these cases we establish asymptotically sharp bounds. Our examples cover
almost all known basic constructions of symmetric designs (see [CD06, Part II
Chapter 6.8]), with the notable exception of symmetric designs coming from
difference sets, as there seems to exist no uniform way of establishing
effective bounds in this case. The problem of solving this remaining case, as
well as a number of other open problems, is discussed in Section 7.

##  2 Preliminaries

The following key observation allows us to translate upper bounds for sizes of
incidence-free sets into lower bounds for $\gamma_{e}(D)$. This will be the
driving force behind almost all of the lower bounds throughout this paper.

######  Lemma 2.1.

If $D=(\mathcal{P},\mathcal{B})$ is an incidence structure with
$|\mathcal{P}|=v$ and $|\mathcal{B}|=b$, then there is an incidence-free set
$(X,Y)$ with $|X|\geq v-\gamma_{e}(D)$ and $|Y|\geq b-\gamma_{e}(D)$.

###### Proof.

Let $\Gamma$ be an edge dominating set of size $\gamma_{e}(D)$. Let
$X\subseteq\mathcal{P}$ denote the set of points which are not contained in
any edge of $\Gamma$, and similarly define $Y\subseteq\mathcal{B}$. Note that
$(X,Y)$ is incidence-free by definition of $\Gamma$ being an edge dominating
set. Since there are at most $|\Gamma|$ points of $\mathcal{P}$ in an edge of
$\Gamma$, we have

$|X|\geq|\mathcal{P}|-|\Gamma|=v-\gamma_{e}(D),$

and the same argument gives the desired bound for $Y$. ∎

To construct small edge dominating sets, we rely on matchings in $I(D)$.
Recall that a _matching_ in a graph $G=(V,E)$ is a subset $M\subseteq E$ such
that each vertex of $G$ lies in at most one edge of $M$. A matching is called
_maximal_ if it cannot be extended to a larger matching. It is not hard to see
that a matching is maximal if and only if it is an edge dominating set, and an
observation of Yannakakis and Gavril [YG80] implies that $\gamma_{e}(G)$ is
equal to the smallest size of a maximal matching of $G$.

We say that a matching $M$ of $G=(V,E)$ _covers_ a subset $S$ of vertices if
each element of $S$ is contained in an element of $M$. A _perfect matching_ is
a matching that covers all vertices exactly once. Note that perfect matchings
are maximal matchings and edge dominating sets. A standard but important fact
about matchings that we need is the following easy consequence of Hall’s
theorem, where we recall that a graph is biregular if it has a bipartition
$U\cup V$ such that every vertex within $U$ has the same degree and every
vertex within $V$ has the same degree.

######  Lemma 2.2.

If $G$ is a biregular graph with bipartition $U\cup V$ such that $|U|\leq|V|$,
then $G$ has a matching which covers $U$.

We can use this to show when a trivial upper bound on $\gamma_{e}(D)$ is tight
for designs.

######  Lemma 2.3.

If $D=(\mathcal{P},\mathcal{B})$ is an incidence structure with
$|\mathcal{P}|=v$, then

$\gamma_{e}(D)\leq v.$

If $D$ is a $(v,k,\lambda)$-design, then equality holds if and only if $r\geq
v$.

###### Proof.

To prove the upper bound, we can assume without loss of generality that every
point $P\in\mathcal{P}$ is incident to at least one block
$B_{p}\in\mathcal{B}$. Then $\left\\{(P,B_{P})\right\\}_{P\in\mathcal{P}}$ is
an edge dominating set of $I(D)$ of size $v$, which shows $\gamma_{e}(D)\leq
v$. From now on we suppose $D$ is a design.

First consider the case $r\geq v$. Let $\Gamma$ be a smallest edge dominating
set of $I(D)$. If every point in $\mathcal{P}$ is contained in an edge of
$\Gamma$, then $\gamma_{e}(D)=|\Gamma|\geq|\mathcal{P}|=v$. Thus we may assume
there exists some point $P$ not contained in an edge of $\Gamma$. Since
$\Gamma$ is an edge dominating set, this implies that all of the $r$ blocks
incident to $P$ are contained in an edge of $\Gamma$. Thus $\gamma_{e}(D)\geq
r\geq v$, proving the ‘if’ statement.

Now consider the case $r<v$, and let $\mathcal{B}_{P}$ denote the set of $r$
blocks incident to a point $P\in\mathcal{P}$. The incidence graph of
$(\mathcal{P}\setminus\left\\{P\right\\},\mathcal{B}_{P})$ is biregular, hence
it has a matching $\Gamma^{\prime}$ covering $\mathcal{B}_{P}$ by 2.2. Since
$|\Gamma^{\prime}|=r<v$, one can find a set of edges $\Gamma$ which contains
$\Gamma^{\prime}$ and is such that each point of
$\mathcal{P}\setminus\left\\{P\right\\}$ is contained in exactly one edge of
$\Gamma$ (namely, by arbitrarily adding to $\Gamma$ an edge containing each
point not covered by $\Gamma^{\prime}$). This is an edge dominating set of
size $v-1$, completing the proof of the if and only if statement. ∎

We note that the equality case of 2.3 partially motivates our focus on
studying symmetric incidence structures where the number of points is
comparable to the number of blocks. However, even in this setting the trivial
upper bound of 2.3 is often close to the true value. This is perhaps not too
surprising given that the incidence graphs of designs are ‘expanding’ in the
sense of Thomason [Tho89, Section 3.3]. Roughly speaking, this means that
small sets of points are incident with a relatively large number of blocks and
vice versa. This implies that edges are ‘well-spread’ and do not concentrate
on small sets of vertices. It is thus reasonable to think that in order to
dominate all edges, we need a fairly large number of them. This is indeed the
case as we will see.

##  3 Lower bounds

To start this section, we will give a lower bound on the number of blocks
incident with at least one point of a certain point set. For designs, this can
be done using eigenvalue techniques, as was done by Haemers [Hae95, Corollary
5.3]. We will revisit this idea in Section 6.3.

This same result can also be proved using simple counting techniques. Stinson
[Sti13, Theorem 3.1] and De Winter, Schillewaert, Verstraëte [DWSV12, Theorem
3] independently bound the largest number of non-incident points and blocks in
a projective plane. Later, Elvey Price, Adib Surani, Zhou [EPASZ18, Lemma 3]
gave a combinatorial proof for Haemers’ bound for symmetric designs. However,
their arguments can be generalised in a straightforward way to hold for all
incidence structures of type $(v,b,k,r,\lambda)$. For the sake of
completeness, we give such a proof.

######  Definition 3.1.

A _maximal arc (of order n)_ in an incidence structure of type
$(v,b,k,r,\lambda)$ is a non-empty set of points $S$ such that every block
intersects $S$ in either 0 or $n$ points, for some integer $n$. We call a
maximal arc _trivial_ if it consists of one point, all points, or the
complement of a block333The complement of a block $B$ is a maximal arc if and
only if every other block intersects $B$ in a constant number of points. This
is the case in symmetric designs..

Suppose that $D$ is a $(v,k,\lambda)$-design, and that $S$ is a maximal arc of
order $n$ in $D$. Fix a point $P\in S$. Then there are $r$ blocks incident to
$P$, each containing $n-1$ other points of $S$. Since each point of
$S\setminus\left\\{P\right\\}$ is incident with $\lambda$ blocks incident to
$P$, this implies that $|S|=1+r\frac{n-1}{\lambda}$, or equivalently that the
order of a maximal arc $S$ equals $1+\frac{|S|-1}{r}\lambda$.

Now take a point $Q\notin S$. Consider the set $\left\\{(P,B)\in
S\times\mathcal{B}\,\,||\,\,P,Q\in B\right\\}$. By performing a double count
on this set, we see that there are
$(1+r\frac{n-1}{\lambda})\frac{\lambda}{n}=r-\frac{r-\lambda}{n}$ blocks
incident with $Q$ containing $n$ points of $S$. So, if $T$ denotes the set of
blocks not incident with any point of $S$, then any point is incident with
either 0 or $\frac{r-\lambda}{n}$ blocks of $T$. We call $T$ the _dual arc_ of
$S$.

######  Lemma 3.2.

Let $D=(\mathcal{P},\mathcal{B})$ be an incidence structure of type
$(v,b,k,r,\lambda)$. For any set $S\subseteq\mathcal{P}$, there are at least
$\frac{r^{2}|S|}{r+(|S|-1)\lambda}$ blocks which intersect $S$. Equality holds
in designs if and only if $S$ is a maximal arc of order
$1+\frac{|S|-1}{r}\lambda$.

###### Proof.

Let $x$ be the number of blocks intersecting $S$, and let $n_{i}$ be the
number of blocks intersecting $S$ in exactly $i$ points. Then the so-called
standard equations tell us that

$\displaystyle\sum_{i>0}n_{i}=x,$ $\displaystyle\sum_{i>0}in_{i}=r|S|,$
$\displaystyle\sum_{i>0}i^{2}n_{i}\leq|S|(r+(|S|-1)\lambda),$

by performing a double count on $\left\\{(P,B)\in
S\times\mathcal{B}\,\,||\,\,P\in B\right\\}$ and $\left\\{(P,Q,B)\in S\times
S\times\mathcal{B}\,\,||\,\,P,Q\in B\right\\}$. Using these equations we find

$\displaystyle 0$
$\displaystyle\leq\sum_{i>0}\left(i-\left(1+\frac{|S|-1}{r}\lambda\right)\right)^{2}n_{i}$
$\displaystyle=\sum_{i>0}i^{2}n_{i}-2\left(1+\frac{|S|-1}{r}\lambda\right)\sum_{i>0}in_{i}+\left(1+\frac{|S|-1}{r}\lambda\right)^{2}\sum_{i>0}n_{i}$
$\displaystyle\leq|S|(r+(|S|-1)\lambda)-2\left(1+\frac{|S|-1}{r}\lambda\right)r|S|+\left(1+\frac{|S|-1}{r}\lambda\right)^{2}x$
$\displaystyle\iff$
$\displaystyle\left(1+\frac{|S|-1}{r}\lambda\right)^{2}x\geq
2\left(1+\frac{|S|-1}{r}\lambda\right)r|S|-|S|(r+(|S|-1)\lambda)$
$\displaystyle\iff$
$\displaystyle\,\,x\geq\frac{r|S|}{1+\frac{|S|-1}{r}\lambda}=\frac{r^{2}|S|}{r+(|S|-1)\lambda}.$

Equality holds if and only if $n_{i}$ is only non-zero for $i=0$ and
$i=1+\frac{|S|-1}{r}\lambda$ and any two points of $S$ determine $\lambda$
blocks, which is always true in designs. This is equivalent to $S$ being a
maximal arc of order $1+\frac{|S|-1}{r}\lambda$. ∎

We can do a bit better for small values of $|S|$, which we will need later on.

######  Lemma 3.3.

Let $D=(\mathcal{P},\mathcal{B})$ be an incidence structure of type
$(v,b,k,r,\lambda)$. For any set $S\subseteq\mathcal{P}$, there are at least
$r|S|-\lambda\binom{|S|}{2}$ blocks which intersect $S$. Equality holds in
designs if and only if no three (or more) points of $S$ are incident with the
same block.

###### Proof.

We can recycle the definition of $x$, $n_{i}$ and the inequalities above to
compute

$\displaystyle 0$ $\displaystyle\leq\sum_{i>0}(i-1)(i-2)n_{i}$
$\displaystyle=\sum_{i>0}i^{2}n_{i}-3\sum_{i>0}in_{i}+2\sum_{i>0}n_{i}$
$\displaystyle\leq|S|(r+(|S|-1)\lambda)-3r|S|+2x$
$\displaystyle\Leftrightarrow x\geq r|S|-\lambda\binom{|S|}{2}$

In case of equality, we see that only $n_{1}$ and $n_{2}$ can be non-zero,
which implies the last statement. ∎

One can check that Lemma 3.3 yields a better bound than Lemma 3.2 if and only
if $|S|<1+\frac{r}{\lambda}$. In fact, a set of points with no three in a
block can have at most $1+r/\lambda$ points, and equality holds if and only if
it is a maximal arc of order 2. In that case, both bounds coincide.

We note that in Section 5 we will similarly want to estimate the number of
blocks incident with a small set of points. There we will use a greedy
approach, which would work equally well to prove the lemma above.

We will now use the first bound combined with 2.1 to obtain lower bounds on
the edge domination number of designs. We restrict ourselves to designs
instead of general incidence structures both for ease of presentation and the
fact that we do not need the general bounds in the remainder of this text.

######  Proposition 3.4.

Let $D=(\mathcal{P},\mathcal{B})$ be a $(v,k,\lambda)$-design and let $(X,Y)$
be an incidence-free pair satisfying $v-|X|=b-|Y|$. Then

  1. (1)

$\displaystyle|X|\leq
r\frac{k-r-2+\sqrt{(r-k)^{2}+4(r-\lambda)}}{2\lambda}+1$.

Equality holds if and only if $X$ is a maximal arc of order
$\displaystyle\frac{k-r+\sqrt{(r-k)^{2}+4(r-\lambda)}}{2}$ and $Y$ is its dual
arc.

  2. (2)

If $D$ is a symmetric design, then $\displaystyle|X|\leq
k\frac{\sqrt{k-\lambda}-1}{\lambda}+1$.

Equality holds if and only if $X$ is a maximal arc of order $\sqrt{k-\lambda}$
and $Y$ is its dual arc.

###### Proof.

(1) Since $Y$ contains no blocks incident to $X$, there are at most
$b-|Y|=v-|X|$ blocks incident with a point in $X$. By Lemma 3.2, this implies
that

$\frac{r^{2}|X|}{r+(|X|-1)\lambda}\leq v-|X|.$

This gives us an equation of the form $f(|X|)\leq 0$, where $f$ is a quadratic
polynomial with positive leading coefficient. Therefore, $|X|$ is at most the
largest root of $f$. Calculating this root is tedious, but straightforward,
and yields the bound from the Proposition, relying on Equation 1.

Now suppose that equality holds. Then we attain equality in the bound from
3.2, which implies that $X$ is a maximal arc. In this case, one can calculate
from the size of $X$ that it is a maximal arc of order
$(k-r+\sqrt{(r-k)^{2}+4(r-\lambda)})/2$. Necessarily, $Y$ must consist of all
blocks missing $X$, i.e. $Y$ must be the dual arc of $X$.

(2) This follows immediately from (1) using $k=r$. ∎

######  Corollary 3.5.

Let $D=(\mathcal{P},\mathcal{B})$ be a $(v,k,\lambda)$-design, then

  1. (1)

$\displaystyle\gamma_{e}(D)\geq
r\frac{r+k-\sqrt{(r-k)^{2}+4(r-\lambda)}}{2\lambda}$.

Equality holds if and only if $D$ has a maximal arc of order
$\displaystyle\frac{k-r+\sqrt{(r-k)^{2}+4(r-\lambda)}}{2}$.

  2. (2)

If $D$ is a symmetric design, then $\gamma_{e}(D)\geq\displaystyle
k\frac{k-\sqrt{k-\lambda}}{\lambda}$.

Equality holds if and only if $D$ has a maximal arc of order
$\sqrt{k-\lambda}$.

###### Proof.

By 2.1, there exists an incidence-free pair $(X,Y)$ with $|X|\geq
v-\gamma_{e}(D)$, and $|Y|\geq b-\gamma_{e}(D)$. Hence, we can find subsets
$X^{\prime}\subseteq X$ and $Y^{\prime}\subseteq Y$ of size $v-\gamma_{e}(D)$
and $b-\gamma_{e}(D)$ respectively. Note that $(X^{\prime},Y^{\prime})$ is
necessarily also incidence-free. Plugging this into 3.4 yields the desired
bound.

Vice versa, suppose that $D$ has a maximal arc $X$ of order
$n=(k-r+\sqrt{(r-k)^{2}+4(r-\lambda)})/2$. Let $Y$ denote its dual arc.
Consider the induced subgraph $H$ of $I(D)$ on $(\mathcal{P}\setminus
X)\cup(\mathcal{B}\setminus Y)$. Then every vertex in $\mathcal{P}\setminus X$
has degree $r-\frac{r-\lambda}{n}$, and every vertex in $Y$ has degree $k-n$,
i.e. $H$ is biregular. Furthermore, from equality in 3.4, it follows that
$|\mathcal{P}\setminus X|=|\mathcal{B}\setminus Y|$. Thus, $H$ is a regular
bipartite graph, and hence has a perfect matching by 2.2. Since there are no
edges between $X$ and $Y$ in $I(D)$, this matching is an edge dominating set
of size $v-|X|$. It is straightforward to check that $v-|X|$ equals the right-
hand side of the above bound. ∎

######  Remark 3.6.

  1. 1.

Recall that for a symmetric $(v,k,\lambda)$-design we have $r=k$ and
$v=k(k-1)/\lambda+1$, so (2) can be restated as

$\gamma_{e}(D)\geq v-\frac{k\sqrt{k-\lambda}-k}{\lambda}-1.$

This indeed shows that $\gamma_{e}(D)$ is equal to $v$ up to lower order
terms.

  2. 2.

Laskar and Wallis [LW99] showed that if $D$ is a symmetric $(n^{2}+n+1,n+1,1)$
design one has $\gamma_{e}(D)>\frac{1}{2}(n^{2}+3n)$. Our results improve this
to $\gamma_{e}(D)\geq n^{2}-n\sqrt{n}+2n-\sqrt{n}+1$.

  3. 3.

One could try to improve the bounds above by studying the existence of maximal
arcs in designs. This is however not feasible to do in general: even for the
class of projective planes defined over a finite field $\mathbb{F}_{q}$, which
are a special type of symmetric $(q^{2}+q+1,q+1,1)$-designs, the existence of
maximal arcs depends on the parity of $q$ as we will see later. Improvements
are thus only possible by restricting oneself to particular classes of
designs.

##  4 Constructing large incidence-free sets

In view of Theorem 1.2, upper bounding $\gamma_{e}(D)$ when $D$ is a symmetric
design is equivalent to constructing large incidence-free pairs. Here we
discuss two general techniques for achieving this goal.

###  4.1 A probabilistic construction

In a symmetric $(v,k,\lambda)$-design, one can greedily construct sets
$X\subseteq\mathcal{P},\ Y\subseteq\mathcal{B}$ such that no point in $X$ is
contained in a block of $Y$ and such that $|X|=|Y|\geq v/(k+1)\approx
k/\lambda$. One can improve this bound somewhat through a simple probabilistic
argument, which is based on a similar proof by De Winter, Schillewaert, and
Verstraëte [DWSV12, Theorem 6].

######  Proposition 4.1.

Let $D=(\mathcal{P},\mathcal{B})$ be an SIS of type $(v,k,\lambda)$ with
$\lambda\leq\frac{k}{64\log k}$. Then there exists an equinumerous incidence-
free pair whose size is at least $\frac{k\log k}{2\lambda}$.

###### Proof.

Let $X\subseteq\mathcal{P}$ be a random set of points obtained by including
each point in $\mathcal{P}$ independently with probability $p=\frac{\log
k}{2k}$, and let $Y\subseteq\mathcal{B}$ consist of the blocks which do not
contain any points of $X$. Note that by construction no point in $X$ is
contained in a block of $Y$, so it suffices to show that with positive
probability $|X|,|Y|\geq\frac{k\log k}{\lambda}$.

First observe that

$\mathbb{E}[|X|]=pv\geq\frac{\log
k}{2k}\cdot\frac{k(k-1)}{\lambda}\geq\frac{k\log k}{4\lambda}\geq 16,$ (2)

where the second to last step used $k\geq 2$, which is implicit from the
bounds $1\leq\lambda\leq\frac{k}{64\log k}$, and the last step used
$\lambda\leq\frac{k}{64\log k}$. Since $|X|$ is a binomial random variable, by
the Chernoff bound we have

$\Pr\left[|X|\leq\frac{1}{2}\mathbb{E}[|X|]\right]\leq
e^{-\mathbb{E}[|X|]/8}<\frac{1}{2}.$ (3)

For $B\in\mathcal{B}$, let $A_{B}$ denote the event that $B\in Y$. Then

$\Pr[A_{B}]=(1-p)^{k}\geq e^{-kp/(1-p)}\geq k^{-1/4},$

where this first inequality follows from exponentiating the inequality
$\log(1+x)\geq\frac{x}{1+x}$, and the last used $1-p\geq 1/2$. As
$v\geq\frac{k(k-1)}{\lambda}+1$, we conclude that

$\mathbb{E}[|Y|]=\sum_{B\in\mathcal{B}}\Pr[A_{B}]\geq\frac{k\log
k}{2\lambda}.$ (4)

Note that for any $B,B^{\prime}\in\mathcal{B}$ (possibly non-distinct), we
have

$\Pr[A_{B}\cap
A_{B^{\prime}}]\leq(1-p)^{2k-\lambda}=(1-p)^{-\lambda}\Pr[A_{B}]\Pr[A_{B^{\prime}}]\leq
e^{\lambda p/(1-p)}\Pr[A_{B}]\Pr[A_{B^{\prime}}]\leq
e^{1/32}\Pr[A_{B}]\Pr[A_{B^{\prime}}],$

where the second inequality used $\log(1+x)\geq\frac{x}{1+x}$ as before, and
the second used $\lambda p\leq 1/64$ and $1-p\geq 1/2$ by hypothesis.
Combining these two results gives

$\mathrm{Var}(|Y|)=\sum_{B,B^{\prime}\in\mathcal{B}}\Pr[A_{B}\cap
A_{B^{\prime}}]-\Pr[A_{B}]\Pr[A_{B}^{\prime}]\leq\left(e^{1/32}-1\right)\mathbb{E}[|Y|]^{2}\leq.04\mathbb{E}[|Y|]^{2}.$

Using this, Chebyshev’s inequality and denoting $Z=|Y|$ for readability, we
have

$\Pr\left(Z\leq\frac{1}{2}\mathbb{E}[Z]\right)\leq\Pr\left[|Z-\mathbb{E}[Z]|\geq\frac{1}{2}\mathbb{E}[Z]\right]\leq\frac{\mathrm{Var}(Z)}{\frac{1}{4}\mathbb{E}[Z]^{2}}\leq\frac{4}{25}.$
(5)

By (2), (3), (4) and (5) we conclude with positive probability we have
$|X|,|Y|\geq\frac{k\log k}{2\lambda}$, and hence there exists some pair of
sets $X,Y$ of at least this size such that no point in $X$ is contained in a
block of $Y$. Taking subsets of $X,Y$ of size
$\min\\{|X|,|Y|\\}\geq\frac{k\log k}{2\lambda}$ gives the result. ∎

For symmetric designs, this probabilistic construction is suboptimal for
proving asymptotically sharp bounds on the edge domination number, and it is
reasonable to think that more advanced techniques might provide better
constructions. However, [DWSV12, Problem 7] suggests that improving this
result to $k^{1+\varepsilon}/\lambda$ for any $\varepsilon>0$ might be hard
when $\lambda$ is small, as it is related to an open and difficult conjecture
by Erdős on $C_{4}$-free graphs and its generalisation to $K_{2,t}$-free
graphs.

This result (and its limitations mentioned above) motivates the need to look
at particular classes of symmetric designs in order to do better, which is
exactly what we will do in Section 6.

###  4.2 From polarities

In this section we describe a technique to construct equinumerous incidence-
free pairs in symmetric designs with special kinds of symmetries, such as the
Hadamard designs and those corresponding to projective planes over finite
fields.

######  Definition 4.2.

A _polarity_ of a symmetric design $D=(\mathcal{P},\mathcal{B})$ is a
bijection $\rho:\mathcal{P}\cup\mathcal{B}\to\mathcal{P}\cup\mathcal{B}$, such
that

  1. 1.

$\rho$ maps points to blocks and blocks to points,

  2. 2.

$\rho$ preserves incidence: for each pair
$(P,B)\in\mathcal{P}\times\mathcal{B}$ it holds that $P\in B$ if and only if
$\rho(B)\in\rho(P)$,

  3. 3.

$\rho^{2}$ is the identity map.

A point or block is _absolute_ if it is incident with its image under $\rho$.

Given a symmetric design $D=(\mathcal{P},\mathcal{B})$ with a polarity $\rho$,
define its _polarity graph_ $R(D,\rho)$ as the graph with $\mathcal{P}$ as
vertices, where two vertices $P$ and $Q$ are adjacent if and only if
$P\in\rho(Q)$. Note that each absolute point will give rise to a loop in this
graph. With this we can translate the problem of finding equinumerous
incidence-free pairs to finding cocliques in the polarity graph, which we
record in the following observation.

######  Lemma 4.3.

If $C$ is a coclique in $R(D,\rho)$, then $(C,\rho(C))$, where
$\rho(C):=\left\\{\rho(P)\,\,||\,\,P\in C\right\\}$, is an equinumerous
incidence-free pair.

We count loops as edges, which implies that a coclique in the polarity graph
contains no absolute points.

##  5 Incidence-free sets in symmetric designs

In this section we prove 1.2, which says that for symmetric designs $D$, the
edge domination number $\gamma_{e}(D)$ is equal to $v-\alpha$ where $\alpha$
is the size of a largest equinumerous incidence-free pair $(X,Y)$. The fact
that $\gamma_{e}(D)$ is at least this quantity follows from 2.1, so it remains
to construct an edge dominating set of this size. We do this through the
following.

######  Proposition 5.1.

Let $D=(\mathcal{P},\mathcal{B})$ be a symmetric $(v,k,\lambda)$-design with
$k\geq 100$. If $(X,Y)$ is an equinumerous incidence-free pair, then there is
a perfect matching between $\mathcal{P}\setminus X$ and $\mathcal{B}\setminus
Y$ in $I(D)$.

The perfect matching guaranteed by 5.1 gives an edge dominating set of size
$v-|X|$, so choosing a largest equinumerous incidence-free pair gives the
upper bound of 1.2. Thus to prove 1.2, it only remains to prove 5.1. We do
this in the next subsection.

###  5.1 Proof of 5.1

For the remainder of this subsection, we fix the following assumptions and
notation:

  * •

$D=(\mathcal{P},\mathcal{B})$ is a symmetric $(v,k,\lambda)$-design with
$k\geq 100$;

  * •

$(X,Y)$ is an equinumerous incidence-free pair in $D$;

  * •

$G$ will denote the induced subgraph of $I(D)$ obtained by removing $X$ and
$Y$ from its vertex set;

  * •

$\alpha:=|X|=|Y|$.

We note that under the assumption $k\geq 100$, we have

$\alpha\leq\frac{k^{2}}{10\lambda}.$ (6)

Indeed, by 3.4 we have
$\alpha\leq\frac{k^{3/2}}{\lambda}\leq\frac{k^{2}}{10\lambda}$, where this
last step used $k\geq 100$.

We will use the following easy consequence of Hall’s theorem to show the
existence of perfect matchings in $G$; see e.g. [Ehr15] for details of its
proof. Here $N_{G^{\prime}}(S)$ denotes the set of vertices which are adjacent
to some vertex of $S$ in a graph $G^{\prime}$.

######  Lemma 5.2.

Let $G^{\prime}$ be a bipartite graph on $U\cup V$ with $|U|=|V|$. If every
$S\subseteq U$ and $T\subseteq V$ with
$|S|,|T|\leq\left\lceil\frac{1}{2}|U|\right\rceil$ satisfies
$|N_{G^{\prime}}(S)|\geq|S|$ and $|N_{G}(T)|\geq|T|$, then $G^{\prime}$ has a
perfect matching.

We first show that 5.2 is satisfied whenever $S\subseteq\mathcal{P}\setminus
X$ is relatively large. For this, we observe that by definition of $D$ being a
symmetric $(v,k,\lambda)$-design, the graph $I(D)$ is $K_{2,\lambda+1}$-free,
and hence all of its subgraphs are as well. By using the famous result by
Kővári, Sós, and Turán [KST54], which upper bounds the maximum number of edges
that a $K_{s,t}$-free bipartite graph can have, we immediately get the
following.

######  Lemma 5.3.

For any $S\subseteq\mathcal{P}$ and $T\subseteq\mathcal{B}$, we have

$e(S,T)\leq\sqrt{\lambda}(|S|-1)\sqrt{|T|}+|T|,$

where $e(S,T)$ denotes the number of edges in $I(D)$ between $S$ and $T$.

This gives the following.

######  Lemma 5.4.

If $S\subseteq\mathcal{P}\setminus X$ satisfies

$\lambda(|S|+\alpha)\leq\left(k-1-\frac{\alpha}{|S|}\right)^{2},$

then $|N_{G}(S)|\geq|S|$.

###### Proof.

Let $S$ be as in the lemma statement and set $T=N_{I(D)}(S)$. If
$|T|\geq|S|+\alpha$, then

$|N_{G}(S)|=|T\setminus Y|\geq|T|-|Y|=|T|-\alpha\geq|S|.$

Thus we may assume for contradiction that $|T|<|S|+\alpha$. By the preceding
lemma, we find

$k|S|=e(S,T)\leq\sqrt{\lambda}(|S|-1)\sqrt{|T|}+|T|<\sqrt{\lambda}|S|\sqrt{|S|+\alpha}+|S|+\alpha.$

By dividing both sides by $|S|$, we see that the above is equivalent to

$\sqrt{\lambda(|S|+\alpha)}>k-1-\frac{\alpha}{|S|}.$

This contradicts our choice of $S$, so we conclude the result. ∎

######  Corollary 5.5.

If $S\subseteq\mathcal{P}\setminus X$ satisfies

$\alpha\leq|S|\leq\frac{(k-2)^{2}}{\lambda}-\alpha,$

then $|N_{G}(S)|\geq|S|$.

Note that the number of vertices in each part of $G$ is exactly
$\frac{k(k-1)}{\lambda}+1-\alpha$, so this corollary shows that Hall’s
condition is satisfied for almost all sets of size at least $\alpha$.

###### Proof.

Let $S$ be as in the hypothesis of the statement and assume for contradiction
that

$\lambda(|S|+\alpha)>\left(k-1-\frac{\alpha}{|S|}\right)^{2}\geq(k-2)^{2},$

where this last inequality used $|S|\geq\alpha$. This contradicts our
assumption on $S$. We conclude that the hypothesis of 5.4 is satisfied, and
hence $|N_{G}(S)|\geq|S|$. ∎

######  Corollary 5.6.

If $S\subseteq\mathcal{P}\setminus X$ satisfies

$\frac{2\alpha}{k}\leq|S|\leq\alpha,$

then $|N_{G}(S)|\geq|S|$.

###### Proof.

Let $S$ be as in the hypothesis of the statement and assume for contradiction
that

$\lambda(|S|+\alpha)>\left(k-1-\frac{\alpha}{|S|}\right)^{2}\geq\left(\frac{1}{2}k-1\right)^{2}\geq\frac{1}{5}k^{2},$

where the second inequality used $\frac{\alpha}{|S|}\leq\frac{1}{2}k$, and the
last inequality used $k\geq 100$. Because $|S|\leq\alpha$, this implies
$2\lambda\alpha>\frac{1}{5}k^{2}$, and this does not hold by (6). We conclude
that the hypothesis of 5.4 is satisfied, and hence $|N_{G}(S)|\geq|S|$. ∎

Note that up to this point, we have not used the hypothesis that $(X,Y)$ is
incidence-free. We use this to deal with sets of size at most
$\frac{2\alpha}{k}$. The following lemma can be seen as a variation of 3.3.

######  Lemma 5.7.

Every $S\subseteq\mathcal{P}\setminus X$ has

$|N_{G}(S)|\geq\max_{s\leq|S|}\frac{\lambda\alpha s}{k}-\lambda\binom{s}{2}.$

###### Proof.

Fix any vertex $P\in\mathcal{P}\setminus X$. Observe that each vertex in $X$
has $\lambda$ common neighbours with $P$ in $I(D)$, and that these neighbours
necessarily lie in $\mathcal{B}\setminus Y$ since $X$ and $Y$ are incidence-
free. Thus

$\lambda\alpha=\lambda|X|\leq e_{I(D)}(N_{G}(P),X)\leq k|N_{G}(P)|,$

where this last step used that each vertex of $I(D)$ has degree $k$. We
conclude that $|N_{G}(P)|\geq\frac{\lambda\alpha}{k}$ for all
$P\in\mathcal{P}\setminus X$.

Now given any $S\subseteq\mathcal{P}\setminus X$, let $S^{\prime}\subseteq S$
be a subset of size $s$. By an inclusion-exclusion argument, we see

$|N_{G}(S)|\geq|N_{G}(S^{\prime})|\geq\sum_{P\in
S^{\prime}}|N_{G}(P)|-\sum_{P,Q\in S^{\prime}}|N_{G}(P)\cap
N_{G}(Q)|\geq\frac{\lambda\alpha s}{k}-\lambda\binom{s}{2},$

where this last step used the previous observation and that every two distinct
vertices in $S^{\prime}$ have at most $\lambda$ common neighbours in $G$. The
above inequality holds for any $s\leq|S|$, giving the result. ∎

We now have everything in place to prove our main result for this subsection.

###### Proof of 5.1.

If $\alpha=0$ then $G=I(D)$ is a regular bipartite graph, which has a perfect
matching by 2.2. Thus we may assume $\alpha>0$. We now show that $G$ has a
perfect matching by using 5.2, and by the symmetry of the problem, it suffices
to prove $|N_{G}(S)|\geq|S|$ whenever $S\subseteq\mathcal{P}\setminus X$ with
$|S|\leq\left\lceil\frac{1}{2}|\mathcal{P}\setminus X|\right\rceil$.

We first claim that
$\frac{(k-2)^{2}}{\lambda}-\alpha\geq\left\lceil\frac{1}{2}|\mathcal{P}\setminus
X|\right\rceil$. Indeed, recall that
$|\mathcal{P}|=\frac{k(k-1)}{\lambda}+1\leq\frac{k^{2}}{\lambda}$. Thus to
prove the claim it suffices to prove

$2\frac{(k-2)^{2}}{\lambda}-2\alpha\geq\frac{k^{2}}{\lambda}+1-\alpha,$

where the extra $1$ stems from upper bounding the ceiling function. This is
equivalent to showing

$\alpha\leq\frac{k^{2}-8k+8-\lambda}{\lambda}.$

Note that $k^{2}-8k+8-\lambda\geq(k-9)k\geq\frac{1}{10}k^{2}$ since
$k\geq\lambda$ and $k\geq 100$. Thus the inequality above follows from (6),
proving the claim.

With this claim, Corollaries 5.5 and 5.6 imply $|N_{G}(S)|\geq|S|$ for
$\frac{2\alpha}{k}\leq|S|\leq\left\lceil\frac{1}{2}|\mathcal{P}\setminus
X|\right\rceil$. If $\lambda\geq 2$ and $|S|\leq\frac{2\alpha}{k}$, then Lemma
5.7 with $s=1$ implies $|N_{G}(S)|\geq|S|$, proving the result in this case.
If $\lambda=1$ and $2\leq|S|<\frac{2\alpha}{k}$, then
$|S|\leq\left\lceil\frac{2\alpha}{k}-1\right\rceil$, and Lemma 5.7 with $s=2$
implies $|N_{G}(S)|\geq\left\lceil\frac{2\alpha}{k}-1\right\rceil\geq|S|$.
Finally, if $\lambda=1$ and $S=\\{P\\}$, we claim there is at least one block
in $N_{I(D)}(P)\setminus Y$. Indeed, $X$ is non-empty since $\alpha>0$, and
any $Q\in X$ is contained in a unique block $B$ with $P$ since $\lambda=1$. We
can not have $B\in Y$ since $(X,Y)$ is incidence-free, so $B\in
N_{I(D)}(P)\setminus Y$. We conclude that the conditions of 5.2 are satisfied
in all cases, giving the result. ∎

###  5.2 Adapting the proof to symmetric incidence structures

As mentioned in the introduction, 1.2 does not hold for SIS’s in general.
Indeed, if $D$ is the disjoint union of two symmetric designs
$(\mathcal{P}_{1},\mathcal{B}_{1})$ and $(\mathcal{P}_{2},\mathcal{B}_{2})$,
then taking $X=\mathcal{P}_{1}$ and $Y=\mathcal{B}_{2}$ shows that such a
result can not hold in general. Counterexamples continue to exist even if one
assumes $I(D)$ is connected, as we will see in 6.24.

This being said, there were only a few crucial instances where we used the
properties of a design. Firstly, we used 3.4 to show that $\alpha$ is small in
comparison to $v$. Secondly, in 5.7 we used that in a design every two points
have at least $\lambda$ common neighbours in order to show small sets
satisfied Hall’s condition. In this subsection, we will replace these
consequences by making assumptions on the size of $X$ and a minimum degree
condition in $G$, respectively.

In addition to this, we will require that the incidence structure is somewhat
close to a symmetric design in the sense that $v$ is comparable to
$\frac{k^{2}}{\lambda}$. The construction indicated above to obtain an SIS
from disjoint unions of symmetric designs can be iterated an arbitrarily
number of times. The edge density of the resulting SIS will be very small, and
in this case the upper bound in 3.4 will be useless. For this reason we will
require that $v=c\frac{k^{2}}{\lambda}$ for some constant $c>0$.

All of these conditions will allow us to construct small edge dominating sets
whenever the incidence structure is not a symmetric design in Section 6.3. The
theorem we state will not be best possible, but suffices for our purposes in
this paper and allows us to recycle the proofs in the previous subsection.

######  Theorem 5.8.

Let $D=(\mathcal{P},\mathcal{B})$ be an SIS of type $(v,k,\lambda)$ where
$v\leq\frac{9}{5}\frac{k^{2}}{\lambda}$ and $k\geq 100$. If $(X,Y)$ is an
equinumerous incidence-free pair with $|X|\leq\frac{k^{2}}{10\lambda}$ and
every point or block not in $X\cup Y$ is incident with at least
$\frac{2|X|}{k}$ blocks or points not in $X\cup Y$, then

$\gamma_{e}(D)\leq v-|X|.$

###### Proof.

The proof is nearly identical to that of 1.2, so we omit some of the redundant
details. As before, it suffices to show there is a perfect matching between
$\mathcal{P}\setminus X$ and $\mathcal{B}\setminus Y$ in $I(D)$.

Let $G$ denote the induced subgraph of $I(D)$ after removing the vertices of
$X\cup Y$ and define $\alpha:=|X|=|Y|$. It is not difficult to show that the
proofs of 5.5 and 5.6 continue to hold in this setting by our assumptions on
$\alpha$ and $k$. Instead of 5.7, we find

$\displaystyle|N_{G}(S)|\geq\max_{s\leq|S|}\frac{2\alpha
s}{k}-\lambda\binom{s}{2}$ (7)

for every $S\subset\mathcal{P}\setminus X$ by the minimum degree condition.

Then we prove again the claim that
$\frac{(k-2)^{2}}{\lambda}-\alpha\geq\left\lceil\frac{1}{2}|\mathcal{P}\setminus
X|\right\rceil$. This will follow from the inequality

$2\frac{(k-2)^{2}}{\lambda}-2\alpha\geq\frac{9k^{2}}{5\lambda}-\alpha,$

using the assumption $|\mathcal{P}|=v\leq\frac{9k^{2}}{5\lambda}$.
Equivalently

$\alpha\leq\frac{11k^{2}-80k+80}{10\lambda}.$

Since $\alpha\leq\frac{k^{2}}{10\lambda}$ by assumption, we see that the claim
is satisfied for $k\geq 100$.

Now we conclude the proof by observing that for all sets
$S\subseteq\mathcal{P}\setminus X$ with
$\frac{2\alpha}{k}\leq|S|\leq\frac{1}{2}|\mathcal{P}\setminus X|$ we have
$N_{G}(S)\geq|S|$ by the analogues of 5.5 and 5.6. For
$|S|\leq\frac{2\alpha}{k}$, we see that the minimum degree condition provides
$N_{G}(S)\geq|S|$ by setting $s=1$ in Equation 7. ∎

##  6 Application to particular classes of designs

###  6.1 Projective point-subspace designs

In this section we will discuss the edge domination number of the design of
points and $k$-spaces in the projective space $\textnormal{PG}(n,q)$, with
$0<k<n$. By $k$-spaces we refer to subspaces of projective dimension $k$. The
$0$-, $1$-, and $(n-1)$-spaces are referred to as points, lines and
hyperplanes. This design is symmetric only when $k=n-1$. Denote the number of
points in $\textnormal{PG}(n,q)$ by

$\theta_{n}=\frac{q^{n+1}-1}{q-1}.$

The smallest case is the design of points and lines in the Desarguesian
projective plane. In this setting, we can construct large incidence-free sets
from polarities.

Assign coordinates
$(x_{0},\dots,x_{n})\in\mathbb{F}_{q}^{n+1}\setminus\left\\{(0,\dots,0)\right\\}$
to the points in $\textnormal{PG}(n,q)$, where $(x_{0},\dots,x_{n})$ and
$(y_{0},\dots,y_{n})$ are considered as the same point if they are scalar
multiples of each other. For each projective point $P=(a_{0},\dots,a_{n})$,
let $P^{\perp}$ denote the hyperplane with equation
$a_{0}X_{0}+\dots+a_{n}X_{n}=0$. Then mapping a point $P$ to the hyperplane
$P^{\perp}$ and vice versa, determines a polarity $\perp$ of
$\textnormal{PG}(n,q)$. When $n=2$, the following lower bounds on the
independence number of the polarity graph $R(D,\rho)$ are known.

######  Theorem 6.1 ([MW07, MPS19]).

Let $D$ be the design of points and lines in $\textnormal{PG}(2,q)$, $q=p^{h}$
where $p$ prime and $h\geq 1$, and let $\rho$ be the polarity described above.
Then the polarity graph $R(D,\rho)$ has a coclique of size at least
$cq\sqrt{q}-O(q)$, where

$c=\begin{cases}1&\text{for $p=2$ and $h$ even},\\\
\frac{1}{\sqrt{2}}&\text{for $p=2$ and $h$ odd},\\\ \frac{1}{2}&\text{for $p$
odd and $h$ even},\\\ 0.19&\text{for $p$ odd and $h$ odd}.\end{cases}$

######  Corollary 6.2.

Let $D$ be the design of points and lines in $\textnormal{PG}(2,q)$, $q\geq
101$. Then

$q^{2}-q\sqrt{q}-O(q)\leq\gamma_{e}(D)\leq q^{2}-cq\sqrt{q}-O(q),$

where $c$ is defined as in 6.1.

###### Proof.

The lower bound follows from 3.5. The upper bound follows from 4.3 and 6.1,
giving us the incidence-free pair, and 1.2 turning it into an edge-dominating
set of the wanted size. ∎

Going via the polarity graph is actually a detour when $p=2$. It is known that
$\textnormal{PG}(2,q)$ has a maximal arc of order $n$ if and only if $q=2^{h}$
and $n$ divides $q$ [Den69, BBM97]. So starting from a maximal arc of order
$\sqrt{q}$ or $\sqrt{q/2}$, depending on the parity of $h$, we can combine our
earlier observations on arcs and the corresponding dual arcs with 2.2 to
improve the result in 6.2 for even $q$. The improvement only lies in the
omission of the restriction on $q$, the actual value of $\gamma_{e}(D)$ will
be the same. We state the sharp result for even $h$ for completeness.

######  Corollary 6.3.

For all $q=2^{2h}$ we have

$\gamma_{e}(D)=q^{2}-q\sqrt{q}+\sqrt{q}+1.$

A similar result holds in the more general design of points and hyperplanes in
$\textnormal{PG}(n,q)$, $n\geq 2$. A large incidence-free set was found by De
Winter, Schillewaert, and Verstraëte [DWSV12, §4.2].

######  Theorem 6.4.

There exists an equinumerous incidence-free pair $(X,Y)$ of sets of points and
hyperplanes respectively in $\textnormal{PG}(n,q)$ of size
$\Theta(q^{\frac{n+1}{2}})$.

######  Corollary 6.5.

Let $D$ be the design of points and hyperplanes in $\textnormal{PG}(n,q)$,
$n\geq 2$. Then

$\gamma_{e}(D)=\theta_{n}-\Theta_{q}(q^{\frac{n+1}{2}}).$

###### Proof.

This follows from 3.5 and the preceding result combined with 1.2. ∎

In other projective point-subspace designs, it is not difficult to determine
the edge domination number exactly.

######  Proposition 6.6.

Let $D$ be the design of points and $k$-spaces in $\textnormal{PG}(n,q)$,
$1\leq k<n-1$, and $n\geq 3$. Then

$\gamma_{e}(D)=\begin{cases}\theta_{n}-q&\text{if }k=1,\\\
\theta_{n}&\text{otherwise.}\end{cases}$

###### Proof.

If $1<k<n-1$, then the number of $k$-spaces each point is incident to equals

$r=\prod_{i=1}^{k}\frac{q^{n-k+i}-1}{q^{i}-1}>\frac{q^{n+1}-1}{q-1}=v.$

By Lemma 2.3, $\gamma_{e}(D)=v=\theta_{n}$.

Now suppose $k=1$. First we show that $\gamma\geq\theta_{n}-q$. One can see
that

$\theta_{n}-(q+1)<(q+1)\theta_{n-1}-\binom{q+1}{2}$

if $n\geq 3$. Therefore, by Lemma 3.3 every set $S$ of $q+1$ points is
incident with a set of lines $T$, where $|T|>\theta_{n}-(q+1)$. Now suppose
for the sake of contradiction that we have an edge dominating set $\Gamma$
with $|\Gamma|\leq\theta_{n}-(q+1)$. Then there are at least $q+1$ points not
covered by an edge of $\Gamma$, so that the lines with which they are incident
should all be covered by an edge. However, the number of such lines is more
than $\theta_{n}-(q+1)=|\Gamma|$, so this is impossible.

We can describe a construction that yields edge dominating sets of $I(D)$ of
size $\theta_{n}-q$. Consider an incident point-line pair $(x,\ell)$. Let $S$
denote the points not on $\ell$ and $T$ denote the set of lines intersecting
$\ell\setminus\\{x\\}$ in a point (so not $\ell$ itself). Then
$|S|=|T|=\theta_{n}-(q+1)$. The subgraph of $I(D)$ induced on $(S,T)$ is
$q$-regular and hence has a perfect matching due to 2.2. By adding the edge
$(x,\ell)$, we find a maximal matching in $I(D)$ of size $\theta_{n}-q$. ∎

###  6.2 Symmetric designs from Hadamard matrices

A _Hadamard matrix_ is an $n\times n$-matrix $M$ with only $1$ and $-1$ as
entries such that $M^{t}M=nI_{n}$. We refer the reader to [IS06, Chapter 4]
for a treatise of the subject. There are several constructions of symmetric
designs from Hadamard matrices.

####  6.2.1 Hadamard designs and Paley matrices

Let $\mathbf{1}$ denote the all-one column vector. If a $4u\times 4u$ Hadamard
matrix $M$ is normalised, i.e. of the form

$M=\begin{pmatrix}1&\mathbf{1}^{t}\\\ \mathbf{1}&N\end{pmatrix},$

then we can replace every $-1$ in $N$ with a 0. Equivalently, if we define $J$
to be the all-one matrix of the appropriate size (which will be clear from
context), then we consider the matrix $\frac{1}{2}(N+J)$. This yields the
incidence matrix of a symmetric $2-(4u-1,2u-1,u-1)$ design. Such a design is
called a _Hadamard design_. The next bound follows directly from 3.5(2).

######  Lemma 6.7.

Let $D$ be a $(4u-1,2u-1,u-1)$ Hadamard design. Then

$\gamma_{e}(D)\geq 4u-2\sqrt{u}-\frac{1}{\sqrt{u}+1}.$

We consider the following construction due to Paley [Pal33] of a Hadamard
matrix. Consider the field $\mathbb{F}_{q}$ with $q$ odd. Define the quadratic
character of $\mathbb{F}_{q}$ as

$\chi(x)=\begin{cases}0&\text{if }x=0,\\\ 1&\text{if $x$ is a non-zero
square},\\\ -1&\text{if $x$ is not a square},\end{cases}$

Let $Q$ denote the Jacobstahl matrix of $\mathbb{F}_{q}$, i.e. the rows and
columns of $Q$ are indexed by the elements of $\mathbb{F}_{q}$, and
$Q_{x,y}=\chi(x-y)$.

Suppose that $q\equiv 1\pmod{4}$. Then the matrix

$M=\begin{pmatrix}0&\mathbf{1}^{t}\\\
\mathbf{1}&Q\end{pmatrix}\otimes\begin{pmatrix}1&1\\\
1&-1\end{pmatrix}+I\otimes\begin{pmatrix}1&-1\\\ -1&-1\end{pmatrix}$

is a Hadamard matrix, where $\otimes$ denotes the tensor product. We can
interpret this matrix as follows. Say that the the first row and column of
$\begin{pmatrix}0&\mathbf{1}^{t}\\\ \mathbf{1}&Q\end{pmatrix}$ are indexed by
$\infty$. The other rows and columns are naturally indexed by
$\mathbb{F}_{q}$. Say that the rows and columns of the $2\times 2$-matrices
are indexed by $1$ and $-1$, in that order. Define $\infty-\infty=0$,
$\infty-x=x-\infty=\infty$ for all $x\in\mathbb{F}_{q}$, and $\chi(\infty)=1$.
Then

$M((x,i),(y,j))=\begin{cases}1&\text{if $x=y$ and }(i,j)=(1,1),\\\ -1&\text{if
$x=y$ and }(i,j)\neq(1,1),\\\ \chi(x-y)&\text{if $x\neq y$ and
}(i,j)\neq(-1,-1),\\\ -\chi(x-y)&\text{if $x\neq y$ and
}(i,j)=(-1,-1).\end{cases}$

If we scale the second the second row and the second column with a factor
$-1$, then we obtain a Hadamard matrix of the form
$\begin{pmatrix}1&\mathbf{1}^{t}\\\ \mathbf{1}&N\end{pmatrix}$, and therefore
$\frac{1}{2}(N+J)$ is the incidence matrix of a Hadamard design. We denote
this design as $HD(q)$. It is a $(2q+1,q,\frac{q-1}{2})$ design. The point set
is $(\mathbb{F}_{q}\times\left\\{1,-1\right\\})\cup\left\\{\infty\right\\}$.
For each point $P$ there is a block $B_{P}$, with

$\displaystyle B_{\infty}$
$\displaystyle=\mathbb{F}_{q}\times\left\\{-1\right\\},$ $\displaystyle
B_{(x,1)}$ $\displaystyle=\left\\{(y,i)\,\,||\,\,\chi(x-y)=1,i=\pm
1\right\\}\cup\left\\{(x,1)\right\\},$ $\displaystyle B_{(x,-1)}$
$\displaystyle=\left\\{(y,i)\,\,||\,\,\chi(y-x)=i\right\\}\cup\left\\{\infty\right\\}.$

######  Lemma 6.8.

Let $C$ be a clique in the Paley graph of order $q\geq 101$. Then $I(HD(q))$
has an edge dominating set of size $2q+1-|C|$.

###### Proof.

Consider the map $\rho$ which maps a point $P$ to the block $B_{P}$, and vice
versa the block $B_{P}$ to the point $P$. As $N$ is symmetric, for any two
points $P$ and $Q$, it holds that $P\in Q^{\rho}$ if and only if $Q\in
P^{\rho}$. In other words, $\rho$ is a polarity of the design. The cocliques
in the polarity graph of $HD(q)$ are exactly the sets
$K\times\left\\{-1\right\\}$, with $K$ a clique in the Paley graph of order
$q$, and $\left\\{\infty\right\\}$.

Hence, if $C$ is a clique in the polarity graph, then the statement of the
lemma follows from 1.2 and 4.3. ∎

If $q$ is a square, then it is known that $\mathbb{F}_{\sqrt{q}}$ is a clique
of maximal size in the Paley graph of order $q$. We thus obtain the following
corollary.

######  Corollary 6.9.

If $q\geq 101$ is a square, then $\gamma_{e}(HD(q))=2q-\Theta(\sqrt{q})$.

####  6.2.2 Menon designs and symmetric Bush-type Hadamard matrices

If a $4u\times 4u$ Hadamard matrix $M$ has constant row sum, then it is called
regular. In that case $u$ must be square, say $u=h^{2}$, and
$\frac{1}{2}(J+M)$ and $\frac{1}{2}(J-M)$ are incidence matrices of symmetric
designs, called _Menon designs_. These designs have parameters
$2$-$(4h^{2},2h^{2}+\varepsilon h,h^{2}+\varepsilon h)$ with $\varepsilon=\pm
1$. By Lemma 3.2(2), the edge domination number of such a design is at least
$4h^{2}-2h$ if $\varepsilon=-1$, and $4h^{2}-2h+2-\frac{2}{h+1}$ if
$\varepsilon=1$.

A regular $4h^{2}\times 4h^{2}$ Hadamard matrix $M$ is _of Bush type_ if it is
a block matrix where all the blocks are $2h\times 2h$-matrices, all the
diagonal blocks are all-one matrices, and all the other blocks have constant
row and column sum 0. If such a matrix $M$ is symmetric, then
$\frac{1}{2}(J-M)$ is the incidence matrix of Menon design with
$\varepsilon=-1$, which has a polarity without absolute points, and where the
vertices of the polarity graph can be partitioned into cocliques of size $2h$.
Note that each such coclique consists of $2h$ points, with $2h$ blocks not
incident with these points (namely their image under the polarity).

######  Proposition 6.10.

If $D$ is a Menon design associated with a symmetric Hadamard matrix of Bush
type, it is a $(4h^{2},2h^{2}-h,h^{2}-h)$-design and
$\gamma_{e}(D)=4h^{2}-2h$.

###### Proof.

Applying 3.5(2) to this set of parameters gives the lower bound, while the
incidence-free set of size $2h$ described above provides the upper bound. We
note that this set is a maximal arc by 3.4(2) and so indeed gives rise to an
edge dominating set as seen before. ∎

There are constructions of infinite families of symmetric Bush-type Hadamard
matrices. One such family can be found in [MX06]. Another interesting family
are the symplectic symmetric designs, which Kantor [Kan85] proved to be one of
the only two infinite families of 2-transitive symmetric designs with $v>2k$.

###  6.3 Semi-biplanes

There are only a very limited number of explicit symmetric designs with
$\lambda=2$. These designs are known as _biplanes_. However, we can relax the
definition to obtain the so-called semi-biplanes, of which there are several
known infinite families. They were introduced by Hughes [Hug78].

######  Definition 6.11.

A _semi-biplane_ is a symmetric incidence structure
$D=(\mathcal{P},\mathcal{B})$ such that

  1. 1.

for every two distinct points $P$ and $Q$, there are either 0 or 2 blocks
incident with $P$ and $Q$,

  2. 2.

for every two distinct blocks $B$ and $C$, $|B\cap C|$ equals either 0 or 2,

  3. 3.

the incidence graph $I(D)$ is connected.

Given a semi-biplane, there exist numbers $v$ and $k$ such that
$|\mathcal{P}|=|\mathcal{B}|=v$, and every point or block is incident with
exactly $k$ blocks or points respectively. The parameters $(v,k)$ are called
the _order_ of the semi-biplane, and a semi-biplane of order $(v,k)$ is
denoted as $\operatorname{sbp}(v,k)$.

The _collinearity graph_ of an incidence structure $(\mathcal{P},\mathcal{B})$
is the graph with vertex set $\mathcal{P}$, where two distinct points $P$ and
$Q$ are adjacent if and only if there is some block incident with $P$ and $Q$.
The collinearity graph of a $\operatorname{sbp}(v,k)$ is regular of degree
$\binom{k}{2}$.

If we denote by $N$ the point-block incidence matrix of a
$\operatorname{sbp}(v,k)$, and by $A$ the adjacency matrix of its collinearity
graph, then

$NN^{t}=kI_{v}+2A.$

####  6.3.1 Divisible semi-biplanes

We call a semi-biplane $D=(\mathcal{P},\mathcal{B})$ _divisible_ if its
collinearity graph is a complete multipartite graph. Another way to formulate
is that the relation $\sim$ defined on $\mathcal{P}$ by

$P\sim Q\iff P=Q\text{ or $P$ and $Q$ are not collinear}$

is an equivalence relation. It is not difficult to show that every equivalence
class contains the same number of elements, say $d$, and that
$v=\binom{k}{2}+d$.

We would like to give a lower bound on the edge domination number of the
incidence graph of a divisible semi-biplane. As before, such a bound follows
from an upper bound on the size of an equinumerous incidence-free pair. One
way to bound this size is by using 3.2. Another way is by using an eigenvalue
bound from spectral graph theory. For designs, this yields the same bound, but
for divisible semi-biplanes, this is no longer the case. Both approaches yield
lower bounds on $\gamma_{e}(D)$ that look roughly like
$v-\frac{k\sqrt{k}}{2}$, but the spectral approach yields a significantly
simpler expression.

######  Lemma 6.12 ([Hae95, Theorem 5.1] Expander mixing lemma).

Let $G$ be a $k$-regular bipartite graph, with bipartition $L$ and $R$. Take
sets $S\subseteq L$ and $T\subseteq R$. Suppose that the second largest
eigenvalue of the adjacency matrix of $G$ is $\lambda_{2}$. Then

$\left(e(S,T)-\frac{k}{|R|}|S||T|\right)^{2}\leq\lambda_{2}^{2}|S||T|\left(1-\frac{|S|}{|L|}\right)\left(1-\frac{|T|}{|R|}\right).$

######  Proposition 6.13.

Let $D$ denote an SIS of type $(v,k,\lambda)$. Let $\lambda_{2}$ denote the
second largest eigenvalue of $I(D)$. Then

$\gamma_{e}(D)\geq\frac{k}{\lambda_{2}+k}v.$

###### Proof.

Take an edge dominating set of size $\gamma:=\gamma_{e}(D)$. Then there exist
sets $S$ and $T$ of blocks and points respectively of size $v-\gamma$ with no
incidences between them. Apply the expander mixing lemma in $I(D)$ to $S$ and
$T$. This tells us that

$\left(\frac{k}{v}(v-\gamma)^{2}\right)^{2}\leq\lambda_{2}^{2}(v-\gamma)^{2}\left(\frac{\gamma}{v}\right)^{2}.$

Taking square roots, this reduces to

$k(v-\gamma)\leq\lambda_{2}\gamma,$

which gives the desired equality. ∎

######  Remark 6.14.

Observe that if $N$ is the incidence matrix of an SIS of type $(v,k,\lambda)$,
then $vk=\mathrm{Tr}(NN^{t})\leq k^{2}+(v-1)\lambda_{2}$. This shows that
$\lambda_{2}=\Omega(\sqrt{k})$. On the other hand, we can have $\lambda_{2}=k$
when the SIS is the union of two disjoint symmetric designs. This shows that
the edge domination number of an SIS could lie anywhere between
$\left(1-\Omega\left(\frac{1}{\sqrt{k}}\right)\right)v$ and $\frac{1}{2}v$.
For the symmetric designs we have seen before, we observe that the truth is
closer to the higher end. This is again related to the fact that incidence
graphs of symmetric designs are ‘expanding’, this time expressed by the fact
that $\lambda_{2}$ is small compared to $k$.

######  Lemma 6.15.

Let $D$ be a divisible $\operatorname{sbp}(v,k)$ and write $d=v-\binom{k}{2}$.
Then the spectrum of the adjacency matrix of $I(D)$ equals

$\\{\pm
k,\pm\sqrt{k}^{(\frac{v}{d}(d-1))},\pm\sqrt{k-2d}^{(\frac{v}{d}-1)}\\}.$

###### Proof.

Let $N$ denote the incidence matrix of $D$. It suffices to compute the
spectrum of $NN^{t}$. The adjacency matrix of the collinearity graph of $D$
equals $A=(J-I)_{\frac{v}{d}}\otimes J_{d}$. Since $(J-I)_{\frac{v}{d}}$ has
spectrum $(\frac{v}{d}-1)^{(1)},-1^{(\frac{v}{d}-1)}$, and $J_{d}$ has
spectrum $d^{(1)},0^{(d-1)}$, the spectrum of $NN^{t}=kI+2A$ equals

$\\{{k^{2}},k^{(\frac{v}{d}(d-1))},(k-2d)^{(\frac{v}{d}-1)}\\}.$

It is well-known that if $N$ is a square matrix, then $\lambda$ is an
eigenvalue of $NN^{t}$ with multiplicity $m$ if and only if $\sqrt{\lambda}$
and $-\sqrt{\lambda}$ are eigenvalues of $\begin{pmatrix}O&N\\\
N^{t}&O\end{pmatrix}$, both with multiplicity $m$. ∎

######  Remark 6.16.

The lemma implies that $d\leq k/2$ and thus $v\leq k^{2}/2$. This also has an
easy combinatorial proof, see Wild [Wil81, Result 2].

######  Corollary 6.17.

Let $D$ be a divisible $\operatorname{sbp}(v,k)$. Then

$\gamma_{e}(D)\geq v-\frac{v}{\sqrt{k}+1}$

###### Proof.

This follows directly from 6.15 and 6.13. ∎

####  6.3.2 Divisible semi-biplanes from projective planes

A classical construction of a divisible $\operatorname{sbp}(v,k)$ is given by
Hughes, Leonard, and Wilson [Hug78]. Take an involution $\varphi$ of
$\textnormal{PG}(2,q)$, i.e. an incidence-preserving map of order two. Then
either $\varphi$ is a _perspectivity_ , which means it fixes a point, called
the _centre_ of $\varphi$, and fixes a line pointwise, called the _axis_ of
$\varphi$; or $\varphi$ is a _Baer involution_ , i.e. it fixes a Baer
subplane. Take as point set the points $P$ of $\textnormal{PG}(2,q)$ not fixed
by $\varphi$, where we consider $P$ and $P^{\varphi}$ as equivalent, i.e.
$\mathcal{P}=\left\\{\left\\{P,P^{\varphi}\right\\}\,\,||\,\,P\neq
P^{\varphi}\right\\}$. For each line $l$ such that $l^{\varphi}\neq l$ define
the block $B_{l}=\left\\{\left\\{P,P^{\varphi}\right\\}\,\,||\,\,P\in
l,\,P\neq P^{\varphi}\right\\}$. Then $B_{l}=B_{l^{\varphi}}$. The biplane is
given by $(\mathcal{P},\mathcal{B})$ with
$\mathcal{B}=\left\\{B_{l}\,\,||\,\,l\neq l^{\varphi}\right\\}$. An easy
counting argument shows that a perspectivity of order 2 in
$\textnormal{PG}(2,q)$ is an _elation_ (i.e. centre and axis are incident) if
$q$ is even, and a _homology_ (i.e. the centre and axis are not incident) if
$q$ is odd. It is not difficult to verify that two perspectivities of order 2
in $\textnormal{PG}(2,q)$ must be projectively equivalent, and all Baer
involutions are projectively equivalent as well. This allows us to give a more
concrete description of the semi-biplanes described above. For more details on
involutions of projective planes, we refer to [Dem68, page 30].

Case 1. $q$ is even, $\varphi$ is an elation.

Then we can give $\textnormal{PG}(2,q)$ coordinates such that
$\varphi:(x_{0},x_{1},x_{2})\mapsto(x_{0},x_{1},x_{2}+x_{0})$. The axis of
$\varphi$ is the line $X_{0}=0$, and the centre is $(0,0,1)$. Every point not
on the axis has a unique representation $(1,x_{1},x_{2})$. We denote this
point as $(x_{1},x_{2})$. Every line not through the centre has a unique
equation of the form $X_{2}=mX_{1}+b$. We denote this line as $l_{m,b}$. Then
$(x_{1},x_{2})^{\varphi}=(x_{1},x_{2}+1)$ and $l_{m,b}^{\varphi}=l_{m,b+1}$.
If we identify each point and line with its image under $\varphi$, then
$(x_{1},x_{2})$ and $l_{m,b}$ are incident if and only if
$x_{2}+mx_{1}+b\in\left\\{0,1\right\\}$.

Inspired by Mubayi and Williford [MW07], we give the following construction of
a small edge dominating set.

######  Proposition 6.18.

Let $q\geq 128$ be an even prime power, and let $D$ be the
$\operatorname{sbp}(q^{2}/2,q)$ arising from an elation in
$\textnormal{PG}(2,q)$. Then

$\frac{q^{2}}{2}-\frac{q^{2}}{2(\sqrt{q}+1)}\leq\gamma_{e}(D)\leq\begin{cases}\frac{q^{2}}{2}-\frac{q\sqrt{q}}{4}&\text{if
$q$ is a square},\\\
\frac{q^{2}}{2}-\frac{q\sqrt{q}}{4\sqrt{2}}&\text{otherwise.}\end{cases}$

###### Proof.

The lower bound follows from 6.17, so we focus on the upper bound.

Use the notation for points and lines of this semi-biplane as described above.
Suppose that $q=2^{h}$. Let $\omega$ be a primitive element of
$\mathbb{F}_{q}$. Then $1,\omega,\dots,\omega^{h-1}$ is an
$\mathbb{F}_{2}$-basis of $\mathbb{F}_{q}$. For each $x\in\mathbb{F}_{q}$, let
$(x^{(0)},\dots,x^{(h-1)})$ denote its coordinate vector with respect to this
basis, i.e. $x=\sum_{i=0}^{h-1}x^{(i)}\omega^{i}$. Define
$f=\lfloor\frac{h}{2}\rfloor-1$, and let $F$ denote $\mathbb{F}_{2}$-span of
$1,\omega,\dots,\omega^{f}$. If we take $x_{1}$ and $x_{2}$ in $F$, then
$(x_{1}x_{2})^{(h-1)}=0$, since $2f<h-1$. Let $X$ denote the set of all points
$(x_{1},x_{2})$ with $x_{1}\in F$ and $x_{2}^{(h-1)}=0$. Let $Y$ denote the
set of all blocks $l_{m,b}$ with $m\in F$ and $b_{h-1}=1$. Then
$(x_{2}+mx_{1}+b)^{(h-1)}=1$. In particular,
$x_{2}+mx_{1}+b\notin\left\\{0,1\right\\}$, which implies that no point of $X$
is incident with a block of $Y$.

Since each point has two coordinate representatives, and likewise for the
blocks, we find an equinumerous incidence-free pair of size

$|X|=|Y|=\frac{|F|\frac{q}{2}}{2}=\frac{2^{f+1}q}{4}=\frac{2^{\lfloor\frac{h}{2}\rfloor}q}{4}=\begin{cases}\frac{q\sqrt{q}}{4}&\text{if
$h$ is even,}\\\ \frac{q\sqrt{q}}{4\sqrt{2}}&\text{if $h$ is odd.}\end{cases}$

Thus, all that is left to show that $(X,Y)$ satisfy the conditions of 5.8 with
$v=q^{2}/2$, $k=q$ and $\alpha=|X|$ as above.

First off, we have $v=q^{2}/2$ and $q\geq 128$, which is larger than
$9/5(q^{2}/2)$ and $100$ respectively. Secondly, we have indeed that $|X|\leq
q^{2}/20$ for $q\geq 128$ as $|X|\leq q\sqrt{q}/4$. Finally, take a point
$(x_{1},x_{2})$. For every value of $m$, there is a unique $b$ with
$(x_{1},x_{2})\in l_{m,b}$, hence $(x_{1},x_{2})$ lies on at most
$|F|\leq\sqrt{q}$ lines in $Y$. Equivalently, $(x_{1},x_{2})$ has at least
$q-\sqrt{q}\geq 2|X|/k$ neighbours in $\mathcal{B}\setminus Y$. ∎

Case 2. $q$ is odd, $\varphi$ is a homology.

We can choose coordinates such that
$\varphi:(x_{0},x_{1},x_{2})\mapsto(-x_{0},x_{1},x_{2})$. The axis of
$\varphi$ is the line $X_{0}=0$, the centre of $\varphi$ is $(1,0,0)$. Similar
to the previous case, we represent each point of the semi-biplane as
$(x_{1},x_{2})\neq(0,0)$, where $(x_{1},x_{2})$ and $(-x_{1},-x_{2})$ are
considered to be the same point. Every line in $\textnormal{PG}(2,q)$ distinct
from $X_{0}=0$ that misses $(1,0,0)$ has a unique equation of the form
$X_{0}=aX_{1}+bX_{2}$, $(a,b)\neq(0,0)$. Denote this line as $l_{a,b}$. Then
$l_{a,b}^{\varphi}=l_{-a,-b}$. The lines in the biplane are of the form
$l_{a,b}$ with $(x_{1},x_{2})\in l_{a,b}$ if and only if $ax_{1}+bx_{2}=\pm
1$.

######  Proposition 6.19.

Let $q\geq 11$ be odd, and let $D$ be the
$\operatorname{sbp}((q^{4}-1)/2,q^{2})$ arising from a homology in
$\textnormal{PG}(2,q^{2})$. Then

$\frac{q^{4}-1}{2}-\frac{q^{4}-1}{2q+1}\leq\gamma_{e}(D)\leq\frac{q^{4}-1}{2}-q\frac{q^{2}-1}{4}.$

###### Proof.

The lower bound again follows from 6.17.

Let $\zeta$ denote a primitive $(q+1)$st root of unity in
$\mathbb{F}_{q^{2}}$. Consider the sets

$\displaystyle X$
$\displaystyle=\left\\{(x_{1},x_{2})\,\,||\,\,x_{1}\in\mathbb{F}_{q},\,x_{2}^{q-1}\in\left\\{\zeta^{0},\dots,\zeta^{(q-1)/2}\right\\}\right\\}$
$\displaystyle Y$
$\displaystyle=\left\\{l_{a,b}\,\,||\,\,a\in\mathbb{F}_{q},\,b^{q-1}\in\left\\{\zeta^{1},\dots,\zeta^{(q+1)/2}\right\\}\right\\}$

If you take a point $(x_{1},x_{2})\in X$ and a line $l_{a,b}\in Y$, then
$ax_{1}\in\mathbb{F}_{q}$ and
$(bx_{2})^{q-1}\in\left\\{\zeta^{1},\dots,\zeta^{q}\right\\}$. In particular,
$(bx_{2})^{q-1}\notin\left\\{0,1\right\\}$, which implies that
$bx_{2}\notin\mathbb{F}_{q}$. Therefore, $ax_{1}+bx_{2}\notin\mathbb{F}_{q}$,
hence $ax_{1}+bx_{2}\neq\pm 1$. Thus, $(X,Y)$ is an equinumerous incidence-
free pair.

To calculate the size of $X$, note that there are $q$ choices for $x_{1}$,
$\frac{q+1}{2}$ choices for $x_{2}^{q-1}$, so $\frac{(q-1)(q+1)}{2}$ choices
for $x_{2}$. Since $(x_{1},x_{2})$ and $(-x_{1},-x_{2})$ are the same point
and either both or neither are in $X$, we conclude that
$|X|=|Y|=\frac{q(q^{2}-1)}{4}$.

To finish the proof, we check that the conditions of 5.8 are met. Using that
$q\geq 11$, the only non-trivial condition to check is that every point
outside of $X$ is incident with at least
$\frac{2}{q^{2}}q\frac{q^{2}-1}{4}=\frac{q^{2}-1}{2q}$ lines outside of $Y$
and vice versa. By the symmetry of the situation, we only check the condition
for points outside of $X$. So take a point $(x_{1},x_{2})\notin X$.

First suppose that $x_{2}\neq 0$. Then for every $a\notin\mathbb{F}_{q}$, the
lines $l_{a,\frac{\pm 1-ax_{1}}{x_{2}}}$ are lines outside of $Y$ incident
with $(x_{1},x_{2})$. So $(x_{1},x_{2})$ is incident with at least
$q^{2}-q>\frac{q^{2}-1}{2q}$ lines outside of $Y$.

Now suppose that $x_{2}=0$. Then $x_{1}\neq 0$, and every line $l_{\frac{\pm
1}{x_{1}},b}$ is incident with $(x_{1},x_{2})$. There are
$q^{2}-\frac{q^{2}-1}{2}=\frac{q^{2}+1}{2}$ values of $b$ such that
$b^{q-1}\notin\left\\{\zeta^{1},\dots,\zeta^{(q+1)/2}\right\\}$, so
$(x_{1},x_{2})$ is incident with at least
$\frac{q^{2}+1}{2}\geq\frac{q^{2}-1}{2q}$ lines outside of $Y$. ∎

######  Remark 6.20.

The semi-biplanes with $\varphi$ a homology and $q$ an odd non-square prime
power are left untreated. If $\mathbb{F}_{q}$ has a large subfield, a similar
construction yields a fairly large incidence-free pair. However, if
$\mathbb{F}_{q}$ does not have a large subfield, one would need some new
ideas.

Case 3. $\varphi$ is a Baer involution in $\textnormal{PG}(2,q^{2})$.

After choosing appropriate coordinates,
$\varphi:(x_{0},x_{1},x_{2})\mapsto(x_{0}^{q},x_{1}^{q},x_{2}^{q})$. The semi-
biplane then consists of the points $(x_{0},x_{1},x_{2})$ not fixed by
$\varphi$, which we identify with $(x_{0}^{q},x_{1}^{q},x_{2}^{q})$, and the
blocks $l_{a,b,c}$ with $(a,b,c)\neq(a^{q},b^{q},c^{q})$ containing the points
$(x_{0},x_{1},x_{2})$ satisfying $ax_{0}+bx_{1}+cx_{2}=0$ or
$ax_{1}^{q}+bx_{1}^{q}+cx_{2}^{q}=0$. Note that
$l_{a,b,c}=l_{a^{q},b^{q},c^{q}}$.

######  Proposition 6.21.

Let $q\geq 11$ be a prime power, and let $D$ denote the
$\operatorname{sbp}(q(q^{3}-1)/2,q^{2})$ arising from a Baer involution in
$\textnormal{PG}(2,q^{2})$. Then

$\frac{q^{4}-q}{2}-\frac{q^{4}-q}{2q+1}\leq\gamma_{e}(D)\leq\begin{cases}q\frac{q^{3}-1}{2}-\frac{q-1}{2}\frac{q^{2}+2q-1}{2}&\text{if
}q\equiv 3\pmod{4},\\\
q\frac{q^{3}-1}{2}-(q^{2}-1)\left\lfloor\frac{q}{4}\right\rfloor&\text{otherwise.}\end{cases}$

###### Proof.

The lower bound follows from 6.17.

Let $\zeta$ be a primitive $(q+1)$st root of unity in $\mathbb{F}_{q^{2}}$.
Define $f=\left\lfloor\frac{q+1}{4}\right\rfloor$. Consider the sets

$\displaystyle X$
$\displaystyle=\left\\{(x_{0},x_{1},x_{2})\,\,||\,\,(x_{0},x_{1})\in\textnormal{PG}(1,q),\,x_{2}^{q-1}\in\left\\{\zeta,\dots,\zeta^{f}\right\\}\right\\},$
$\displaystyle Y$
$\displaystyle=\left\\{l_{a,b,c}\,\,||\,\,(a,b)\in\textnormal{PG}(1,q),\,c^{q-1}\in\left\\{\zeta^{f+1},\dots,\zeta^{2f}\right\\}\right\\}.$

Take $(x_{0},x_{1},x_{2})\in X$ and $l_{a,b,c}\in Y$. Then
$ax_{0}+bx_{1}=ax_{0}^{q}+bx_{1}^{q}\in\mathbb{F}_{q}$,
$x_{2}^{q-1}=\zeta^{i}$ with $1\leq i\leq f$, and $c^{q-1}=\zeta^{j}$ with
$f+1\leq j\leq 2f$. Therefore, $(cx_{2})^{q-1}=\zeta^{i+j}$ with $f+1\leq
i+j\leq 3f$. On the other hand, since $\zeta^{q}=\zeta^{-1}$,
$(x_{2}^{q}c)^{q-1}=\zeta^{j-i}$ with $1\leq j-i\leq 2f-1$. Thus,
$(cx_{2})^{q-1}$ and $(cx_{2}^{q})^{q-1}$ are not equal to 1. This means that
$cx_{2}$ and $cx_{2}^{q}$ are not in $\mathbb{F}_{q}$, which implies that
$ax_{0}+bx_{1}+cx_{2}$ and $ax_{0}^{q}+bx_{1}^{q}+cx_{2}^{q}$ are not in
$\mathbb{F}_{q}$, so definitely not equal to 0. Hence, no point of $X$ lies on
a block of $Y$.

For every $(q+1)$st root of unity $\zeta^{i}$, there are $q-1$ elements
$x_{2}$ with $x_{2}^{q-1}=\zeta^{i}$, which in fact form a multiplicative
coset of $\mathbb{F}_{q}^{*}$. Hence, $|X|=(q+1)(q-1)f$. Note that we do not
count any points twice under the equivalence
$(x_{0},x_{1},x_{2})=(x_{0}^{q},x_{1}^{q},x_{2}^{q})$, since
$(x_{0},x_{1})\in\textnormal{PG}(1,q)$ implies that
$(x_{0}^{q},x_{1}^{q})=(x_{0},x_{1})$, and
$x_{2}^{q-1}\in\left\\{\zeta,\dots,\zeta^{f}\right\\}$ implies that
$(x_{2}^{q})^{q-1}\in\left\\{\zeta^{q},\dots,\zeta^{q+1-f}\right\\}$.

For the set $Y$, things are a little more delicate. If $f=\frac{q+1}{4}$, i.e.
$q\equiv 3\pmod{4}$, we must beware that if $c^{q-1}=\zeta^{2f}$, then
$l_{a,b,c}$ and $l_{a,b,c^{q}}$ define the same line, but $(c^{q})^{q-1}$ also
equals $\zeta^{2f}$. Thus, in this case, the size of $Y$ equals
$(q+1)((f-1)(q-1)+\frac{q-1}{2})=(q^{2}-1)\frac{q-1}{4}$. Consider the blocks
$l_{a,1,0}$ with $a\notin\mathbb{F}_{q}$. If $(x_{0},x_{1},x_{2})\in X$, then
$ax_{0}+x_{1}$ cannot be zero, since $ax_{0}\notin\mathbb{F}_{q}$ and
$x_{1}\in\mathbb{F}_{q}$. There are $\frac{q^{2}-q}{2}$ such blocks. Define
$Y^{\prime}=Y\cup\left\\{l_{a,1,0}\,\,||\,\,a\notin\mathbb{F}_{q}\right\\}$.
Then $|Y^{\prime}|=|X|-\frac{q-1}{2}$. So we can delete $\frac{q-1}{2}$ points
from $X$ to obtain a subset $X^{\prime}$. Then $(X^{\prime},Y^{\prime})$ is an
equinumerous incidence-free pair.

To finish the proof, one can again check that the conditions of 5.8 are
satisfied. Apart from some elementary inequalities, one needs to observe that
every point $(x_{0},x_{1},x_{2})$ in $\mathcal{P}\setminus X$ is contained in
at most $q+1$ blocks of $Y$. First suppose that $x_{2}=0$ so that we can write
it as $(x_{0},1,0)$ with $x_{0}\notin\mathbb{F}_{q}$. Then it cannot be
incident with a block in $Y$ as otherwise $ax_{0}+b=0$ or $ax_{0}^{q}+b=0$
leads to the contradiction that $x_{0}\in\mathbb{F}_{q}$. Now suppose that
$x_{2}\neq 0$. Choose $(a,b)\in\textnormal{PG}(1,q)$, then
$ax_{0}+bx_{1}+cx_{2}=0$ has a unique solution for $c$. Hence for this choice
of $(a,b)$, there is at most one $l_{a,b,c}\in Y$ incident with the point
$(x_{0},x_{1},x_{2})$. ∎

####  6.3.3 Semi-biplanes from binary affine spaces

In this subsection, we consider another large family of semi-biplanes. They
are no longer divisible, but we can still find lower bounds on the edge-
domination number, emphasising the flexibility of the approach based on
eigenvalues. In one particular member of this family of semi-biplanes, we will
construct a large equinumerous incidence-free pair in an SIS that will not
give rise to an edge dominating set. This shows the necessity of some extra
conditions in 5.8 when compared with 5.1.

Consider the $n$-dimensional affine space over $\mathbb{F}_{2}$, denoted
$\textnormal{AG}(n,2)$. Give coordinates to the points. The _weight_ of a
point is the number of coordinate positions in which the point has a non-zero
entry. Let $W$ and $\mathcal{P}$ denote the sets of points of odd and even
weight, respectively. Consider a set $S\subseteq W$ of size $k$ such that

  * •

the (affine) span of $S$ is $W$,

  * •

$S$ does not fully contain any (affine) plane of $\textnormal{AG}(n,2)$.

Define $\mathcal{B}=\left\\{y+S\,\,||\,\,y\in W\right\\}$. Then
$D=(\mathcal{P},\mathcal{B})$ is an $\operatorname{sbp}(2^{n-1},k)$, see
[Wil95].

######  Lemma 6.22.

Let $\mathcal{H}$ denote the set of all affine hyperplanes of $W$. Then the
spectrum of the adjacency matrix of $I(D)$ equals the multiset

$\left\\{\pm k\right\\}\cup\left\\{k-2|H\cap
S|\,\,||\,\,H\in\mathcal{H}\right\\}.$

###### Proof.

As in 6.15, let $N$ denote the incidence matrix of the semi-biplane, and $A$
the adjacency matrix of its collinearity graph. Then $NN^{t}=kI+2A$, and the
spectrum of the adjacency matrix of $I(D)$ can be derived from the spectrum of
$NN^{t}$.

Denote $S^{+}=\left\\{s+t\,\,||\,\,s,t\in S,\,s\neq t\right\\}$. The planes in
$\textnormal{AG}(n,2)$ are exactly the sets of four distinct points whose
total sum is the zero vector. Since $S$ does not contain any plane, $s+t$
uniquely determines $\left\\{s,t\right\\}\subseteq S$, and
$|S^{+}|=\binom{k}{2}$. Furthermore, two distinct points $x,z\in\mathcal{P}$
are collinear if and only if $x,z\in y+S$ for some $y\in W$. This is
equivalent to $x=y+s$ and $z=y+t$ for some $y\in W$, and some $s,t\in S$. This
again is equivalent to $x+s=z+t$ for some $s,t\in S$, since this immediately
implies that $x+s=z+t\in W$. The last statement is equivalent to $x+z\in
S^{+}$. In conclusion, $x$ and $z$ are collinear if and only if $x+z\in
S^{+}$.

We can now use [BVM22, §7.1] to conclude that the spectrum of $A$ equals the
multiset

$\left\\{\binom{k}{2}\right\\}\cup\left\\{2|H\cap
S^{+}|-|S^{+}|\,\,||\,\,H\text{ a hyperplane of $\mathcal{P}$ through
}\mathbf{0}\right\\}.$

Consider the standard inner product $x\cdot y=\sum_{i}x_{i}y_{i}$ on
$\textnormal{AG}(n,2)$. Every hyperplane $H$ in $\mathcal{P}$ through
$\mathbf{0}$ is of the form $X\cdot a=0$ for some
$a\in\mathcal{P}\setminus\left\\{\mathbf{0},\mathbf{1}\right\\}$. Then $H$ is
an $(n-2)$-space in $\textnormal{AG}(n,2)$. There are three hyperplanes in
$\textnormal{AG}(n,2)$ through $H$, namely $H_{0}$ with equation $X\cdot a=0$,
$H_{1}$ with equation $X\cdot(a+\mathbf{1})=0$, and $\mathcal{P}$. Then
$H_{0}\cap W$ and $H_{1}\cap W$ are parallel hyperplanes of $W$, partitioning
the points. Take a point $x$ in $S^{+}$. There exist unique $s$ and $t$ in $S$
such that $x=s+t$. Then

$x\notin H\iff x\cdot a=1\iff s\cdot a\neq t\cdot a.$

Thus, $|S^{+}\setminus H|$ equals the number of ways to choose an element of
$s\in S\cap H_{0}$ and an element $t\in S\cap H_{1}$. If $|S\cap H_{0}|=m$,
then $|S\cap H_{1}|=k-m$. Hence,

$2|H\cap S^{+}|-|S^{+}|=|S^{+}|-2|H\setminus S^{+}|=\binom{k}{2}-2m(k-m)$

This gives an eigenvalue

$k+2\left(\binom{k}{2}-2m(k-m)\right)=k+k(k-1)-4m(k-m)=k^{2}-4m(k-m)=(k-2m)^{2}$

of $NN^{t}$. This gives us eigenvalues $k-2m$ and $-(k-2m)$ of the adjacency
matrix of $I(D)$. Note that if $k-2|S\cap H_{0}|=k-2m$, then $k-2|S\cap
H_{1}|=-(k-2m)$. Lastly, the eigenvalue $\binom{k}{2}$ of $A$, gives us the
eigenvalue $k^{2}$ of $NN^{t}$, hence the eigenvalues $\pm k$ of the adjacency
matrix of $I(D)$. This proves the statement of the lemma. ∎

The following lower bound on the edge domination number of $I(D)$ follows
directly from 6.13.

######  Lemma 6.23.

Let $W$ denote the hyperplane of odd-weight points in $\textnormal{AG}(n,2)$,
and let $S$ be a subset spanning $W$, not containing a plane. Denote the
associated $\operatorname{sbp}(2^{n-1},k)$ by $D$. Let $m$ denote the maximum
number of points of $S$ contained in a hyperplane of $W$. Then

$\gamma_{e}(D)\geq\frac{k}{m}2^{n-2}.$

######  Remark 6.24.

Let $S$ be the set of weight one vectors. In this
$\operatorname{sbp}(2^{n-1},n)$, we can construct a large incidence-free set
by taking $X$ to be the set of even weight vectors with weight at most
$\left\lfloor n/2\right\rfloor-1$ while we take $Y$ to be the set of blocks
$y+S$, where $y$ runs over the odd weight vectors with weight at least
$\left\lceil n/2\right\rceil+1$. By taking subsets, we can easily find a large
equinumerous incidence-free pair of sets, but it will not give rise to a small
edge dominating set in its complement. This is easily seen, as a point
corresponding to a vector of even weight at least $\left\lceil
n/2\right\rceil+2$ has no neighbours in $\mathcal{B}\setminus Y$. This example
reaffirms that an assumption like the minimum degree condition in 5.8 is
necessary, even though $I(D)$ is connected.

##  7 Conclusion

In this paper, we studied the edge domination number $\gamma_{e}(D)$ of
incidence structures $D$ through its connections with maximal matchings and
incidence-free sets. In almost all families we studied, we saw that
$\gamma_{e}(D)=(1-o(1))v$, so the interesting quantity to study is
$v-\gamma_{e}(D)$. Using a combination of probabilistic, combinatorial and
geometric techniques, supplemented with tools from spectral graph theory, we
made headway on bounding the edge domination number of various designs, often
obtaining sharp bounds on $v-\gamma_{e}(D)$ up to a constant factor.
Nevertheless, many problems remain open, and we state a few of them here.

######  Problem 7.1.

What is the edge domination number for non-Desarguesian projective planes? Can
one construct large incidence-free pairs?

Various classes of symmetric designs are constructed using difference sets
[CD06, Section 6.8]. Quite a few of them are difference sets in cyclic groups.

######  Problem 7.2.

Is it possible to construct incidence-free pairs in a ‘uniform’ way for
symmetric designs coming from difference sets? That is, without resorting to
the specific structure of the difference set, but only using properties of the
group?

If $G$ is a group with difference set $S$, one can translate this problem to
finding so-called cross-intersecting independent sets in the (directed) Cayley
graph $C(G,S)$ where we have an arc between two distinct elements $x$ and $y$
if $xy^{-1}\in S$.

The following problem asks if we can improve our general lower bound from 4.1.

######  Problem 7.3.

Can we always find equinumerous incidence-free pairs of size
$k^{1+\varepsilon}/\lambda$ in a symmetric $(v,k,\lambda)$-design for small
$\lambda$?

It seems plausible that such incidence-free pairs should always exist for
symmetric designs, but we do not necessarily think it should hold for SIS’s in
general. Finding an example of such an SIS (if it exists) would also be of
significant interest.

## References

  * [BBM97] S. Ball, A. Blokhuis, and F. Mazzocca.  Maximal arcs in Desarguesian planes of odd order do not exist.  Combinatorica, 17(1):31–41, 1997.
  * [BVM22] A. E. Brouwer and H. Van Maldeghem.  Strongly regular graphs, volume 182 of Encyclopedia of Mathematics and its Applications.  Cambridge University Press, Cambridge, 2022.
  * [CD06] C. J. Colbourn and J. H. Dinitz, editors.  Handbook of Combinatorial Designs.  Taylor Francis, 2006.
  * [CDJHH04] E. Cockayne, P. Dreyer Jr, S. Hedetniemi, and S. Hedetniemi.  Roman domination in graphs.  Discrete mathematics, 278(1-3):11–22, 2004.
  * [Dem68] P. Dembowski.  Finite geometries.  Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 44. Springer-Verlag, Berlin-New York, 1968.
  * [Den69] R. H. F. Denniston.  Some maximal arcs in finite projective planes.  J. Combinatorial Theory, 6:317–319, 1969.
  * [DWSV12] S. De Winter, J. Schillewaert, and J. Verstraete.  Large incidence-free sets in geometries.  Electron. J. Combin., 19(4):Paper 24, 16, 2012.
  * [Ehr15] R. Ehrenhorg.  An unbiased marriage theorem.  Amer. Math. Monthly, 122(1):59, 2015.
  * [EPASZ18] A. Elvey Price, M. Adib Surani, and S. Zhou.  The isoperimetric number of the incidence graph of ${\rm PG}(n,q)$.  Electron. J. Combin., 25(3):Paper No. 3.20, 15, 2018.
  * [GRM14] F. Goldberg, D. Rajendraprasad, and R. Mathew.  Domination in designs.  arXiv preprint arXiv:1405.3436, 2014.
  * [Hae95] W. H. Haemers.  Interlacing eigenvalues and graphs.  Linear Algebra Appl., 226/228:593–616, 1995.
  * [HHL20] T. Héger and L. Hernandez Lucas.  Dominating sets in finite generalized quadrangles.  Ars Math. Contemp., 19(1):61–76, 2020.
  * [HHS98] T. W. Haynes, S. T. Hedetniemi, and P. J. Slater.  Fundamentals of domination in graphs, volume 208 of Monographs and Textbooks in Pure and Applied Mathematics.  Marcel Dekker, Inc., New York, 1998.
  * [HK93] J. Horton and K. Kilakos.  Minimum edge dominating sets.  SIAM Journal on Discrete Mathematics, 6(3):375–387, 1993.
  * [HN17] T. Héger and Z. L. Nagy.  Dominating sets in projective planes.  J. Combin. Des., 25(7):293–309, 2017.
  * [Hug78] D. Hughes.  Biplanes and semi-biplanes.  In Combinatorial mathematics (Proc. Internat. Conf. Combinatorial Theory, Australian Nat. Univ., Canberra, 1977), volume 686 of Lecture Notes in Math., pages 55–58. Springer, Berlin, 1978\.
  * [HY13] M. A. Henning and A. Yeo.  Total domination in graphs.  Springer Monographs in Mathematics. Springer, New York, 2013.
  * [IS06] Y. J. Ionin and M. S. Shrikhande.  Combinatorics of symmetric designs, volume 5 of New Mathematical Monographs.  Cambridge University Press, Cambridge, 2006.
  * [Kan85] W. M. Kantor.  Classification of $2$-transitive symmetric designs.  Graphs Combin., 1(2):165–166, 1985.
  * [KST54] T. Kövari, V. T. Sós, and P. Turán.  On a problem of K. Zarankiewicz.  Colloq. Math., 3:50–57, 1954.
  * [LW99] R. Laskar and C. Wallis.  Chessboard graphs, related designs, and domination parameters.  J. Statist. Plann. Inference, 76(1-2):285–294, 1999.
  * [MPS19] S. Mattheus, F. Pavese, and L. Storme.  On the independence number of graphs related to a polarity.  J. Graph Theory, 92(2):96–110, 2019.
  * [MW07] D. Mubayi and J. Williford.  On the independence number of the Erdős-Rényi and projective norm graphs and a related hypergraph.  J. Graph Theory, 56(2):113–127, 2007.
  * [MX06] M. Muzychuk and Q. Xiang.  Symmetric Bush-type Hadamard matrices of order $4m^{4}$ exist for all odd $m$.  Proc. Amer. Math. Soc., 134(8):2197–2204, 2006.
  * [Pal33] R. E. A. C. Paley.  On orthogonal matrices.  Journal of Mathematics and Physics, 12(1-4):311–320, 1933.
  * [Sti13] D. R. Stinson.  Nonincident points and blocks in designs.  Discrete Math., 313(4):447–452, 2013.
  * [Tho89] A. Thomason.  Dense expanders and pseudo-random bipartite graphs.  In B. Bollobás, editor, Graph Theory and combinatorics 1988, volume 43 of Annals of Discrete Mathematics, pages 381–386. Elsevier, 1989\.
  * [TZC19] L. Tang, S. Zhou, and J. Chen.  Domination number of incidence graphs of block designs.  Appl. Math. Comput., 363:124600, 6, 2019.
  * [Wil81] P. Wild.  Divisible semisymmetric designs.  In Combinatorial mathematics, VIII (Geelong, 1980), volume 884 of Lecture Notes in Math., pages 346–350. Springer, Berlin-New York, 1981.
  * [Wil95] P. Wild.  Some families of semibiplanes.  Discrete Math., 138(1-3):397–403, 1995.
  * [YG80] M. Yannakakis and F. Gavril.  Edge dominating sets in graphs.  SIAM J. Appl. Math., 38(3):364–372, 1980.