# Lovasz’ Conjecture and Other Applications of Topological Methods in Discrete
Mathematics

Jingsi Hou, Guangyan Huang, Sammy Suliman, Haoran Yan

(September 2022)

##  1 Background

In 20th century mathematics, the field of topology, which concerns the
properties of geometric objects under continuous transformation, has proved
surprisingly useful in application to the study of discrete mathematics, such
as combinatorics, graph theory, and theoretical computer science. In this
paper, we seek to provide an introduction to the relevant topological concepts
to non-specialists, as well as a selection of some existing applications to
theorems in discrete mathematics.

##  2 Introductory Topology

Topology is the study of continuously deformable objects. To rigorously define
this, we begin by introducing the concept of a homeomorphism. Two objects are
homeomorphic if there exist a continuous bijection between them with a
continuous inverse. For example, a square and a circle are homeomorphic. While
an explicit map may not immediately clear (see [1]), its existence is made
intuitively evident by inflating the edges of the square into a circle. On the
other hand, a homeomorphism does not exist between the torus, the geometric
shape formed by revolving a circle in $\mathds{R}^{3}$ about an axis
(visually, a hollow doughnut), and a sphere in $\mathds{R}^{3}$. If X and Y
are two homeomorphic topological spaces, we denote this as $X\cong Y$.

Next, we introduce affine independence, a generalisation of the more familiar
concept of linear independence to point sets. A set of $k+1$ points
$v_{0},...,v_{k}$ is said to be affinely independent if there exist real
numbers not $a_{0},...,a_{k}$ not all zero such that
$\sum_{i=0}^{d}a_{i}v_{i}=0$ and $\sum_{i=0}^{k}a_{i}=0$. We can express this
in a form more familiar to students of linear algebra, in that the $k$-vectors
$v_{k}-v_{0},...,v_{1}-v_{0}$ are linearly independent. Therefore, a set of 2
distinct points is automatically affinely independent, a set of 3 distinct
points are affinely independent if they do not lie on a common line, etc.

Now we will introduce the simplex, which generalises the notion of a triangle
into arbitrary dimensions. Formally, a simplex is defined as the convex hull
of a finite affinely independent point set. Thus, a simplex in
$\mathds{R}^{1}$ is a line segment as this forms the most ”efficient” possible
connection between any 2 points. Similarly, a simplex in $\mathds{R}^{2}$ is a
triangle as no other shape can be drawn that encompasses all connections
between 3 affinely independent points with fewer line segments. Extensions
into higher-dimensional spaces can be made similarly. A face of a simplex is
the convex hull of an arbitrary subset of vertices of the simplex, which forms
a lower-dimensional simplex of its own right by definition.

A simplicial complex is defined as a set of simplicies satisfying the
properties that each face of a simplex is included within the set and that
every intersection between 2 simplices must be a face of both. Below are some
pictured examples of some families of simplices that satisfy and violate the
conditions:

Credit: Matoušek

The common understanding of a polyhedra can thus be represented a union of a
simplicial complex and is denoted $||\triangle||$.

A triangulation of any topological space $X$ is a simplicial complex
$\triangle$ such that $X\cong||\triangle||$. This results in a simplicial
complex that can be ”smoothed” back into the original shape through continuous
deformation.

The triangulation of a torus. Credit: https://math.stackexchange.com/

Having introduced the necessary topological background, we now proceed to
stating the Borsuk-Ulam Theorem, which will be of keen interest as we seek to
prove theorems in discrete mathematics.

##  3 The Borsuk-Ulam Theorem and Equivalent Results

Let $S^{n}$ denote the unit sphere in $\mathds{R}^{n-1}$. That is, $S^{1}$ is
a circle, $S^{2}$ is a traditional sphere, and so on. The Borsuk-Ulam Theorem
states the following:

######  Borsuk-Ulam Theorem.

For every continuous mapping $f:S^{n}\rightarrow\mathds{R}^{n}$ there exists a
point $x\in S^{n}$ with $f(x)=f(-x)$.

The points $x,-x$ are referred to as antipodal points. The canonical example
of this phenomena is that there exist 2 antipodal points on the globe where
temperature and barometric position are equal (assuming temperature and
barometric pressure to be continuous maps).

In order to aid the transition to a combinatorial / graph-theoretic viewpoint,
we now present 2 equivalent formulations of the theorem in the language of
discrete mathematics.

######  Tucker’s Lemma.

Let $T$ be a triangulation of $B^{n}$ that is antipodally symmetric on the
boundary. Let $\lambda:V(T)\rightarrow\\{+1,-1,+2,-2,...,+n,-n\\}$ be a
labeling of the vertices of $T$ that satisfies $\lambda(-v)=-\lambda(v)$ for
every vertex $v\in\partial B^{n}$ (that is, $\lambda$ is antipodal on the
boundary). Then there exists a 1-simplex (an edge) in $T$ that is
complementary; i.e., its two vertices are labeled by opposite numbers.

######  Lusternik–Schnirelmann Theorem.

Whenever $S^{n}$ is covered by $n+1$ sets $A_{1},A_{2},...,A_{n+1}$, each
$A_{i}$ open or closed, there is an $i$ such that $x,-x\in A_{i}$.

##  4 The Ham Sandwich Theorem

######  Ham Sandwich Theorem for Measures.

Let $\mu_{1},\mu_{2},...,\mu_{d}$ be finite Borel measures on $\mathds{R}^{d}$
such that every hyperplane has measure $0$ for each of the $\mu_{i}$. Then
there exists a hyperplane $h$ such that
$\mu_{i}(h^{+})=\frac{1}{2}\mu_{i}(\mathds{R}^{d})$ for $i=1,2,...,d$, where
$h^{+}$ denotes one of the half-spaces defined by $h$.

The theorem derives its informal name from the case $n=3$, where the Borel
measures in questions take the form of 2 pieces of bread and a slice of ham.
In this case, the ham sandwich theorem guarantees that there exists a planar
cut with a knife that divides both pieces of bread and ham precisely in two.

###### Proof.

First, let us consider $\textbf{u}=(u_{0},u_{1},...,u_{d})$ a point on sphere
$S^{d}$. If not all of the components in $u$ are zeros, we define

$h^{+}(u):=\\{(x_{1},...,x_{d})\in\mathbb{R}^{d}:u_{1}x_{1}+...+u_{d}x_{d}\leq
u_{0}\\}$

Consider the half-space assigned to the antipodal point
$\textbf{-u}=(-u_{0},-u_{1},...,-u_{d})$, as defined

$h^{+}(-u):=\\{(x_{1},...,x_{d})\in\mathbb{R}^{d}:u_{1}x_{1}+...+u_{d}x_{d}\geq
u_{0}\\}$

We now choose u = (1,0,…,0) and -u = (-1,0,…,0), so we have

$h^{+}(u):=\\{(x_{1},...,x_{d})\in\mathbb{R}^{d}:0\leq 1\\}=\mathbb{R}^{d}(*)$
$h^{+}(-u):=\\{(x_{1},...,x_{d})\in R^{d}:0\geq 1\\}=\emptyset(**)$

We now define a new family of functions $f_{i}:S^{d}\rightarrow\mathbb{R}^{d}$
by

$f_{i}(u):=\mu_{i}(h^{+}(u))$

If we want to apply to the Borsuk-Ulam Theorem, we need to check the antipodal
mapping first. Let $f(u_{0})=f(-u_{0})$ for some $u_{0}\in S^{d}$, then by (*)
and (**), we know that $h^{+}(u_{0})$ is a half-space. As defined, every
hyperplane has measure 0, so there exist $u\in S^{d}$ such that $f(u)=0$,
thereby satisfying the antipodal mapping. Next, we will check the continuity
of $f$. Let $(u_{n})^{\infty}_{n=1}$ be a sequence of points of $S^{d}$
converging to u. Our goal is to prove
$\mu_{i}(h^{+}(u_{n}))\rightarrow\mu_{i}(h^{+}(u))$. By assumption, if
$x\not\in\partial h^{+}(u)$, then $x\in h^{+}(u_{n})$ if and only if $x\in
h^{+}(u)$ for all n sufficiently large. Now define the characteristic function
of $h^{+}(u)$

$g(x)=1,x\in h^{+}(u)$ $g(x)=0,x\not\in h^{+}(u)$

Similarly, define the characteristic function of $h^{+}(u_{n})$

$g_{n}(x)=1,x\in h^{+}(u_{n})$ $g_{n}(x)=0,x\not\in h^{+}(u_{n})$

