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.

We investigate two open problems in discrete geometry regarding how large subsets of sets of points need to be in order for certain structures to emerge. First of all there is the Erdős-Szekeres convex polygon problem, also known as the Happy Ending problem. Interestingly, there is a clear distinction between the number of points required to ensure a lot of points in convex position in the plane and in higher dimensions. This raises the question whether such a difference depending on the considered dimension can also be found in other problems concerning subsets of point sets. The second problem where we research this difference is the Big-Line-Big-Clique Conjecture. As far as we know, this conjecture has not been studied yet in other dimensions than the plane. Apart from discussing the relevant literature for both problems, we present a formulation of the Big-Line-Big-Clique Conjecture in higher dimensions and a generalisation in terms of (hyper)graphs. We also state a stronger version of the conjecture that would imply the BLBC Conjecture to be true. However, we show a counterexample to the stronger conjecture, leaving the original one open.

The role of Unmanned Aerial Vehicles (UAVs), more commonly known as drones, in society continues to become more significant every day, both in everyday life and in military operations. The extent to which unmanned vehicles are used for both offensive as well as reconnaissance missions is at an all-time high. To expand the number of operational systems while managing costs, it is desirable to deploy systems that can operate fully independently. For a survey mission, this requires a planning of the complete mission before the drone leaves for enemy territory. The setting of such a mission can be stated as follows: starting from a secure base, multiple surveillance locations need to be safely reached and the acquired information has to be transmitted back to the base. There are many possible strategies for gathering this information. This report investigates how to find the strategy that maximises the expected amount of retrieved information. Specifically, such an optimal strategy tells us which route the UAV should take in enemy territory and at what moments in the mission transmissions should be made. We present a mathematical framework for formulating the problem, as well as a genetic algorithm capable of finding the optimal strategy in different scenarios.

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.