A. Bishnoi
info
Please Note
<p>This page displays the records of the person named above and is not linked to a unique person identifier. This record may need to be merged to a profile.</p>
16 records found
1
For a family of graphs $\mathcal{H}$, the maximum size of a collection of graphs $\mathcal{F}$ for which the symmetric difference $\oplus$ of two distinct graphs $G_1, G_2$ has the property $G_1 \oplus G_2 \not\in \mathcal{H}$ (or $\in \mathcal{H}$) is denoted by $D_{\mathcal{H}}(n)$ (or $M_{\mathcal{H}}(n)$ respectively).
We also denote the independence ratio by $d_{\mathcal{H}}(n) = D_{\mathcal{H}}(n) / 2^{\binom{n}{2}}$.
This thesis gives a new approach to get an upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain cycles of length $2k$, i.e. $\mathcal{H} = \{H : C_{2k} \subseteq H\}.$
The proof of which is based on a different proof by Noga Alon concerning the upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain stars with $2k$ edges, i.e. $\mathcal{H} = \{H : K_{1,2k} \subseteq H\}.$
A bound on the number of $C_{2k}$-free graphs proven by Morris and Saxton indirectly already solved this problem, but Alon's approach could be expanded upon for different types of graph families for which the upper bound is not yet known.
In this thesis we also perform a spectral analysis of the Cayley graph corresponding to the families $\mathcal{H} = \{H : L \subseteq H\}$ and $\mathcal{H} = \{H : L \cong H\}$, in order to give upper bounds on $D_{\mathcal{H}}(n)$.
These upper bounds are compared to known lower bounds.
...
We also denote the independence ratio by $d_{\mathcal{H}}(n) = D_{\mathcal{H}}(n) / 2^{\binom{n}{2}}$.
This thesis gives a new approach to get an upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain cycles of length $2k$, i.e. $\mathcal{H} = \{H : C_{2k} \subseteq H\}.$
The proof of which is based on a different proof by Noga Alon concerning the upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain stars with $2k$ edges, i.e. $\mathcal{H} = \{H : K_{1,2k} \subseteq H\}.$
A bound on the number of $C_{2k}$-free graphs proven by Morris and Saxton indirectly already solved this problem, but Alon's approach could be expanded upon for different types of graph families for which the upper bound is not yet known.
In this thesis we also perform a spectral analysis of the Cayley graph corresponding to the families $\mathcal{H} = \{H : L \subseteq H\}$ and $\mathcal{H} = \{H : L \cong H\}$, in order to give upper bounds on $D_{\mathcal{H}}(n)$.
These upper bounds are compared to known lower bounds.
...
For a family of graphs $\mathcal{H}$, the maximum size of a collection of graphs $\mathcal{F}$ for which the symmetric difference $\oplus$ of two distinct graphs $G_1, G_2$ has the property $G_1 \oplus G_2 \not\in \mathcal{H}$ (or $\in \mathcal{H}$) is denoted by $D_{\mathcal{H}}(n)$ (or $M_{\mathcal{H}}(n)$ respectively).
We also denote the independence ratio by $d_{\mathcal{H}}(n) = D_{\mathcal{H}}(n) / 2^{\binom{n}{2}}$.
This thesis gives a new approach to get an upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain cycles of length $2k$, i.e. $\mathcal{H} = \{H : C_{2k} \subseteq H\}.$
The proof of which is based on a different proof by Noga Alon concerning the upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain stars with $2k$ edges, i.e. $\mathcal{H} = \{H : K_{1,2k} \subseteq H\}.$
A bound on the number of $C_{2k}$-free graphs proven by Morris and Saxton indirectly already solved this problem, but Alon's approach could be expanded upon for different types of graph families for which the upper bound is not yet known.
In this thesis we also perform a spectral analysis of the Cayley graph corresponding to the families $\mathcal{H} = \{H : L \subseteq H\}$ and $\mathcal{H} = \{H : L \cong H\}$, in order to give upper bounds on $D_{\mathcal{H}}(n)$.
These upper bounds are compared to known lower bounds.
We also denote the independence ratio by $d_{\mathcal{H}}(n) = D_{\mathcal{H}}(n) / 2^{\binom{n}{2}}$.
This thesis gives a new approach to get an upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain cycles of length $2k$, i.e. $\mathcal{H} = \{H : C_{2k} \subseteq H\}.$
The proof of which is based on a different proof by Noga Alon concerning the upper bound of $d_{\mathcal{H}}(n)$ where $\mathcal{H}$ is the family of graphs that contain stars with $2k$ edges, i.e. $\mathcal{H} = \{H : K_{1,2k} \subseteq H\}.$
A bound on the number of $C_{2k}$-free graphs proven by Morris and Saxton indirectly already solved this problem, but Alon's approach could be expanded upon for different types of graph families for which the upper bound is not yet known.
In this thesis we also perform a spectral analysis of the Cayley graph corresponding to the families $\mathcal{H} = \{H : L \subseteq H\}$ and $\mathcal{H} = \{H : L \cong H\}$, in order to give upper bounds on $D_{\mathcal{H}}(n)$.
These upper bounds are compared to known lower bounds.
This thesis is about the following hat guessing game first described by Winkler. Consider a group of n players situated at the vertices of a graph G. An adversary gives each player a hat coloured one of q possible colours. The players are unable to see the colour of their own hat, but each player can see the hat colour of their neighbours in G. The players are asked to simultaneously make a guess on the colour of their own hat, according to a predetermined guessing strategy based solely on the hat colours each player can see. The players win if at least one of them correctly guesses their hat colour, otherwise the adversary wins. Is it possible for the players to devise a strategy which guarantees they win regardless of how the adversary places the hats? Clearly, if the players have a winning strategy on the graph G for q colours, then the same strategy must also be winning for any number of colours less than q. This motivates us to define the hat guessing number HG(G) of G, a parameter first introduced by Farnik.
Definition: Let HG(G) be the maximum q such that the players have a winning strategy when playing the hat guessing game on the graph G with q colours.
Bosek et al. showed an upper bound on the hat guessing number using a partition into independent sets. We show that the same bound holds when V1, ..., Vl partition the vertices into sets that induce directed acyclic graphs. This implies that for any arc a of the complete graph Kn we have that HG(Kn-a) = n-1, whereas HG(Kn) = n. Furthermore, we give a family of graphs for which choosing a partition into the minimum number of independent sets may be arbitrarily worse than choosing a different partition into independent sets, when applying the bound.
Szczechla have shown the hat guessing number for cycles. They formulate strategies to show that HG(C4) ≥ 3 and HG(C3n) ≥ 3 in a complex coordinate system. We reformulate those same strategies and show that they are winning without using this coordinate system.
The winning strategy for C4 can be generalised to obtain the following result. For an odd prime power q, let M a maximum matching in the complete graph Kq+1. Then HG(Kq+1-M) = q.
On a more general and technical note, we define a notion of equivalence of strategies to try revealing some of the inherent symmetries of the problem. For example, reassigning individual strategies according to an automorphism of the graph does not change whether the collective strategy is winning. We also obtain a notion of uniqueness of a winning strategy, which we conjecture to be a strong, but rare, property. ...
Definition: Let HG(G) be the maximum q such that the players have a winning strategy when playing the hat guessing game on the graph G with q colours.
Bosek et al. showed an upper bound on the hat guessing number using a partition into independent sets. We show that the same bound holds when V1, ..., Vl partition the vertices into sets that induce directed acyclic graphs. This implies that for any arc a of the complete graph Kn we have that HG(Kn-a) = n-1, whereas HG(Kn) = n. Furthermore, we give a family of graphs for which choosing a partition into the minimum number of independent sets may be arbitrarily worse than choosing a different partition into independent sets, when applying the bound.
Szczechla have shown the hat guessing number for cycles. They formulate strategies to show that HG(C4) ≥ 3 and HG(C3n) ≥ 3 in a complex coordinate system. We reformulate those same strategies and show that they are winning without using this coordinate system.
The winning strategy for C4 can be generalised to obtain the following result. For an odd prime power q, let M a maximum matching in the complete graph Kq+1. Then HG(Kq+1-M) = q.
On a more general and technical note, we define a notion of equivalence of strategies to try revealing some of the inherent symmetries of the problem. For example, reassigning individual strategies according to an automorphism of the graph does not change whether the collective strategy is winning. We also obtain a notion of uniqueness of a winning strategy, which we conjecture to be a strong, but rare, property. ...
This thesis is about the following hat guessing game first described by Winkler. Consider a group of n players situated at the vertices of a graph G. An adversary gives each player a hat coloured one of q possible colours. The players are unable to see the colour of their own hat, but each player can see the hat colour of their neighbours in G. The players are asked to simultaneously make a guess on the colour of their own hat, according to a predetermined guessing strategy based solely on the hat colours each player can see. The players win if at least one of them correctly guesses their hat colour, otherwise the adversary wins. Is it possible for the players to devise a strategy which guarantees they win regardless of how the adversary places the hats? Clearly, if the players have a winning strategy on the graph G for q colours, then the same strategy must also be winning for any number of colours less than q. This motivates us to define the hat guessing number HG(G) of G, a parameter first introduced by Farnik.
Definition: Let HG(G) be the maximum q such that the players have a winning strategy when playing the hat guessing game on the graph G with q colours.
Bosek et al. showed an upper bound on the hat guessing number using a partition into independent sets. We show that the same bound holds when V1, ..., Vl partition the vertices into sets that induce directed acyclic graphs. This implies that for any arc a of the complete graph Kn we have that HG(Kn-a) = n-1, whereas HG(Kn) = n. Furthermore, we give a family of graphs for which choosing a partition into the minimum number of independent sets may be arbitrarily worse than choosing a different partition into independent sets, when applying the bound.
Szczechla have shown the hat guessing number for cycles. They formulate strategies to show that HG(C4) ≥ 3 and HG(C3n) ≥ 3 in a complex coordinate system. We reformulate those same strategies and show that they are winning without using this coordinate system.
The winning strategy for C4 can be generalised to obtain the following result. For an odd prime power q, let M a maximum matching in the complete graph Kq+1. Then HG(Kq+1-M) = q.
On a more general and technical note, we define a notion of equivalence of strategies to try revealing some of the inherent symmetries of the problem. For example, reassigning individual strategies according to an automorphism of the graph does not change whether the collective strategy is winning. We also obtain a notion of uniqueness of a winning strategy, which we conjecture to be a strong, but rare, property.
Definition: Let HG(G) be the maximum q such that the players have a winning strategy when playing the hat guessing game on the graph G with q colours.
Bosek et al. showed an upper bound on the hat guessing number using a partition into independent sets. We show that the same bound holds when V1, ..., Vl partition the vertices into sets that induce directed acyclic graphs. This implies that for any arc a of the complete graph Kn we have that HG(Kn-a) = n-1, whereas HG(Kn) = n. Furthermore, we give a family of graphs for which choosing a partition into the minimum number of independent sets may be arbitrarily worse than choosing a different partition into independent sets, when applying the bound.
Szczechla have shown the hat guessing number for cycles. They formulate strategies to show that HG(C4) ≥ 3 and HG(C3n) ≥ 3 in a complex coordinate system. We reformulate those same strategies and show that they are winning without using this coordinate system.
The winning strategy for C4 can be generalised to obtain the following result. For an odd prime power q, let M a maximum matching in the complete graph Kq+1. Then HG(Kq+1-M) = q.
On a more general and technical note, we define a notion of equivalence of strategies to try revealing some of the inherent symmetries of the problem. For example, reassigning individual strategies according to an automorphism of the graph does not change whether the collective strategy is winning. We also obtain a notion of uniqueness of a winning strategy, which we conjecture to be a strong, but rare, property.
An Entropy-Based Approach to the Union-Closed Sets Conjecture
Understanding the chaos of entropy in combinatorics
The Union-Closed Sets Conjecture (UCSC), posed by Peter Frankl in 1979, asserts that every finite union-closed family of sets contains an element that appears in at least half of its member sets. Despite this seemingly simple formulation, the conjecture has remained unresolved for decades. Recently in November 2022 Gilmer developed a novel approach based on the information theoretic concept: \emph{entropy}, which has offered fresh insights and promising partial results. In this thesis, we provide a self-contained introduction to entropy and explore its utility in combinatorics, specifically its application to the UCSC. We thoroughly examine the groundbreaking entropy-based proof that establishes a constant lower bound of \(\frac{3 - \sqrt{5}}{2}\approx0.382\). Additionally, we shortly discuss the small further improvements made to this bound. We then consider a related conjecture proposed by Nagel, which states: \textit{the \(k\)th most frequent element in a union-closed family appears in at least a fraction \(\frac{1}{2^{k-1} +1}\) of the sets.} We shall discuss how the new entropy approach could also be used there to improve the bounds on the sizes of the family.
All these explorations have been focused on understanding recent developments and to create a unified narrative. Due to time constraints, the thesis did not pursue new results. However, the comprehensive understanding gained has given some promising directions for future research. ...
All these explorations have been focused on understanding recent developments and to create a unified narrative. Due to time constraints, the thesis did not pursue new results. However, the comprehensive understanding gained has given some promising directions for future research. ...
The Union-Closed Sets Conjecture (UCSC), posed by Peter Frankl in 1979, asserts that every finite union-closed family of sets contains an element that appears in at least half of its member sets. Despite this seemingly simple formulation, the conjecture has remained unresolved for decades. Recently in November 2022 Gilmer developed a novel approach based on the information theoretic concept: \emph{entropy}, which has offered fresh insights and promising partial results. In this thesis, we provide a self-contained introduction to entropy and explore its utility in combinatorics, specifically its application to the UCSC. We thoroughly examine the groundbreaking entropy-based proof that establishes a constant lower bound of \(\frac{3 - \sqrt{5}}{2}\approx0.382\). Additionally, we shortly discuss the small further improvements made to this bound. We then consider a related conjecture proposed by Nagel, which states: \textit{the \(k\)th most frequent element in a union-closed family appears in at least a fraction \(\frac{1}{2^{k-1} +1}\) of the sets.} We shall discuss how the new entropy approach could also be used there to improve the bounds on the sizes of the family.
All these explorations have been focused on understanding recent developments and to create a unified narrative. Due to time constraints, the thesis did not pursue new results. However, the comprehensive understanding gained has given some promising directions for future research.
All these explorations have been focused on understanding recent developments and to create a unified narrative. Due to time constraints, the thesis did not pursue new results. However, the comprehensive understanding gained has given some promising directions for future research.
The Container Method
And its applications
In this thesis, we explore the method of hypergraph containers and its applications to problems in extremal combinatorics and discrete geometry. We start by introducing containers on triangle-free graphs and use it to give a lower bound on the number of triangle-free graphs on n vertices. We then generalise to the container algorithm for independent sets in graphs, which is a version of regular graphs. The proof of this theorem is an algorithm. We study this algorithm and apply it to the Erdős-Rényi random graph G(n,p). After this we expand to hypergraphs, specifically 3-uniform hypergraphs. Finally we look at the application to a problem in discrete geometry: Given n points in the Euclidean plane ℝ², with at most three on any line, how large a subset are we guaranteed to find in general position (i.e., with at most two on any line)? A strong upper bound is obtained by using the hypergraph container method.
...
In this thesis, we explore the method of hypergraph containers and its applications to problems in extremal combinatorics and discrete geometry. We start by introducing containers on triangle-free graphs and use it to give a lower bound on the number of triangle-free graphs on n vertices. We then generalise to the container algorithm for independent sets in graphs, which is a version of regular graphs. The proof of this theorem is an algorithm. We study this algorithm and apply it to the Erdős-Rényi random graph G(n,p). After this we expand to hypergraphs, specifically 3-uniform hypergraphs. Finally we look at the application to a problem in discrete geometry: Given n points in the Euclidean plane ℝ², with at most three on any line, how large a subset are we guaranteed to find in general position (i.e., with at most two on any line)? A strong upper bound is obtained by using the hypergraph container method.
Solving scheduling problems in practical environments, such as manufacturing facilities, can be a big challenge. Theoretical mathematical methods that aim to address these problems are oftentimes underutilized, both due to difficulties adapting them to the specific problem at hand, and limited mathematical expertise in an organization. The aim of this report is to address both of these issues by providing a step-by-step guide on the application of mathematical scheduling theory, including tools on dealing with difficult constraints. To showcase the effectiveness of this guide and its process, we provide a case study where the guide was applied to a manufacturer of generic medicine. Here we encountered many problems, such as non-standard constraints and large-sized data, but success- fully addressed each of them with a mathematical model capable of generating strong, practical solutions. While further improvements are definitely possible and encouraged, this research provides a strong proof of concept on how the gap between practice and theory can be addressed.
...
Solving scheduling problems in practical environments, such as manufacturing facilities, can be a big challenge. Theoretical mathematical methods that aim to address these problems are oftentimes underutilized, both due to difficulties adapting them to the specific problem at hand, and limited mathematical expertise in an organization. The aim of this report is to address both of these issues by providing a step-by-step guide on the application of mathematical scheduling theory, including tools on dealing with difficult constraints. To showcase the effectiveness of this guide and its process, we provide a case study where the guide was applied to a manufacturer of generic medicine. Here we encountered many problems, such as non-standard constraints and large-sized data, but success- fully addressed each of them with a mathematical model capable of generating strong, practical solutions. While further improvements are definitely possible and encouraged, this research provides a strong proof of concept on how the gap between practice and theory can be addressed.
In this text, we begin by giving a definition of Vector Space Ramsey Numbers. It concerns colourings of $t$-dimensional subspaces of some vector space $\mathbb{F}_q^n$. We want to ensure that each colouring contains a monochromatic $k$-dimensional subspace. After proving that these numbers always exist, we continue with studying asymptotic bounds for these numbers. We study a selection of methods, such as through coding theory or using the probabilistic method, to obtain lower and upper bounds for vector space Ramsey numbers. Lastly, we introduce two methods to directly compute vector space Ramsey numbers. That being through an ILP formulation and through a SAT formulation.
...
In this text, we begin by giving a definition of Vector Space Ramsey Numbers. It concerns colourings of $t$-dimensional subspaces of some vector space $\mathbb{F}_q^n$. We want to ensure that each colouring contains a monochromatic $k$-dimensional subspace. After proving that these numbers always exist, we continue with studying asymptotic bounds for these numbers. We study a selection of methods, such as through coding theory or using the probabilistic method, to obtain lower and upper bounds for vector space Ramsey numbers. Lastly, we introduce two methods to directly compute vector space Ramsey numbers. That being through an ILP formulation and through a SAT formulation.
Master thesis
(2024)
-
L.K.M. Verlinde, C.E. Groenland, A. Bishnoi, D.C. Gijswijt, J.M.A.M. van Neerven
Consider an arbitrary finite grid in some field. How many hyperplanes are required so that every point is contained in at least k hyperplanes, except for one point that is not allowed to be contained in any hyperplane? To solve this so-called hyperplane grid covering problem, the polynomial method has proven to be extremely useful in finding bounds on the minimum number of hyperplanes required. This has given rise to a second problem: the polynomial grid covering problem. This problem considers the minimum degree of a polynomial such that every grid point is a root with multiplicity k, except for one point where the polynomial does not vanish. We study these two related problems for multiple grids: the hypercube, the vector space over the binary field and grids in the Cartesian plane. Since polynomial covers in the latter have not been studied before, we provide algorithms and techniques to study these covers. We also explore the link between grid coverings and two results from algebraic geometry: the Footprint Bound and the Cayley-Bacharach Theorems.
...
Consider an arbitrary finite grid in some field. How many hyperplanes are required so that every point is contained in at least k hyperplanes, except for one point that is not allowed to be contained in any hyperplane? To solve this so-called hyperplane grid covering problem, the polynomial method has proven to be extremely useful in finding bounds on the minimum number of hyperplanes required. This has given rise to a second problem: the polynomial grid covering problem. This problem considers the minimum degree of a polynomial such that every grid point is a root with multiplicity k, except for one point where the polynomial does not vanish. We study these two related problems for multiple grids: the hypercube, the vector space over the binary field and grids in the Cartesian plane. Since polynomial covers in the latter have not been studied before, we provide algorithms and techniques to study these covers. We also explore the link between grid coverings and two results from algebraic geometry: the Footprint Bound and the Cayley-Bacharach Theorems.
The Impact of Charging Electric Vehicles Between Routing Instances
The Modeling of a Combined Electric Vehicle Routing and Charging Model
E-mobility, in particular electric vehicles (EVs), play a crucial role in the energy transition. While businesses are increasingly adopting EVs, there is still a lot of opportunity to grow. One aspect of this growth is the way these vehicles are used by companies, especially when it comes to the logistics of EV charging. To encourage companies to further reduce their carbon footprint by more efficiently utilizing EVs, this project proposes a combined vehicle routing and charging model. These models can be used separately, as well as together, allowing the charging model to be combined with any pre-existing routing engine. The goal of this project is to show the benefits of allowing EVs to be charged between shifts during the day, rather than exclusively overnight, as well as to show how such schedules can be made. Our results show that giving vehicles the opportunity to charge between shifts can significantly reduce the costs associated with fleet operations. If the fleet contains non-electric vehicles as well as electric ones, we also see a significant reduction in the number of kilometers driven using fossil fuels. When sufficient chargers were available, even when the vehicles had little time to charge, a feasible schedule could always be found. Moreover, when more realistic charging intervals were used, most vehicles were even able to fully recharge before the start of their next shift. Finally, we concluded that the set of chargers needed to find such a feasible schedule can be relatively small, meaning that even without extensive additions to the charging infrastructure, companies can still benefit from this policy change.
...
E-mobility, in particular electric vehicles (EVs), play a crucial role in the energy transition. While businesses are increasingly adopting EVs, there is still a lot of opportunity to grow. One aspect of this growth is the way these vehicles are used by companies, especially when it comes to the logistics of EV charging. To encourage companies to further reduce their carbon footprint by more efficiently utilizing EVs, this project proposes a combined vehicle routing and charging model. These models can be used separately, as well as together, allowing the charging model to be combined with any pre-existing routing engine. The goal of this project is to show the benefits of allowing EVs to be charged between shifts during the day, rather than exclusively overnight, as well as to show how such schedules can be made. Our results show that giving vehicles the opportunity to charge between shifts can significantly reduce the costs associated with fleet operations. If the fleet contains non-electric vehicles as well as electric ones, we also see a significant reduction in the number of kilometers driven using fossil fuels. When sufficient chargers were available, even when the vehicles had little time to charge, a feasible schedule could always be found. Moreover, when more realistic charging intervals were used, most vehicles were even able to fully recharge before the start of their next shift. Finally, we concluded that the set of chargers needed to find such a feasible schedule can be relatively small, meaning that even without extensive additions to the charging infrastructure, companies can still benefit from this policy change.
The k-truncated metric dimension of a graph is the minimum number of sensors (a subset of the vertex set) needed to uniquely identify every vertex in the graph based on its distance to the sensors, where the sensors have a measuring range of k. We give an algorithm with the goal that given any tree and any value for the measuring range of the sensors k, the algorithm finds the k-truncated metric dimension of that tree. The algorithm presented in this thesis is a modification of the algorithm given by Gutkovich and Song Yeoh [6]. The algorithm in this thesis improves on their algorithm in both validity and time complexity. We show that given any tree and any value k, the algorithm returns a k-resolving set for that tree. Moreover, we conjecture the difference in the k-truncated metric dimension of any tree and the size of the k-resolving set found by the algorithm for that tree is never greater than one. The time complexity of the algorithm is proven to be O(k3n), where k is the measuring range of the sensors and n is the number of vertices in the tree. This implies that the time complexity is linear in n for fixed k.
...
The k-truncated metric dimension of a graph is the minimum number of sensors (a subset of the vertex set) needed to uniquely identify every vertex in the graph based on its distance to the sensors, where the sensors have a measuring range of k. We give an algorithm with the goal that given any tree and any value for the measuring range of the sensors k, the algorithm finds the k-truncated metric dimension of that tree. The algorithm presented in this thesis is a modification of the algorithm given by Gutkovich and Song Yeoh [6]. The algorithm in this thesis improves on their algorithm in both validity and time complexity. We show that given any tree and any value k, the algorithm returns a k-resolving set for that tree. Moreover, we conjecture the difference in the k-truncated metric dimension of any tree and the size of the k-resolving set found by the algorithm for that tree is never greater than one. The time complexity of the algorithm is proven to be O(k3n), where k is the measuring range of the sensors and n is the number of vertices in the tree. This implies that the time complexity is linear in n for fixed k.
For this thesis, we consider two $k$-colorings of a graph $G$ adjacent if one can recolor one into the other by changing the color of one vertex. The reconfiguration graph of a graph $G$ on $k$ colors $\mathcal{C}_{k}(G)$ is the graph for which the vertices are the $k$-colorings of $G$, and an edge is between two $k$-colorings if they are adjacent. We further investigate the diameter of the reconfiguration graph on $k$ colors: $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$.
The general conjecture the thesis is based around says that $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ for every graph $G$ and $k \geq \Delta(G)+2$. This conjecture is confirmed for various families of graphs, for example the complete graph $K_n$ and complete bipartite $K_{n,m}$. This thesis will prove the lower bound of the conjecture for the family of complete $r$-partite graphs $G = K_{x_1,x_2,\ldots,x_r}$, utilising an approach from Cambie et al. for the proof. Furthermore we give an algorithm that computes the $k$-colorings of $G$, the reconfiguration graph $\mathcal{C}_{k}(G)$, and its diameter $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ and give a few results on this diameter for small graphs. ...
The general conjecture the thesis is based around says that $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ for every graph $G$ and $k \geq \Delta(G)+2$. This conjecture is confirmed for various families of graphs, for example the complete graph $K_n$ and complete bipartite $K_{n,m}$. This thesis will prove the lower bound of the conjecture for the family of complete $r$-partite graphs $G = K_{x_1,x_2,\ldots,x_r}$, utilising an approach from Cambie et al. for the proof. Furthermore we give an algorithm that computes the $k$-colorings of $G$, the reconfiguration graph $\mathcal{C}_{k}(G)$, and its diameter $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ and give a few results on this diameter for small graphs. ...
For this thesis, we consider two $k$-colorings of a graph $G$ adjacent if one can recolor one into the other by changing the color of one vertex. The reconfiguration graph of a graph $G$ on $k$ colors $\mathcal{C}_{k}(G)$ is the graph for which the vertices are the $k$-colorings of $G$, and an edge is between two $k$-colorings if they are adjacent. We further investigate the diameter of the reconfiguration graph on $k$ colors: $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$.
The general conjecture the thesis is based around says that $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ for every graph $G$ and $k \geq \Delta(G)+2$. This conjecture is confirmed for various families of graphs, for example the complete graph $K_n$ and complete bipartite $K_{n,m}$. This thesis will prove the lower bound of the conjecture for the family of complete $r$-partite graphs $G = K_{x_1,x_2,\ldots,x_r}$, utilising an approach from Cambie et al. for the proof. Furthermore we give an algorithm that computes the $k$-colorings of $G$, the reconfiguration graph $\mathcal{C}_{k}(G)$, and its diameter $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ and give a few results on this diameter for small graphs.
The general conjecture the thesis is based around says that $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ for every graph $G$ and $k \geq \Delta(G)+2$. This conjecture is confirmed for various families of graphs, for example the complete graph $K_n$ and complete bipartite $K_{n,m}$. This thesis will prove the lower bound of the conjecture for the family of complete $r$-partite graphs $G = K_{x_1,x_2,\ldots,x_r}$, utilising an approach from Cambie et al. for the proof. Furthermore we give an algorithm that computes the $k$-colorings of $G$, the reconfiguration graph $\mathcal{C}_{k}(G)$, and its diameter $\mathrm{diam}\left(\mathcal{C}_{k}(G)\right)$ and give a few results on this diameter for small graphs.
A Note on Integrity
ILP Modelling and Analysis on Graph Families
This thesis provides a fresh perspective on the (vertex) integrity of graphs, serving as a measure of network robustness. The study begins by introducing fundamental concepts and methods for evaluating the integrity of different graph families. An Integer Linear Programming (ILP) model, specifically designed for assessing integrity, is then presented. By applying this model, integrity values are calculated for various graph families, and patterns within the results are identified. These patterns contribute to establishing boundaries or determining exact values of integrity for the analyzed graph families. The analyzed graph families encompass Glued Paths, generalized Theta graphs, (Double) Cone graphs, Fan graph, Lollipop graphs, generalized Barbell graphs, (Dutch) Windmill graphs, Paley graphs, and Kneser graphs. Additionally, two conjectures are formulated: one concerning a lower bound for the integrity of all Paley graphs, and another addressing the exact integrity values of specific Kneser graphs. The ILP model proves to be a valuable tool for further exploration of graph family integrity, offering opportunities for additional research and expanding our understanding of network robustness.
...
This thesis provides a fresh perspective on the (vertex) integrity of graphs, serving as a measure of network robustness. The study begins by introducing fundamental concepts and methods for evaluating the integrity of different graph families. An Integer Linear Programming (ILP) model, specifically designed for assessing integrity, is then presented. By applying this model, integrity values are calculated for various graph families, and patterns within the results are identified. These patterns contribute to establishing boundaries or determining exact values of integrity for the analyzed graph families. The analyzed graph families encompass Glued Paths, generalized Theta graphs, (Double) Cone graphs, Fan graph, Lollipop graphs, generalized Barbell graphs, (Dutch) Windmill graphs, Paley graphs, and Kneser graphs. Additionally, two conjectures are formulated: one concerning a lower bound for the integrity of all Paley graphs, and another addressing the exact integrity values of specific Kneser graphs. The ILP model proves to be a valuable tool for further exploration of graph family integrity, offering opportunities for additional research and expanding our understanding of network robustness.
A set of lines passing through the origin in Euclidean space is called equiangular if the angle between any two lines is the same. The question of finding the maximum number of such lines, N(d) in any dimension d is an extensively studied problem. Closely related, is the problem of finding the maximum number of lines, N_α(d), such that the common angle between the lines is arccosα. In recent years, many progress has been made on this problem. We review some of these breakthrough results and the techniques they use to approach this problem. The first main result is a linear upper bound on N_α(d) which is found using a completely novel approach with respect to techniques used in previous works. Another main result that we discuss solves the problem of finding N_α(d) for high enough dimensions. Some classic results from some of the first studies on equiangular lines are also discussed. Finally, some suggestions are given for possible further research.
...
A set of lines passing through the origin in Euclidean space is called equiangular if the angle between any two lines is the same. The question of finding the maximum number of such lines, N(d) in any dimension d is an extensively studied problem. Closely related, is the problem of finding the maximum number of lines, N_α(d), such that the common angle between the lines is arccosα. In recent years, many progress has been made on this problem. We review some of these breakthrough results and the techniques they use to approach this problem. The first main result is a linear upper bound on N_α(d) which is found using a completely novel approach with respect to techniques used in previous works. Another main result that we discuss solves the problem of finding N_α(d) for high enough dimensions. Some classic results from some of the first studies on equiangular lines are also discussed. Finally, some suggestions are given for possible further research.
A code C is defined to be a set of S words, where a word is a sequence of n entries. We call S the size and n the length of the code. The entries of the code can have k different values, {0, .., (k − 1)}. Define a perfect k-hash code (PHC) as a code with the property that any collection of v words in the code is different at at least one index. PHC’s are useful mathematical objects within different fields of theoretical computer science and coding theory. This thesis will focus on one typical kind of PHC, a trifferent code. Such a trifferent code is defined as a PHC where k = v = 3. This means that any collection of three words in the code has to differ at some index. We now define T (n) to be the largest possible size of a trifferent code given that it has length n. The question that arises is, what is the value of T (n)? It turns out that determining the exact value is complicated, unless n is really small. Therefore, we try to understand the asymptotic nature of the function T (n). This is what we call the trifference problem. This paper will cover and prove the best known asymptotic upper and lower bound on T (n). Moreover, it will explain and include a Python code that can be used to show and prove all values of T (n) for n ∈ {1, .., 6}. Lastly, two different ways to explicitly construct trifferent codes for any value of n will be given and compared.
...
A code C is defined to be a set of S words, where a word is a sequence of n entries. We call S the size and n the length of the code. The entries of the code can have k different values, {0, .., (k − 1)}. Define a perfect k-hash code (PHC) as a code with the property that any collection of v words in the code is different at at least one index. PHC’s are useful mathematical objects within different fields of theoretical computer science and coding theory. This thesis will focus on one typical kind of PHC, a trifferent code. Such a trifferent code is defined as a PHC where k = v = 3. This means that any collection of three words in the code has to differ at some index. We now define T (n) to be the largest possible size of a trifferent code given that it has length n. The question that arises is, what is the value of T (n)? It turns out that determining the exact value is complicated, unless n is really small. Therefore, we try to understand the asymptotic nature of the function T (n). This is what we call the trifference problem. This paper will cover and prove the best known asymptotic upper and lower bound on T (n). Moreover, it will explain and include a Python code that can be used to show and prove all values of T (n) for n ∈ {1, .., 6}. Lastly, two different ways to explicitly construct trifferent codes for any value of n will be given and compared.
Controlling the behaviour of eigenvalues
The interlacing method
This thesis uses the method of interlacing polynomials to study the behaviour of eigenvalues of a matrix after a rank-one update. Specifically, interlacing polynomials, common interlacing and interlacing families are exhaustively studied. These are excellent tools to find bounds on the eigenvalues of updated matrices by keeping track of how they move.
This enables us to prove results in different mathematical fields. We investigate three of them. The first one is from spectral graph theory: we prove the existence of a sharp κ-approximation for any graph.
The second result is from linear algebra. It states that if a matrix has a high stable rank, it must contain a large column submatrix with large least singular value.
Lastly, the proof of the Kadison-Singer Problem is discussed. Despite being a problem from analysis, it was solved with the interlacing method, which is originally a method from discrete mathematics.
This thesis shows how these three seemingly different problems are all connected by the same method, highlighting its advantages. The objective is to present a clear framework of the different facets of the interlacing method and provide an insight in the situations where one can expect the said method to be useful.
...
This enables us to prove results in different mathematical fields. We investigate three of them. The first one is from spectral graph theory: we prove the existence of a sharp κ-approximation for any graph.
The second result is from linear algebra. It states that if a matrix has a high stable rank, it must contain a large column submatrix with large least singular value.
Lastly, the proof of the Kadison-Singer Problem is discussed. Despite being a problem from analysis, it was solved with the interlacing method, which is originally a method from discrete mathematics.
This thesis shows how these three seemingly different problems are all connected by the same method, highlighting its advantages. The objective is to present a clear framework of the different facets of the interlacing method and provide an insight in the situations where one can expect the said method to be useful.
...
This thesis uses the method of interlacing polynomials to study the behaviour of eigenvalues of a matrix after a rank-one update. Specifically, interlacing polynomials, common interlacing and interlacing families are exhaustively studied. These are excellent tools to find bounds on the eigenvalues of updated matrices by keeping track of how they move.
This enables us to prove results in different mathematical fields. We investigate three of them. The first one is from spectral graph theory: we prove the existence of a sharp κ-approximation for any graph.
The second result is from linear algebra. It states that if a matrix has a high stable rank, it must contain a large column submatrix with large least singular value.
Lastly, the proof of the Kadison-Singer Problem is discussed. Despite being a problem from analysis, it was solved with the interlacing method, which is originally a method from discrete mathematics.
This thesis shows how these three seemingly different problems are all connected by the same method, highlighting its advantages. The objective is to present a clear framework of the different facets of the interlacing method and provide an insight in the situations where one can expect the said method to be useful.
This enables us to prove results in different mathematical fields. We investigate three of them. The first one is from spectral graph theory: we prove the existence of a sharp κ-approximation for any graph.
The second result is from linear algebra. It states that if a matrix has a high stable rank, it must contain a large column submatrix with large least singular value.
Lastly, the proof of the Kadison-Singer Problem is discussed. Despite being a problem from analysis, it was solved with the interlacing method, which is originally a method from discrete mathematics.
This thesis shows how these three seemingly different problems are all connected by the same method, highlighting its advantages. The objective is to present a clear framework of the different facets of the interlacing method and provide an insight in the situations where one can expect the said method to be useful.
We consider the game cops and robbers, which is a pursuit-evasion game played on a graph G. The cops and the robber take turns moving across the vertices of G, where the goal for the cops is to eventually catch the robber. Specifically, we study the cop number of G, i.e. the minimum number of cops that is needed to catch the robber on G. We investigate the relation between the cop number of the Erdős-Rényi (ER) random graph G(n, p_n) and compare it to another graph parameter, the domination number. Our goal is to collect results from previous research and create an overview. Throughout this thesis, we provide some examples of graphs for which the cop number is equal to the domination number. Furthermore, we provide proofs for some results on the domination number of the ER random graph. The main takeaway is that the cop number is asymptotic to the domination number for particular values of p_n.
...
We consider the game cops and robbers, which is a pursuit-evasion game played on a graph G. The cops and the robber take turns moving across the vertices of G, where the goal for the cops is to eventually catch the robber. Specifically, we study the cop number of G, i.e. the minimum number of cops that is needed to catch the robber on G. We investigate the relation between the cop number of the Erdős-Rényi (ER) random graph G(n, p_n) and compare it to another graph parameter, the domination number. Our goal is to collect results from previous research and create an overview. Throughout this thesis, we provide some examples of graphs for which the cop number is equal to the domination number. Furthermore, we provide proofs for some results on the domination number of the ER random graph. The main takeaway is that the cop number is asymptotic to the domination number for particular values of p_n.