So, $g_{n}(x)\rightarrow g(x)$ for all $x\not\in\partial h^{+}(u)$. By
assumption, $\mu_{i}(\partial(h^{+}(u))=0$, so (add reference),
$\mu_{i}(\partial(h^{+}(u_{n}))=\int g_{n}d\mu_{i}\rightarrow\int
gd\mu_{i}=\mu_{i}(\partial(h^{+}(u))$ ∎

######  Ham Sandwich Theorem for Point Sets.

Let $A_{1},A_{2},...,A_{d}\subset\mathbb{R}^{d}$ be finite point sets. Then
there exists a hyperplane $h$ that simultaneously bisects
$A_{1},A_{2},...,A_{d}$.

Note: If a hyperplane $h$ bisects $A_{i}$ with $2k+1$ points, then each open
half-space defined by $h$ contains at most $k$ points, which means at least
one point lies on the hyperplane $h$.

###### Proof.

The general idea of this proof is to replace the points sets with small balls
then apply the Ham Sandwich Theorem for measures. In order to do this, we will
introduce the following definition:

######  Definition.

Finite point sets $A_{1},A_{2},...,A_{d}$ are in general position in
$\mathds{R}^{d}$ if each distinct $A_{i}$ disjoint and no more than $d$ points
of any set lie on a common hyperplane.

A point set in general position in $\mathds{R}^{3}$.

First, we suppose each $A_{i}$ has odd number of points and
$A_{1}\dot{\cup}A_{2}\dot{\cup}...\dot{\cup}A_{d}$ is in general position. Now
let $A_{i}^{\epsilon}$ be balls sets by replacing each point in $A_{i}$ with a
solid ball of radius $\epsilon$ that is small enough such that no hyperplane
can intersect more than d balls of $\cup A_{i}^{\epsilon}$. By the Ham
Sandwich Theorem for measures, we can find a hyperplane $h$ bisecting the sets
$A_{i}^{\epsilon}$ at the same time. Since each $A_{i}$ has odd cardinality,
then at least one point must lie on the hyperplane $h$. Since no more than $d$
balls can be intersected simultaneously, then $h$ intersects only one ball of
each $A_{i}^{\epsilon}$. It means $h$ passes through the center of this ball,
thereby $h$ bisects each $A_{i}$.

Second, we still suppose that each $A_{i}$ has odd number of points but the
position of $A_{1}\dot{\cup}A_{2}\dot{\cup}...\dot{\cup}A_{d}$ can be random.
We use a perturbation argument to construct them in general position. For
every $\eta>0$, let ${A_{i}}_{\eta}$ be point sets by moving each point in
$A_{i}$ by at most $\eta$ so that
${A_{1}}_{\eta}\dot{\cup}{A_{2}}_{\eta}\dot{\cup}...\dot{\cup}{A_{d}}_{\eta}$
is in general position. So we can find a hyperplane $h_{\eta}$ bisecting
${A_{i}}_{\eta}$. So define

$h_{\eta}=\\{x\in\mathbb{R}^{d}:\langle a_{\eta},x\rangle=b_{\eta}\\}$

where $a_{\eta}$ is a unit vector, so $b_{\eta}$ lies in a bounded interval
for $\eta$ small enough. By the Bolzano-Weierstrass Theorem, as
$\eta\rightarrow 0$, for every pair $(a_{\eta},b_{\eta})$ there exists a limit
point $(a,b)\in\mathbb{R}^{d+1}$ Now, let $h$ be the hyperplane obtained from
$\langle a,x\rangle=b$. Next, let $\eta_{1}>\eta_{2}>...$ be a sequence
converging to 0 satisfying $(a_{\eta_{j}},b_{\eta_{j}})\rightarrow(a,b)$.
Consider a point $x$ is $\delta>0$ away from hyperplane $h$, then for $j$
sufficiently large, it is at least $\frac{1}{2}\delta$ away from
$h_{\eta_{j}}$. Now, consider that we have $k$ points of $A_{i}$ in one open
half-space generated by $h$, then for all $j$ sufficiently large, the
corresponding open half-space generated by $h_{\eta_{j}}$ contains at least
$k$ points of $A_{i,\eta_{j}}$. Therefore, we still achieve a bisection of
$A_{i}$ without the general position in our assumption.

Third, let some of the $A_{i}$ have an even cardinality. By deleting and
adding one random point from each even-sized $A_{i}$, we can still check the
bisection. ∎

######  Ham Sandwich Theorem (General Position Version).

Let $A_{1},A_{2},...,A_{d}\\\ \subset\mathbb{R}^{d}$ be disjoint finite point
sets in general position. Then there exists a hyperplane h that bisects each
$A_{i}$, such that there are exactly $\lfloor\frac{1}{2}|A_{i}|\rfloor$ points
from $A_{i}$ in each of the open half-spaces defined by $h$, and at most one
point of $A_{i}$ on the hyperplane $h$.

###### Proof.

By Ham Sandwich Theorem for point sets, we choose a random hyperplane $h$ such
that simultaneously bisects $A_{1},A_{2},...,A_{d}$. We now reassign our
coordinate system to let $h$ be the horizontal hyperplane $x_{d}=0$. We now
define

$B:=h\cap(A_{1}\cup...\cup A_{d}).$

We claim that $B$ consists of at most $d$ affinely independent points. By
assumption, $A_{i}$ is in general position, so there are at most d points on
$B$. Suppose there exists $x$ points that are affinely dependent, then the
hyperplane will require at least $d-x+1$ points to generate, which is a
violation of the general position assumption.

We now add $d-|B|$ points to $B$ to get a $C\subset h$ with d affinely
independent points. Since the points of $C$ are affinely independent, then for
each $a\in C$, we can determine another $a^{\prime}$ such that $a^{\prime}=a$,
or $a^{\prime}=a+\epsilon e_{d}$, or $a^{\prime}=a-\epsilon e_{d}$. We let
$h^{\prime}=h^{\prime}(\epsilon)$ be the desired hyperplane. ∎

##  5 On Multicolored Partitions and Necklaces

We begin with an easy result to establish the relevance of the ham sandwich
theorem in multicolored partition problems.

######  Theorem.

Consider sets $A_{1},A_{2},...,A_{d}$, of $n$ points each, in general position
in $\mathds{R}^{d}$; imagine that the points of $A_{1}$ are red, the points of
$A_{2}$ blue, etc. (each $A_{i}$ has its own color). Then the points of the
union $A_{1}\cup...\cup A_{d}$ can be partitioned into “rainbow” d-tuples
(each d-tuple contains one point of each color) with disjoint convex hulls.

For a visual understanding of the theorem, consider the below illustration:

###### Proof.

: First, let us consider the case where $n$ is an even number. By the general
position version of the ham sandwich theorem, there exists a hyperplane which
bisects all the $A_{i}$ with no points lying on the hyperplane. For $n$ odd,
there exists a hyperplane that simultaneously bisects all $d$ point sets such
that exactly one point from each set lies on the plane by the ham sandwich
theorem for point sets in general position. We will let the convex hull
connecting the points on this plane be the first of the rainbow $d$-tuples. We
then recursively split the points remaining on both half-planes formed on
either side of the initial hyperplane, according to the following algorithm:

\- If the number of points in each half-plane, divide these points evenly in
half with a hyperplane by the ham sandwich theorem.

\- If the number of points in each half-plane is odd, apply the previously
mentioned version of the ham sandwich theorem, such that one point of each
$A_{i}$ remains on the plane. This will form another rainbow $d$-tuple.

Eventually, there will be exactly $d$ points of different colors lying on each
side of the hyperplane, which we can place onto a convex hull. Thus, every
point in the union of point sets now lies on a disjoint rainbow convex hull. ∎

We now proceed to tackling the necklace-splitting problem.

######  The Necklace-Splitting Problem.

Infamous jewel thieves G. Huang and H. Yan steal an invaluable necklace. The
necklace is so valuable not only because of the precious gems it contains, but
because they are embedded in solid gold. Huang and Yan want to split the
jewels evenly between themselves while wasting as little gold as possible. In
how few cuts is this possible?

Luckily, Huang and Yan are accomplished mathematicians and are familiar with
the following theorem:

######  Necklace Theorem.

Every (open) necklace with $d$ kinds of stones can be divided between two
thieves using no more than $d$ cuts.

Before we begin our proof, we require the following definition and lemma.

######  Definition.

A moment curve ($\gamma$) is the curve in $\mathds{R}^{d}$ given by the
parametric equation $(t,t^{2},t^{3},...,t^{d})$

######  Lemma.

No hyperplane intersects the moment curve $\gamma$ in $\mathds{R}^{d}$ in more
than $d$ points

###### Proof of Lemma.

A hyperplane $h$ has an equation $a_{1}x_{1}+a_{2}x_{2}+···+a_{d}x_{d}=b$ with
$(a_{1},a_{2},...,a_{d})$. To find all intersections between $h$ and $\gamma$,
we substitute $\gamma$ in for $h$ and receive
$a_{1}t+a_{2}t^{2}+...+a_{d}t^{d}=b$. Therefore, the values of $h$ at which
$\gamma$ intersects are the roots of the equation
$0=a_{1}t+a_{2}t^{2}+...+a_{d}t^{d}$, which has no more than $d$ solutions. ∎

We may now proceed to proving the Necklace Theorem.

###### Proof of Theorem.

We place our necklace in $\mathds{R}^{d}$ along the moment curve $\gamma$. We
define a system of sets $A_{i}$, where the points of $A_{i}$ are stones of the
$i$-th kind. By the discrete general position version of the ham sandwich
theorem, there exists a hyperplane $h$ that simultaneously bisects each
$A_{i}$. By Lemma 0, $h$ cuts $\gamma$ (and thus the necklace) at no more than
$d$ points. Assuming all sets $A_{i}$ have the same size, no stones lie on
$h$, and thus we have an even division. ∎

There exists a second topologically-inspired proof for the Necklace Theorem.
Before tackling this proof, we require the use of the following lemma, a
continuous version of the necklace theorem:

######  Lemma (Hobby-Rice Theorem).

Let $\mu_{1}$, $\mu_{2}$, …, $\mu_{d}$ be continuous probability measures on
$[0,1]$. Then there exists a partition of $[0,1]$ into $d+1$ intervals
$I_{0},I_{1},...,I_{d}$ (using $d$ cut points) and signs
$\epsilon_{1},\epsilon_{2},...,\epsilon_{d}\in\\{-1,+1\\}$ with
$\sum_{j=0}^{d}\epsilon_{j}\cdot\mu_{i}(I_{j})=0$ for $i=1,2,...,d$.

###### Proof.

For every point $\textbf{x}=(x_{1},x_{2},...,x_{d})$ of the sphere $S^{d}$, we
associate a division of the interval $[0,1]$ into $d+1$ parts, with lengths
$x_{1}^{2},x_{2}^{2},...,x_{d}^{2}$. For example, the point $(1,0,0)$ on the
sphere in $\mathds{R}^{d}$ is associated with the unbroken interval $[0,1]$.
Specifically, each cut on the interval is made at the point $z_{i}$, where
$z_{i}=x_{1}^{2}+...+x_{i}^{2}$ for any $i$ between $0$ and $d+1$, inclusive.
The sign $\epsilon_{j}$ for the interval $I_{j}=[z_{j-1},z_{j}]$ is chosen as
the sign of the coordinate $x_{j}$. From this, we may define a function
$g:S^{d}\rightarrow\mathds{R}^{d}$, where $g(x)=\sum_{j=1}^{d+1}$
sign$(x_{j})\cdot\mu_{i}([z_{j-1},z_{j}])$. We can interpret $g$ as allocating
the measure of the intervals associated with positive sign to the first thief,
and the measure of the intervals associated with the negative sign to the
second thief. $g$ is continuous, since each $\mu_{i}$ is a continuous
probability measure. $g$ is also antipodal, as multiplying $x$ by $-1$
reverses the sign of the coordinate $x_{j}$ while the probability measure
$\mu_{i}([z_{j-1},z_{j}])$ remains the same, such that $g(-x)=-g(x)$.
Therefore, by the Borsuk-Ulam theorem, there exists an x such that
$g(\textbf{x})=0$. This implies that the amount of measure allocated to the
first thief is exactly the same as the amount allocated to the second thief.
Hence, there exists a just division under this x. ∎

We may now proceed to proving the Necklace Theorem (again).

###### Proof.

Firstly, we place the necklace on the interval $[0,1]$, such that the $k$-th
stone corresponds to the interval $[\frac{k-1}{n},\frac{k}{n})$, as pictured
below.

Now we define the family of functions $f_{i}$ such that
$f_{i}:[0,1]\rightarrow[0,1]$,

$f_{i}(x)=\left\\{\begin{array}[]{ll}1&\text{ if }k\text{-th stone of the
necklace is of }i\text{-th kind}\\\ 0&\text{ otherwise.}\end{array}\right.$

With this knowledge, we now can define a family of measures $\mu_{i}$
describing the fraction of stones of the $i$-th kind that is on any part A of
the necklace:

$\mu_{i}(A)=\frac{n}{t_{i}}\cdot\int_{A}f_{i}(x)\cdot dx$

where $t_{i}$ represents the total number of stones of type $i$. To see why
this formula makes sense, evaluate the integral $\int_{A}f_{i}(x)\cdot dx$ to
get $1|_{A}$. Remember that we placed each stone $k$ within the interval
$[\frac{k-1}{n},\frac{k}{n})$, which has length $\frac{1}{n}$. Therefore,
$1|_{A}$ evaluates to $\frac{1}{n}\cdot t_{i}$, the fraction of stones of type
$i$ that are within A. Therefore, we must multiply the entire integral by
$\frac{n}{t_{i}}$ so that it integrates to unity, which is the measure of the
complete interval $[0,1]$. We now apply the Hobby-Rice Theorem, in the case
where $\epsilon_{j}=(-1)^{j}$ so that
$\sum_{j=0}^{d}(-1)^{j}\cdot\mu_{i}(I_{j})=0$. Similar to the above proof, we
can assign the positive intervals to the first thief, and the negative
intervals to the second thief. While this division is fair, some stones may be
split in two between thieves, which violates the spirit of the problem. To
solve this, realize that if a cut splits a stone in two, then there must exist
another cut subdividing a stone of type $i$ to balance the measure. In this
case, we can move both cuts away from the stones without altering the balance.
∎

##  6 Kneser’s Conjecture and the Lovasz-Kneser Theorem

After the application of the Borsuk-Ulam Theorem in the necklace problem we
proceed to the field of combinatorics. In this section, the Borsuk-Ulam
Theorem will only serve as inspiration, and the proof will be primarily from
the fields of combinatorics and graph theory. Therefore, we need some basic
combinatorial background before starting the proof.

Consider a set $[n]$ with $n$ elements, and another number $k$ such that
$n\geq 2k-1$. Denote the set $[n]\choose k$ as the subset of $[n]$’s power set
where every element in $[n]\choose k$ is a subset of $[n]$ with exactly $k$
elements. Here we have a mapping $f:{[n]\choose k}\rightarrow M$, where $M$ is
a set of distinct $i$ colors ($M$: {$m_{1}$,…,$m_{i}$}). The mapping $f$
satisfies this condition:

> For any $K_{1},K_{2}\in{[n]\choose k}$, if $K_{1}\bigcap K_{2}=\varnothing$,
> then $f(K_{1})\neq f(K_{2})$

Of course, there are more than one mapping like this f coloring $k$-element
subsets of $[n]$ with the principle above. One of the possible ways for such
coloring is to color each $k$-element subset with a distinct color, and this
way of coloring needs $n\choose k$ (number of $k$-element subsets in $[n]$)
different colors. However, the Lovasz-Kneser Theorem is not interested in
having as many colors as possible: it focuses on the minimum number of
distinct colors we need in order to color $k$-element subsets of $[n]$
satisfying the condition. Later, we will refer to any coloring of sets in
$[n]\choose k$ satisfying the condition as a ’proper coloring’.

######  Kneser Conjecture.

The minimum number of color needed for a proper coloring of elements in
$[n]\choose k$ is $n-2k+2$.

To interpret this theorem we introduce some background from graph theory.
Consider a graph in which each element in $[n]\choose k$ is a vertex. For any
two dots in the graph representing two elements $K_{1}$ $K_{2}$ in $[n]\choose
k$, if the two subsets don’t share any element of $[n]$, then there is an edge
connecting the two dots representing $K_{1}$ $K_{2}$. Here, a proper coloring
refers to a pattern of coloring each dot in the graph such that, any two
vertices connected in the graph are colored by two distinct colors.

For a set X and its set system $\mathcal{F}$, the graph $G$ that represents
each element of $\mathcal{F}$ (each subset of X in $\mathcal{F}$) as a vertex
is called the Kneser Graph of $\mathcal{F}$. The chromatic number of this
graph, denoted by $\chi(G)$, is the minimum number of $k$ where $k$ distinct
colors are able to color the graph $G$ properly (two vertices connected by an
edge are colored by two different colors). The Kneser graph of set system
$[n]\choose k$ representing each element in $[n]\choose k$ as a vertex is
denoted as $KG_{n,k}$. Thus, the theorem claims that, the chromatic number of
$KG_{n,k}$, $\chi(KG_{n,k})$, is equal to $n-2k+2$.

For example, when we have a set $[5]$ with five elements and the set system
consists of all subsets of $[5]$ with only two elements, the Kneser Graph
looks like this, where every dot represents a subset of $[5]$ with exactly two
elements.

Credit: Matoušek

######  The Lovasz-Kneser Theorem (reformulated Kneser Conjecture).

For natural number $k$ and $n\geq 2k-1$, $\chi(KG_{n,k})$, the chromatic
number of $KG_{n,k}$ is equal to $n-2k+2$.

###### Proof.

To prove this theorem we need to show that $\chi(KG_{n,k})$ is both smaller or
equal to $n-2k+2$ and greater or equal to $n-2k+2$. Then we can conclude
$\chi(KG_{n,k})$ must be equal to $n-2k+2$.

Firstly we show $\chi(KG_{n,k})$ is smaller or equal to $n-2k+2$. Here we view
the set $[n]$ identically to the set $\\{1,...,n\\}$ where every element in
$[n]$ is assigned to a number. Consider the $n-2k+2$ distinct color set
{$m_{1}$,…,$m_{n-2k+2}$}, for each vertex in the Kneser Graph $KG_{n,k}$,
color it with the $i^{th}$ color in {$m_{1}$,…,$m_{n-2k+2}$}, where $i$ =
$\text{min}\\{\text{min}(F),n-2k+2\\}$. Here $min(F)$ denotes the smallest
number among each number assigned to elements in set $F$. Now, each vertex in
$KG_{n,k}$ is assigned to a color in {$m_{1}$,…,$m_{n-2k+2}$}. We need to
verify that this coloring pattern is a proper coloring, which means, if two
vertices in $KG_{n,k}$ are colored in the same color then they must share some
elements in $[n]$.

Here, if two vertices are colored by the same color labelled as number $j$,
and $j\textless n-2k+2$, this means the $k$-element subsets of $[n]$
represented by the two vertices share the same element of $[n]$ such that the
shared element is labelled as $j\in\\{1,...,n\\}$. If two vertices are color
by the same color that is labelled as number $n-2k+2$, then each of the
vertices represents a $k$-element subset of elements of $[n]$ labelled as
numbers in {$n-2k+2$,…,$n$}. Notice that, the subset of elements of $[n]$
labelled as numbers in {$n-2k+2$,…,n} only has $2k-1$ distinct elements. Then
for the two $k$-element subsets, they must be sharing at least one element of
$[n]$ labelled as numbers in {$n-2k+2$,…,n}.

For this coloring pattern, any two vertices colored in the same color
represents two $k$-elements subsets that are not disjoint. Thus, $n-2k+2$ is
sufficient for a proper coloring of $KG_{n,k}$. By definition of
$\chi(KG_{n,k})$, it must be smaller or equal to $n-2k+2$.

The first half of the proof focuses exclusively on set theory, and the
application of the Borsuk-Ulam Theorem will show up in the second half of the
proof where we confirm $\chi(KG_{n,k})\geq n-2k+2$.

To show that $\chi(KG_{n,k})\geq n-2k+2$, we can use an alternative approach
by showing that for any $i\leq n-2k+2$, $i$ distinct colors are insufficient
for a proper coloring of the Kneser graph $KG_{n,k}$. More directly, we only
need to show that $n-2k+1$ distinct colors can’t form a proper coloring for
$KG_{n,k}$ (If $n-2k+1$ distinct colors can only form a coloring pattern where
some pairs of vertices joined by an edge is colored with the same color, then
a color set with less distinct colors can only have even more joint pairs
colored by the same color.).

Consider the color set {$m_{1}$,…,$m_{d}$}, where $d=n-2k+1$. We proceed to
arguing by contradiction through assuming there is a proper coloring of
$KG_{n,k}$ by $n-2k+1$ distinct colors. Take $X\subset S^{d}$ where $X$ is a
$n$-point subset of $S^{d}$. One additional requirement for $X$ is that, for
any hyperplane in $R^{d+1}$ passing through the origin, it can’t contain more
than d points of set $X$. This is a requirement based on the general position
principle (For $R^{d+1}$, a set is in general position implies that each
hyperplane can have at most $d$ points from the set, here the requirement
changes $d$ to $d-1$). It is easy to assign each element in set $[n]$ to a
point in $X$ and such assignment is a one-to-one correspondence. Thus, we no
longer the vertex set of $KG_{n,k}$ as $[n]\choose k$, instead we regard it as
$X\choose k$ where every vertex represents a subset of $X$ with $k$ points on
$S^{d}$. (Every point of $X$ corresponds to an element in $[n]$.

Now, we define subsets $A_{1},...,A_{d}\subseteq S^{d}$ by this way: for $x\in
S^{d}$, if the open hemisphere centered at $x$ contains a $k$-element subset
of $X$ such that, the vertex in $KG_{n,k}$ representing this subset is colored
as the $i$-th color in the color set {$m_{1}$,…,$m_{d}$}. In addition to
$A_{1},...,A_{d}\subseteq S^{d}$, we define $A_{d+1}$ as $S^{d}\backslash
A_{1}\bigcup...\bigcup A_{d}$. It is evident that $A_{1},...,A_{d+1}$ forms a
cover of $S^{d}$. By the Lyusternik–Shnirel’man theorem derived from the
Borsuk-Ulam theorem, given a cover of $A_{1},...,A_{d+1}$ of $S^{d}$, there
exists a set $A_{l}$ among the sets forming the cover such that $A_{l}$
contains a pair of antipodal points. Denote the pair of antipodal points as
$y$, $-y$.

Consider ${l}\in\\{$1$,...,$d$\\}$, then the open hemisphere centered at $y$
contains a $k$-element subset of $X$ such that the vertex in $KG_{n,k}$
representing this subset is colored in color $l$, and the open hemisphere
centered at $-y$ contains another $k$-element subset such that the the vertex
in $KG_{n,k}$ representing this subset is colored in the way. Notice that the
two $k$-element subsets are in different open hemispheres, so they must be
disjoint. Therefore such coloring must have violated the principle of proper
coloring, and ${l}$ must not be in {$1$,…,$d$}.

The only possibility left is ${l}\in\\{$d+1$\\}$, which implies $A_{d+1}$
contains a pair of antipodal points $y$,$-y$. By the way we define
$A_{1}$,…,$A_{d}$,the open hemisphere $H(y)$ centered at $y$ can’t contain any
$k$-element subset of $X$ (If it does then the vertex representing this subset
will be colored with a color and $y$ will no longer be in $A_{d+1}$). Thus the
open hemisphere centered at $y$ can have at most $k-1$ points from $X$, same
for the open hemisphere $H(-y)$ centered at $-y$. Given set $X$ on $S^{d}$ has
$n$ elements, there must be at least $n-(2k-2)$ points on
$S^{d}\backslash(H(y)\bigcup H(-y))$. Notice that $S^{d}\backslash(H(y)\bigcup
H(-y))$ is an equator of $S^{d}$ which lies on a hyperplane passing through
the origin. By our setup, no hyperplane passing through the origin can’t
contain more than d points of $X$. However, here the hyperplane which
$S^{d}\backslash(H(y)\bigcup H(-y))$ lies on contains all points of $X$ on the
equator, and there are $n-2k+2=d+1$ points on the equator (Recall $d=n-2k+1$).
Thus, ${l}$ must not be equal to $d+1$ too.

Here, $x$ is in the $A_{red}$ point set.

By our assumption that there is a proper coloring of $KG_{n,k}$ by $n-2k+1$
distinct colors, there is no set containing a pair of antipodal points among
$A_{1},...,A_{d+1}$ which form a cover of $S^{d}$. This contradicts the
Borsuk-Ulam Theorem which is already accepted as true. Therefore the
assumption must be false and $n-2k+1$ distinct colors are insufficient for a
proper coloring of $KG_{n,k}$. So, at least $n-2k+2$ is needed for a proper
coloring of $KG_{n,k}$. So we proved$\chi(KG_{n,k})\geq n-2k+2$.

Given $\chi(KG_{n,k})\geq n-2k+2$ and $\chi(KG_{n,k})\leq n-2k+2$, we proved
that $\chi(KG_{n,k})=n-2k+2$, the Lovasz-Kneser Theorem is proved. ∎

##  7 Dol’nikov’s Theorem

Dol’nikov’s theorem is a generalization of the Lovász-Kneser theorem. The
difference is that instead of giving an exact number for $\chi(KG_{n,k})$,
Dol’nikov’s theorem provides a lower bound for $\chi(KG(\mathcal{F}))$ where
$\mathcal{F}$ is an arbitrary (finite) set system. However, to properly define
this lower bound, we must first define hypergraph and what it means for a
hypergraph to be $m$-colorable.

######  Definition.

Given any set $X$ and $\mathcal{F}\subseteq 2^{X}$ a system of subsets of $X$,
we call $\mathcal{F}$ a set of hyperedges and the pair $(X,\mathcal{F})$ a
hypergraph generated by $X$ and $\mathcal{F}$.

######  Definition.

The hypergraph is $m$-colorable if there exists a coloring $c:X\rightarrow[m]$
such that no hyperedge is monochromatic under $c$, i.e. $|c(F)|>1$ for all
$F\in\mathcal{F}$.

Notice that here we have identified the set of $m$ colors with the set of
integers $[m]=1,2,...,m$. Also, one should be careful to distinguish this
coloring from the proper coloring of a Kneser Graph.

Now, given a hypergraph $(X,\mathcal{F})$, we define the $m$-colorability
defect as follows:

$cd_{m}(\mathcal{F})=\text{min}\\{|Y|:Y\subseteq X\text{ and }(X\backslash
Y,\\{F\in\mathcal{F}:F\cap Y=\varnothing\\})\text{ is m-colorable}\\}$

where $|Y|$ denotes the number of elements in $Y$.

(Note that we can view the same collection of points as being either a Kneser
graph, with the grouping of certain points being nodes of the Kneser graph, or
as a hypergraph, with the nodes of the Kneser graph being hyperedges on the
hypergraph, grouping together nodes).

In particular, we are concerned with $cd_{2}(\mathcal{F})$, which can be
interpreted as the minimum number of points of $X$ being colored white such
that when the rest of the points in $X$ are colored red or blue, no
$F\in\mathcal{F}$ is completely red or completely blue. Based on these
definitions, Dol’nikov’s theorem can be formally stated as follows:

######  Dol’nikov’s Theorem.

For any hypergraph $(X,\mathcal{F})$, we have

$\chi(KG(\mathcal{F}))\geq cd_{2}(\mathcal{F})$

.

Next, we supply 2 proofs of the theorem, both involving Borsuk-Ulam in some
way.

###### Proof.

This section is strikingly similar to the latter half of the proof of the
Lovász-Kneser theorem. Let $d=\chi(KG(\mathcal{F}))$. We then identify the
points of $X$ with a set of points in general position on $S^{d}$ and
$\mathcal{F}$ with the same set system based on the point set on $S^{d}$. We
construct the sets $A_{1},...,A_{d}$ by the following process: $\forall x\in
S^{d}$, assign $x\in A_{i}$ if the open hemisphere $H(x)$ contains a set
$F\in\mathcal{F}$ colored by color $i$. In other words, $A_{i}=\\{x\in
S^{d}:H(x)\text{ contains an }F\in\mathcal{F}\text{ of color }i\\}$.
Furthermore, we define $A_{d+1}=S^{d}\backslash\\{A_{1}\cup...\cup A_{d}\\}$.

Notice that $S^{d}=A_{1}\cup A_{2}\cup...\cup A_{d+1}$. Then by the
Lyusternik-Shnirel’man theorem, we have $x,-x\in A_{i}$ for some $A_{i}$.

Suppose $i<d+1$, then since $x\in A_{i}$, $H(x)$ contains some
$F\in\mathcal{F}$ with color $i$ and $H(-x)$ also contains some
$F^{\prime}\in\mathcal{F}$ with the same color. Since $H(x)$ and $H(-x)$ are
disjoint, $F\subset H(x)$ and $F^{\prime}\subset H(-x)$ must also be disjoint
(implying they are connected in the Kneser Graph). Now we have an edge between
two nodes with the same color $i$, meaning the coloring of the Kneser Graph is
not proper. However, we assumed proper coloring by letting
$d=\chi(KG(\mathcal{F}))$. Contradiction.

Hence $i=d+1$. In this case, by definition of $A_{d+1}$, neither $H(x)$ nor
$H(-x)$ can contain any $F\in\mathcal{F}$, i.e. any $F\in\mathcal{F}$ either
completely consists of points from both hemispheres or it contains points on
the equator. If we color $Y$=the points of $X$ that are on the equator (which
is at most $d$ points by the general position assumption) white, those in
$H(x)$ red, and those in $H(-x)$ blue, then any $F\in\mathcal{F}$ will have at
least 2 colors. Equivalently speaking, $\\{F\in\mathcal{F}:F\cap
Y=\varnothing\\}$ will be exactly those $F\in\mathcal{F}$ consisting of points
from both hemispheres, which means the hypergraph $(X\backslash
Y,\\{F\in\mathcal{F}:F\cap Y=\varnothing\\})$ has proper 2 coloring.

So we have $cd_{2}(\mathcal{F})\leq d$. ∎

The proof above is not Dol’nikov’s original proof, but it still invokes the
Borsuk-Ulam by its application of Lyusternik-Shnirel’man. Dol’nikov’s original
proof uses another version of Borsuk-Ulam theorem, as we shall see in the
upcoming proposition that is used in the original proof.

######  Proposition.

Let $C_{1},C_{2},...,C_{d}$ be systems of nonempty compact convex sets in
$\mathbb{R}$ (every $C_{i}$ is a family of compact convex sets) such that evey
$C_{i}$ is intersecting, i.e. for any $A,B\in C_{i}$, $A\cap
B\neq\varnothing$. Then there is a hyperplane intersecting all sets of the set
system $\bigcup\limits_{i=1}^{d}C_{i}$.

###### Proof of Proposition.

For a unit vector $v\in S^{d-1}$ starting at the origin, let $\ell_{v}$ denote
the line passing the origin and oriented in the direction of $v$. For each
$C_{i}$, consider the projections of the sets of $C_{i}$ onto $\ell_{v}$ and
denote the intersection of these projections $I_{i}(v)=\bigcap\limits_{C\in
C_{i}}\text{proj}_{\ell_{v}}(C)$. Such intersection must not be empty because
we can apply Helly’s theorem given that the projected intervals are 1
dimensional and any 2 intervals intersect. Furthermore, denote the midpoint of
$I_{i}(v)$ by $m_{i}(v)$, which is a vector parallel to $\ell_{v}$ and $v$.

Credit: Matoušek

The goal is to find some $v$ such that all the midpoints coincide. We will
prove that such a vector exists by defining some functions and applying the
Borsuk-Ulam theorem.

Define a continuous antipodal map $f:S^{d-1}\rightarrow\mathbb{R}^{d}$ by
setting each component $f_{i}(v)=\langle m_{i}(v),v\rangle$. We see that $f$
is antipodal by noticing that $\ell_{v}=\ell_{(-v)}$. Then we have
$\text{proj}_{\ell_{v}}(C)=\text{proj}_{\ell_{(-v)}}(C)$ for any $C\in C_{i}$
and $I_{i}(-v)=I_{i}(v)$. Consequently, $m_{i}(v)=m_{i}(-v)$ and we have
$\langle m_{i}(v),v\rangle=-\langle m_{i}(v),-v\rangle=-\langle
m_{i}(-v),-v\rangle$.

We then define another continuous antipodal map
$g:S^{d-1}\rightarrow\mathbb{R}^{d-1}$ by setting $g_{i}=f_{i}-f_{d}$ for
$i=1,2,...,d-1$. The map is antipodal because
$g_{i}(v)=f_{i}(v)-f_{d}(v)=-f_{i}(-v)+f_{d}(-v)=-(f_{i}(-v)-f_{d}(-v))=-g_{i}(-v)$.
By Borsuk-Ulam, there exists $v\in S^{d-1}$ such that $g(v)=0\Rightarrow
f_{i}(v)-f_{d}(v)=0$ for $i=1,2,...,d$.

By construction of $f$, we now have $\langle m_{i}(v),v\rangle=\langle
m_{d}(v),v\rangle$ for all $i=1,2,...,d$ for some $v$. Then $0=\langle
m_{i}(v),v\rangle-\langle m_{d}(v),v\rangle=\langle
m_{i}(v)-m_{d}(v),v\rangle$, where $m_{i}(v)-m_{d}(v)$ is parallel to $v$.
Hence it must be the case that $m_{i}(v)-m_{d}(v)=0$. Therefore we have
$m_{i}(v)=m_{d}(v)$ for all $i=1,2,...,d$.

Since all the midpoints coincide, we can consider the hyperplane perpendicular
to $\ell_{v}$ at that point, which will intersect all the sets in
$\bigcup\limits_{i=1}^{d}C_{i}$. ∎

Given the above proposition, we can finally proceed to the second proof of
Dol’nikov’s theorem.

###### Another Proof of Dol’nikov’s Theorem.

Let there be a proper $d$-coloring of $KG(\mathcal{F})$. Notice that if we
have $d=\chi(KG(\mathcal{F}))$ then we have a proper $d$-coloring of the
Kneser Graph (hence it is permissible to assume $d=\chi(KG(\mathcal{F}))$).
Then $\mathcal{F}$ can be partitioned into $d$ set systems by color, i.e.
$\mathcal{F}_{1},\mathcal{F}_{2},...,\mathcal{F}_{d}$ where
$\mathcal{F}_{i}=\\{F\in\mathcal{F}:c(F)=i\\}$ where $c$ is the coloring map
on $KG(\mathcal{F})$. Then any 2 sets from $\mathcal{F}_{i}$ must intersect
because they share a color and the coloring is proper.

An illustration of the convex sets of the Kneser graph $4\choose 2$ in
$\mathds{R}^{2}$.

Next, we place the points of $X$ into $\mathbb{R}^{d}$ such that they are in
general position, meaning no more than $d$ points can lie on the same
hyperplane. Furthermore, define

$C_{i}=\\{\text{conv}(F):F\in\mathcal{F}_{i}\\}$

for $i=1,2,...,d$. Then $C_{1},C_{2},...,C_{d}$ are systems of compact convex
sets, and by the previous proposition we obtain a hyperplane $h$ intersecting
all sets of $\bigcup\limits_{i=1}^{d}C_{i}=\\{F\in\mathcal{F}\\}$.

We notice that since $h$ intersects every conv$(F)$, every $F$ must either
completely consist of points from both of the open hemispheres divided by $h$,
or it must contain a point lying on $h$ (otherwise, if $F$ consists of points
from only one of the hemispheres and doesn’t contain any point on $h$ then
conv$(F)$ will not be intersected by $h$). Therefore if we color the points of
$X$ on $h$ white, the points in one of the hemispheres red, and the points in
the other hemisphere blue, then we have a proper 2 coloring of the hypergraph
$(X\backslash Y,\\{F\in\mathcal{F}:F\cap Y=\varnothing\\})$ where $Y$ is the
set of points of $X$ intersecting $h$ (i.e. the set of white points). There
can be at most $d$ white points by the general position assumption. Hence
$cd_{2}(\mathcal{F})\leq d$. ∎

##  8 Conclusion

As we can see, there exist some broad ”recipe” as to how to apply the Borsuk-
Ulam theorem to problems in discrete mathematics. Generally, one takes a
discrete point set in general position, define some kind of clever set-
covering on it, then use this cover to apply some version of Borsuk-Ulam or
its derivatives (i.e, the ham sandwich theorem). The field of topological
methods in combinatorics has proved rich in new ideas, and further research is
needed to see how it can be applied to solve intractable problems in
combinatorics and graph theory.

##  9 References

Matoušek, Jiří. Using the Borsuk–Ulam Theorem: Lectures on Topological Methods
in Combinatorics and Geometry. Springer-Verlag, 2003.


# HyperionSolarNet
Solar Panel Detection from Aerial Images

Poonam Parhar, Ryan Sawasaki, Nathan Nusaputra, Felipe Vergara,
Alberto Todeschini, Hossein Vahabi
University of California, Berkeley
{poonamparhar,rsawasaki,nusaputra137,felipe.vergara,
<EMAIL_ADDRESS>
###### Abstract

With the effects of global climate change impacting the world, collective
efforts are needed to reduce greenhouse gas emissions. The energy sector is
the single largest contributor to climate change and many efforts are focused
on reducing dependence on carbon-emitting power plants and moving to renewable
energy sources, such as solar power. A comprehensive database of the location
of solar panels is important to assist analysts and policymakers in defining
strategies for further expansion of solar energy. In this paper we focus on
creating a world map of solar panels. We identify locations and total surface
area of solar panels within a given geographic area. We use deep learning
methods for automated detection of solar panel locations and their surface
area using aerial imagery. The framework, which consists of a two-branch model
using an image classifier in tandem with a semantic segmentation model, is
trained on our created dataset of satellite images. Our work provides an
efficient and scalable method for detecting solar panels, achieving an
accuracy of 0.96 for classification and an IoU score of 0.82 for segmentation
performance.

##  1 Introduction

As awareness of the impacts and risks of climate change continue to increase,
efforts are being made to reduce greenhouse gas emissions. Within the energy
industry, strategies are being deployed to lower carbon emissions by reducing
fossil fuel energy sources and integrating renewable energy. Although solar
panel production continues to increase, the integration of renewable energy is
losing momentum and carbon emission reduction goals are falling short due to
wavering and unsupportive policy frameworks [1]. Many previous works have
focused on solar energy forecasting based on weather condition data [2] and
solar panel data aggregated from state agencies [3]. However, simply
predicting the solar energy is not sufficient for policy making and
determining expansion strategies. In this paper, we design and evaluate an
end-to-end framework for creating a world map of solar panels. Our framework
identifies locations and total surface area of solar panels within a given
geographic area. This information can help solar companies and analysts
identify key market areas to target for further expansion and assist
policymakers and environmental agencies in making informed decisions to meet
renewable energy objectives.

Many recent works have developed methods for solar panel detection [4, 5, 6,
7, 8]. One such study that produced notable advances in this area was
DeepSolar, which was trained on over $350,000$ images resulting in a precision
and recall for solar panel detection of $90\%$ and a mean relative error of
$2.1\%$ for size estimation of solar panels [4]. While Deep Solar’s
contributions advanced this area of study, their methods require substantial
amounts of imagery data and computational power that are only accessible to
ventures with the necessary resources. In addition, the vast amounts of images
could not be labeled using a supervised, ground-truth approach. Our work takes
an alternative approach to previous studies, which results in increased
performance while requiring considerably less supervised data and
computational resources.

Many studies in this field deploy a two branch model using a classification
model to identify the solar panel images, which are then passed to a
computationally-heavy segmentation model for mask prediction. Our work, as
shown in Figure A.1, builds on these foundational studies and introduces a
number of enhancements with the following contributions:

  * •

Implementation of an EfficientNet-B7 classifier in combination with a semantic
segmentation model based on U-Net architecture utilizing EfficientNet-B7
encoder-backbone to predict the location and size of PV panels.

  * •

We use a very small dataset consisting of 1,963 satellite images, achieving an
average accuracy of 0.96 and an IoU score of 0.82 for our classification and
segmentation models, respectively.

  * •

We demonstrate that our models can be applied in various new locations to
generate more labelled data for classification and segmentation training to
further improve the models performance.

  * •

We provide a user-interface that identifies the location and total area of
solar panels within a geographical region in quasi-real-time. Additional
information on our web application is provided in Appendix D.

##  2 Methods

###  2.1 Data

Given the lack of available datasets, we built our own dataset of satellite
images downloaded using Google Maps Static API. To help train robust models,
images are selected with diverse features and collected from across the U.S.
Batches of images are pulled from Arizona, California, Colorado, Florida,
Hawaii, Idaho, Louisiana, Massachusetts, Nevada, New Jersey, New York, Oregon,
Texas and Washington. The images are at zoom levels $20$ and $21$, and of
sizes $416$x$416$ and $600$x$600$ pixels. In addition, the dataset contains a
mix of both residential and commercial buildings. Early trained models
revealed a number of false positives with images of objects that resemble
solar panels. In subsequent image downloads, we collected no_solar images
containing objects that could potentially be misclassified as solar panels,
such as skylights, crosswalks, and sides of tall buildings, as shown in Figure
B.1.

For classification, images are grouped into solar and no_solar categories. As
shown in Table 2, both classes split the data 80$\%$ training and 20$\%$
validation. For semantic segmentation, we used LabelBox [9], a platform to
manually annotate solar panels in images and generate segmentation masks as
shown in Figure B.2. Table 2 shows the total number of labeled images included
in the segmentation dataset, which is equal to the number of images in the
solar data in the classification dataset.

In addition to our training and validation set, we also conducted an
experiment on the city of Berkeley, CA, and created a test set. The Berkeley
test set consists of random sampling of 10$\%$ of the image tiles from the 8
council districts within the entire city. This set consists of 2,243 images
with a distribution of 1,922 no_solar and 321 solar class images. We use this
test set for evaluating our individual models and the complete pipeline.

Table 1: Classification dataset | solar | no_solar | Total
---|---|---|---
Training | 668 | 1295 | 1963
Validation | 168 | 324 | 492
Berkeley Test Set | 321 | 1922 | 2243

Table 2: Semantic segmentation dataset  | Total
---|---
Training | 668
Validation | 168
Berkeley Test Set | 321

###  2.2 Models

#### Solar panels detection using image classification

In this work, we employ Transfer Learning and fine-tune an EfficientNet-B7 to
classify satellite image tiles into solar and no_solar classes.
EfficientNet-B7 achieves the state-of-the-art 84.4$\%$ top-1 and 97.1$\%$
top-5 accuracy on ImageNet with 66M parameters and 37B FLOPS. We fine-tune
EfficientNet-B7 on a training set consisting of 668 image tiles containing
solar panels, and 1295 image tiles without any solar panels. The performance
of the fine-tuned model is evaluated against a validation dataset consisting
of 168 image tiles containing solar panels, and 324 image tiles without any
solar panels.

In order to train EfficientNet-B7 for solar panels image classification, we
replace its top layer with a Global Average Pooling layer and a fully
connected prediction layer having a single output node. Besides training these
two layers, we fine-tune the trainable variables in all of the layers of
EfficientNet-B7. The classification model training plots are shown in Figure
B.4

To increase variation and diversity of input images for model training, we
augment the images by applying random horizontal flip, translation, rotation,
contrast and cropping on them. Refer to Figure B.5 for example augmented
images. We measure the performance of solar panel image classification using
accuracy, precision and recall metrics. The performance results on the
validation set are shown in Table 4. The classification model achieves a mean
accuracy of 0.98 with a mean precision and recall of 0.98 and 0.95
respectively.

Table 3: Classification model performance Accuracy | Precision | Recall | F1 Score
---|---|---|---
0.98 | 0.95 | 0.98 | 0.97

Table 4: Segmentation model performance IoU Score | F1 Score
---|---
0.86 | 0.92

#### Solar panels size estimation using semantic segmentation

For semantic image segmentation, we use EfficientNet-B7 as the encoder-
backbone to train a U-Net model for segmenting solar panels in satellite
images. Refer to B.7 for an example of the U-Net architecture trained for
segmenting images having solar panels. We annotated 836 images containing
solar panels using the LabelBox platform [9], and produced their corresponding
segmentation masks. We resize all images to a size of 512x512 pixels for
training and testing. The semantic segmentation model training plots are
presented in Figure B.8, and a few examples of the predicted masks are shown
in Figure B.9. Refer to Appendix B for the experimental setup and
hyperparameters used for model training. The performance results on the
validation dataset are shown in Table 4. Our segmentation model reports an IoU
score of 0.86 indicating an average overlap of 86.0$\%$ between the prediction
and the ground truth masks, and a mean F1 Score of 0.92 representing the ratio
of the overlap and the combined area of the predicted and the label masks.

#### Procedure for estimating total surface area and number of solar panels

The determination of the solar panel surface area is accomplished by
programming a function that accepts the output from the segmentation model and
returns the total area of solar panels within a given image, as shown in
Figure B.10. The segmentation model produces a predicted mask for each image
denoting the pixels that are classified as belonging to a solar panel. The
predicted mask is then resized to the size of the original image. This pixel
matrix is fed into the function along with the latitude and zoom of the image,
which are used to derive the size representation of each individual pixel. The
length per pixel is calculated using the Mercator Projection, which accounts
for the differences in length per pixel depending on the zoom and distance
from the equator via:

$\text{meters per
pixels}=\frac{156543.03392\ast\cos{\text{(latitude}\ast\frac{\pi}{180}\text{)}}}{2^{\text{zoom}}}$
(1)

The total area of solar panels is calculated by multiplying the count of ones
in the matrix by the area per pixel value. In turn, the number of solar panels
is calculated by dividing the total solar panel area by 17.6 ft2, which is the
area of a standard PV panel.

##  3 Results

We evaluated the classification model, segmentation model and the complete
pipeline on the test set created consisting of a random sampling of the images
from our Berkeley experiment.

#### Classification model evaluation

The HyperionSolarNet classification model reports a mean accuracy of 0.96 on
the Berkeley test set. Table 6 shows the precision, recall and F1 Scores for
both the solar and no_solar classes. With 1922 no_solar images in the test
set, the model reports a mean precision of 0.98, and a mean recall of 0.97,
achieving an average F1 Score of 0.98. In comparison, with 321 solar class
images, the classification model achieves a mean precision and recall of 0.82
and 0.91 respectively, and an F1 Score of 0.86. A considerably lower precision
for the solar class images indicates that the model makes notable number of
false positive predictions.

Table 5: Berkeley test set classification Class | Precision | Recall | F1 Score | Support
---|---|---|---|---
no_solar | 0.98 | 0.97 | 0.98 | 1922
solar | 0.82 | 0.91 | 0.86 | 321

Table 6: Berkeley test set segmentation IoU | F1 Score
---|---
0.82 | 0.89

Figure C.1 in the appendix presents the confusion matrix we obtain by running
the segmentation model against the Berkeley test set. To gain a better
understanding of where the model is underperforming, we reviewed all the
misclassified images. We present a few examples in Figure C.2, where the title
of the images indicate their true label, but our model misclassified. There
are cases where the model still predicts false positives due to objects such
as skylights. Many of the false negatives are due to the model having
difficulty detecting PV panels located along the edge of images. As
HyperionSolarNet is utilized for various new regions, the misclassified images
can be correctly labeled and utilized as training data to improve the model
further.

#### Segmentation model evaluation

In the Berkeley test set, we had 321 solar-panel images. We manually annotated
those images using the LabelBox platform [9], and created mask labels for
them. We evaluated the HyperionSolarNet segmentation model against these test
set images and the model reported an IoU score of 0.82. The performance
results are presented in Table 6.

In order to understand the model performance better, we examined the
predictions that had the IoU score less than 0.4. A few examples are shown in
Figure C.3. We note that in these images, the solar panels are not very clear
and distinguishable, and it is difficult even for human eyes to identify these
solar panels.

#### Complete pipeline evaluation

Using our complete model pipeline, we computed the percentage error in the
prediction of size and number of solar panels for the Berkeley test set. Our
architecture pipeline makes a percentage error of 0.7$\%$, as shown in Table 7
in Appendix C. In addition, using all the image tiles of the entire Berkeley
city, we estimated that there are around 61,480 solar panels in Berkeley city.
Detailed results are included in Appendix C.

##  4 Conclusion

While this work provides tools to fight climate change, there are potential
negative impacts that should be considered. One primary concern is the
unintended use of this tool for surveillance and investigating compliance of
solar energy mandates, which would disparately impact low-income communities.
In addition, while solar panel expansion is beneficial in the fight against
climate change, the negative environmental impacts are yet to be realized.
Over the next few decades, solar panels will reach the end of their life span
resulting in toxic waste that will need proper disposal.

There is a heightened urgency to solve the climate change crisis by expanding
solar energy. Our work provides solutions to this challenge by leveraging deep
learning methods and implementing a two-branch model using an EfficientNet-B7
classifier in tandem with a U-Net and EfficientNet-B7 encoder-backbone
semantic segmentation model. The use of this two-branch model to predict solar
panel locations and surface area results in improved performance while using a
relatively smaller training dataset.

## Acknowledgments and Disclosure of Funding

We thank Colorado Reed, Professor Paolo D’Odorico, and UC Berkeley for their
support and valuable advice on this work.

## References

  * [1] IEA (2020), Tracking Energy Integration 2020, IEA, Paris https://www.iea.org/reports/tracking-energy-integration-2020
  * [2] Mathe, J., Miolane, N., Sebastien, N., & Lequeux, J. (2019). PVNet: A LRCN architecture for spatio-temporal photovoltaic PowerForecasting from numerical weather prediction. arXiv preprint arXiv:1902.01453.
  * [3] Barbose, G., Darghouth, N., Elmallah, S., Forrester, S., Kristina SH, K., Millstein, D., & O’Shaughnessy, E. (2019). Tracking the Sun: Pricing and Design Trends for Distributed Photovoltaic Systems in the United States-2019 Edition.
  * [4] Yu, J., Wang, Z., Majumdar, A., & Rajagopal, R. (2018). DeepSolar: A machine learning framework to efficiently construct a solar deployment database in the United States. Joule, 2(12), 2605-2617.
  * [5] Camilo, J., Wang, R., Collins, L. M., Bradbury, K., & Malof, J. M. (2018). Application of a semantic segmentation convolutional neural network for accurate automatic detection and mapping of solar photovoltaic arrays in aerial imagery. arXiv preprint arXiv:1801.04018.
  * [6] Zhuang, L., Zhang, Z., & Wang, L. (2020). The automatic segmentation of residential solar panels based on satellite images: A cross learning driven U-Net method. Applied Soft Computing, 92, 106283.
  * [7] Wani, M. A., & Mujtaba, T. (2021). Segmentation of Satellite Images of Solar Panels Using Fast Deep Learning Model. International Journal of Renewable Energy Research (IJRER), 11(1), 31-45.
  * [8] Golovko, V., Kroshchanka, A., Mikhno, E., Komar, M., & Sachenko, A. (2021). Deep convolutional neural network for detection of solar panels. In Data-Centric Business and Applications (pp. 371-389). Springer, Cham.
  * [9] Sharma, M., Rasmuson, D., Rieger, B., & Kjelkerud, D. (2019). Labelbox: The best way to create and manage training data. software, LabelBox. Inc, https://www. labelbox. com.
  * [10] Tan, M., & Le, Q. (2019, May). Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference on Machine Learning (pp. 6105-6114). PMLR.
  * [11] Ronneberger, O., Fischer, P., & Brox, T. (2015, October). U-net: Convolutional networks for biomedical image segmentation. In International Conference on Medical image computing and computer-assisted intervention (pp. 234-241). Springer, Cham.

##  Appendix A Appendix

###  A.1 Background

With the recent advances in deep learning methods, deep learning models are
being extensively used in various computer vision tasks such as image
classification, object detection, and image segmentation. The fast
developments in these tasks have been further accelerated by Transfer
Learning. Using Transfer Learning in a classification and segmentation model
pipeline, this work presents a supervised deep learning method to estimate the
number and surface area of PV panels from high resolution satellite images.

Figure A.1: Architecture diagram of the solar panel area prediction pipeline.
Satellite images are passed through an image classification model to identify
images containing solar panels. The positive predictions from the image
classification model are then run through an image segmentation model to
identify the pixels belonging to solar panels in an image.

###  A.2 Image classification

Image classification is the task of classifying images into the groups they
belong to. For our case, we define two categories: images containing solar
panels and images without any solar panels in them. There are several pre-
trained models available for image classification, including but not limited
to MobileNet, VGG-16, Inception-v3, RetNet and EfficientNet [10]. As shown in
Figure A.2, there are trade-offs between accuracy and number of model
parameters that are to be considered in model selection. We use transfer
learning techniques to fine-tune pre-trained classification models for our
specific classification task.

Figure A.2: Accuracy scores of various pre-trained image classification models
[10].

###  A.3 Semantic image segmentation

Image segmentation is a challenging computer vision task where the goal is to
classify each pixel of a given image to the specific class or object it
belongs to. Semantic segmentation is a specific type of image segmentation
where all the pixels representing a particular class are classified as a
single entity.

U-Net [11] is one of the most popular deep learning based semantic
segmentation methods. It is a convolutional neural network architecture having
Encoder and Decoder layers that down-sample and up-sample the given images to
extract features and classify pixels to specific classes. The Encoder or the
contraction path is a set of convolutional and max-pooling layers that extract
feature maps from the image and reduce its size as it passes through the
encoder layers. On the other hand, the Decoder or the expansive path employs
transposed convolutional layers along with feature maps from the corresponding
encoder layers to restore the resolution and pixel localization information of
the image. The layers of the Encoder can be arranged using any of the image
classification neural networks, which is called the encoder-backbone of the
U-Net architecture. The encoder-backbone also defines how the Decoder layers
are built to up-sample the images.

###  A.4 Performance metrics

The performance of our two branch model is evaluated on a validation dataset
of 168 solar and 324 no_solar images. In addition, we examine model
performance on an experiment conducted on the entire city of Berkeley. For the
classification model, we use the performance metrics of accuracy, precision,
recall, and F1 Score. For the semantic segmentation model, we use the
performance metrics of intersection over union (IoU) and F1 Score. The IoU
metric is the overlap of the predicted mask and the ground-truth labeled mask
divided by their union.

Figure A.3: Intersection over Union (IoU) is the area of intersection of the
actual object label and the predicted mask divided by their union.

##  Appendix B Appendix

Figure B.1: Examples of no_solar images with objects that resemble solar
panels: skylight, crosswalk, side of tall building. Figure B.2: Examples of
solar-panel annotations of images in LabelBox. Figure B.3: Image
classification into solar and no_solar classes. Figure B.4: HyperionSolarNet
classification model training plots. Figure B.5: Examples of augmentation on
input training images Figure B.6: Confusion matrix for the validation dataset
with the HyperionSolarNet classification model. Figure B.7: An example of
U-Net architecture trained for segmenting images having solar-panels. An image
having solar panels is passed through the network, and it produces a
segmentation mask for the pixels belonging to solar panels in the image.
Figure B.8: HyperionSolarNet semantic segmentation model training plots

Satellite Image Label Prediction

Figure B.9: Examples of segmentation mask predictions from HyperionSolarNet,
along with the original images and labels.

###  B.1 Augmentation with Albumentations

In order to bring variation in our training data images and to increase the
dataset size, we augment the images and their segmentation masks. The
augmentations include random cropping, flipping, changing brightness and blur,
scaling, and grid and optical distortion of images. We use the Albumentations
library [https://github.com/albumentations-team/albumentations] to perform the
augmentations, which enabled us to apply the same augmentation to an image and
its corresponding segmentation mask.

###  B.2 Segmentation models library

For training our semantic segmentation model, we use segmentation_models
library. It offers a high level API for training segmentation models, while
making 4 different model architectures and 25 backbones available for each
architecture. Furthermore, it provides implementation of several segmentation
losses (e.g. Jaccard, Dice, Focal) and metrics (e.g. IoU, F1-score), which are
very helpful for segmentation model training. The library code is available
here: https://github.com/qubvel/segmentation_models.

Figure B.10: Procedure for calculating the area of solar panel in an image.

###  B.3 Experimental setup and hyperparameters

We trained both of our models on a Google-Colab machine having Tesla
V100-SXM2-16GB GPU, and on an AWS g4dn.12xlarge instance having 4 NVIDIA T4
GPUs.

For training and fine-tuning our classification model, we use a starting
learning rate of 1e-05 and reduce it by a factor of 0.1 as the validation
accuracy reaches a plateau and does not improve for 10 epochs. The base model
EfficientNet-b7 has 813 neural network layers. Using a batch size of 8 images,
we fine-tune the trainable variables in all of the layers of EfficientNet-b7
for 150 epochs. We use RMSprop as the optimizer and Binary Cross-Entropy as
the loss function for our training procedure.

For training the semantic segmentation model, we achieved the best performance
using a learning rate of 1e-04 and the Adam optimizer. We reduce the learning
rate by a factor of 0.1 as the validation IoU score reaches a plateau. We
perform the model training for 150 epochs. For our training loss function, we
use the Binary Cross-Entropy and the Jaccard loss.

##  Appendix C Appendix

Figure C.1: Confusion Matrix for the Berkeley test set with the
HyperionSolarNet classification model.

Figure C.2: Examples of images misclassified by HyperionSolarNet. The title
above the image denotes the actual class, but our model classified as the
opposite.

Figure C.3: Examples of segmentation predictions with an IoU score < 0.4 from
the Berkeley test set

###  C.1 Percentage error in the prediction of size and number of solar panels
for the Berkeley test set

Using the label masks of the annotated images in the test set, we calculate
the total area and number of solar panels, which we treat as the actual size
and number of panels in those images for the purpose of calculating the
percentage error in the predictions. Additionally, we estimate/predict the
area and number of panels by passing the test set images through our complete
classification and segmentation pipeline. Finally, we compare the actual area
and the number of panels against the predictions of our pipeline to determine
the percent error in prediction for the test set using the following equation.

$\text{Percent Error}=\frac{\text{| Actual - Predicted |}}{\text{Actual}}\cdot
100$ (2)

Our architecture pipeline makes an error of 0.7$\%$ in predicting the number
and size of solar panels in the Berkeley test set, as shown in Table 7

Table 7: Actual and predicted area and number of solar panels for the Berkeley test set | Area (sq. ft.) | Number of Solar Panels
---|---|---
Actual | 101,765.48 | 5,787
Predicted | 102,609.72 | 5,828

###  C.2 Estimated solar panels in Berkeley

We estimated the size and number of solar panels using all the 22,436 image
tiles covering the entire Berkeley city. In Table 8, we share the results.

Table 8: Estimated total area and number of solar panels in Berkeley Area (sq. ft.) | Number of Solar Panels
---|---
1,082,431.98 | 61,480

##  Appendix D Appendix

###  D.1 Web application

We built a web-application that provides users an interactive tool to
visualize the output from the classification and segmentation models. The
interface allows users to outline a desired geographical area on Google Maps.
With the click of a button, HyperionSolarNet splits the region into smaller
600x600 pixel tiles, identifies the latitude and longitude coordinates of each
tile containing solar panels, and estimates the total surface area of solar
panels. In cases where the desired location is a city boundary or larger, we
use a GeoJSON file with the boundary coordinates to preprocess all of the
solar panel tiles, locations and surface area within the region.

Figure D.1: Web application

Our application architecture is built on AWS, using EC2 to host our website
and S3 to save all static content including models, masked images and GeoJSON
files. The website is hosted on a g4dn.xlarge EC2 with T4 GPU and 16 Gb of
memory, which is cost effective for inference. The web application is built
using Flask, Nginx as a reverse proxy, and Gunicorn as the application server
configured to use 3 workers. To achieve inference completely independent from
the Flask application, we configure TensorFlow Serving, which provides a
server to expose model inference through an API. For our web application on
inference, Flask is used as a proxy that connects by calling an API via post
to send data to the TensorFlow Serving API which delivers prediction results.
As input for inference, we require images for classification and segmentation.
The client sends latitude and longitude, height, width and zoom of the map
section. Using this information, we use the Google Map API to generate equal
size image tiles to use as input for inference, which are converted to numpy
arrays. The application returns the classification information for each tile
and the segmentation masks overlaid on the image tiles.

Figure D.2: Diagram of HyperionSolarNet system architecture.

The application has a few limitations mainly due to memory and costs for GPU
instances. Due to memory restrictions our minimum zoom capacity for online
processing is 19. To reduce the memory usage, we have tested model
optimization using TensorRT with the same restrictions. Future enhancements
include improving inference performance by testing new optimizations with
TensorRT and TensorLight and simplifying the model without sacrificing
performance.