E. Lorist
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>
8 records found
1
The neighbour-sum problem on graphs
For which graphs does there exist a non-trivial solution?
The neighbour-sum problem asks whether a graph admits a non-trivial assignment of real numbers to its vertices such that the value at each vertex equals the sum of the values assigned to its neighbours. This problem can be reformulated as the eigenvalue equation Ax=x, where A is the adjacency matrix of the graph, reducing the question to determining whether 1 is an eigenvalue of A.
This thesis investigates the neighbour-sum problem for several classes of graphs using techniques from spectral graph theory, linear algebra, and Fourier analysis on finite groups. Complete characterizations are obtained for path graphs and cycle graphs through explicit formulas for their spectra. These results are extended to Cayley graphs over finite abelian groups, yielding explicit eigenvalue conditions for circulant graphs in terms of group characters. For trees, theoretical results are derived for several special families, including stars, double stars, and caterpillar trees, and an asymptotic result shows that the proportion of solvable trees tends to one as the number of vertices increases.
In addition, computational experiments were performed on all non-isomorphic trees with up to twenty vertices and on connected circulant graphs of small order. The experiments reveal how structural properties such as the number of leaves, maximum degree, diameter, and generating set influence solvability, and suggest that larger trees are increasingly likely to admit non-trivial solutions. Together, the theoretical and computational results provide insight into the relationship between graph structure and the existence of neighbour-sum assignments. ...
This thesis investigates the neighbour-sum problem for several classes of graphs using techniques from spectral graph theory, linear algebra, and Fourier analysis on finite groups. Complete characterizations are obtained for path graphs and cycle graphs through explicit formulas for their spectra. These results are extended to Cayley graphs over finite abelian groups, yielding explicit eigenvalue conditions for circulant graphs in terms of group characters. For trees, theoretical results are derived for several special families, including stars, double stars, and caterpillar trees, and an asymptotic result shows that the proportion of solvable trees tends to one as the number of vertices increases.
In addition, computational experiments were performed on all non-isomorphic trees with up to twenty vertices and on connected circulant graphs of small order. The experiments reveal how structural properties such as the number of leaves, maximum degree, diameter, and generating set influence solvability, and suggest that larger trees are increasingly likely to admit non-trivial solutions. Together, the theoretical and computational results provide insight into the relationship between graph structure and the existence of neighbour-sum assignments. ...
The neighbour-sum problem asks whether a graph admits a non-trivial assignment of real numbers to its vertices such that the value at each vertex equals the sum of the values assigned to its neighbours. This problem can be reformulated as the eigenvalue equation Ax=x, where A is the adjacency matrix of the graph, reducing the question to determining whether 1 is an eigenvalue of A.
This thesis investigates the neighbour-sum problem for several classes of graphs using techniques from spectral graph theory, linear algebra, and Fourier analysis on finite groups. Complete characterizations are obtained for path graphs and cycle graphs through explicit formulas for their spectra. These results are extended to Cayley graphs over finite abelian groups, yielding explicit eigenvalue conditions for circulant graphs in terms of group characters. For trees, theoretical results are derived for several special families, including stars, double stars, and caterpillar trees, and an asymptotic result shows that the proportion of solvable trees tends to one as the number of vertices increases.
In addition, computational experiments were performed on all non-isomorphic trees with up to twenty vertices and on connected circulant graphs of small order. The experiments reveal how structural properties such as the number of leaves, maximum degree, diameter, and generating set influence solvability, and suggest that larger trees are increasingly likely to admit non-trivial solutions. Together, the theoretical and computational results provide insight into the relationship between graph structure and the existence of neighbour-sum assignments.
This thesis investigates the neighbour-sum problem for several classes of graphs using techniques from spectral graph theory, linear algebra, and Fourier analysis on finite groups. Complete characterizations are obtained for path graphs and cycle graphs through explicit formulas for their spectra. These results are extended to Cayley graphs over finite abelian groups, yielding explicit eigenvalue conditions for circulant graphs in terms of group characters. For trees, theoretical results are derived for several special families, including stars, double stars, and caterpillar trees, and an asymptotic result shows that the proportion of solvable trees tends to one as the number of vertices increases.
In addition, computational experiments were performed on all non-isomorphic trees with up to twenty vertices and on connected circulant graphs of small order. The experiments reveal how structural properties such as the number of leaves, maximum degree, diameter, and generating set influence solvability, and suggest that larger trees are increasingly likely to admit non-trivial solutions. Together, the theoretical and computational results provide insight into the relationship between graph structure and the existence of neighbour-sum assignments.
Critical Exponents in Long-Range Percolation
Theory and estimation
In this thesis we study the long-range percolation model on Zd, where each pair of vertices x, y ∈ Zd form a connection with probability 1 − exp(−βJ(x, y)), and J(x, y) decays asymptotically with the form ∥x − y∥−dα. The parameter α > 0 is fixed, while β can be varied. This model is an extension of the classical Bernoulli bond percolation model allowing the modeling of connection phenomena where long-distance connections play a crucial role. In this paper we study the critical value βc, the percolation probability θ(β) = Pβ (|K0| = ∞) and we investigate the critical exponent δ explaining the cluster decay at criticality. We compile known bounds for the critical exponent δ and derive foundational results for βc. In the numerical part we simulate long-range percolation on finite boxes, create new estimators for the percolation probability θ(β) and studying existing ones for the critical parameter βc. Using this estimate for βc we estimate the critical parameter δ using linear regression. The estimators for θ(β) and βc show consistent stable behaviour conforming to theory. The estimates for δ in contrast are sensitive to the finite size approximation, showcasing the limits of simulating critical parameters on a finite scale. ...
In this thesis we study the long-range percolation model on Zd, where each pair of vertices x, y ∈ Zd form a connection with probability 1 − exp(−βJ(x, y)), and J(x, y) decays asymptotically with the form ∥x − y∥−dα. The parameter α > 0 is fixed, while β can be varied. This model is an extension of the classical Bernoulli bond percolation model allowing the modeling of connection phenomena where long-distance connections play a crucial role. In this paper we study the critical value βc, the percolation probability θ(β) = Pβ (|K0| = ∞) and we investigate the critical exponent δ explaining the cluster decay at criticality. We compile known bounds for the critical exponent δ and derive foundational results for βc. In the numerical part we simulate long-range percolation on finite boxes, create new estimators for the percolation probability θ(β) and studying existing ones for the critical parameter βc. Using this estimate for βc we estimate the critical parameter δ using linear regression. The estimators for θ(β) and βc show consistent stable behaviour conforming to theory. The estimates for δ in contrast are sensitive to the finite size approximation, showcasing the limits of simulating critical parameters on a finite scale.
Graphs are mathematical models that contain information about objects (vertices) and relations between those objects (edges). A drawing, also called an embedding, of a graph is made by representing the vertices as points in R2 and the edges as curves between their endpoints. When these curves only intersect in their endpoints, the embedding is planar. Graphs that have such an embedding are planar graphs. There is no fixed set of rules when it comes to drawing a graph. So how to decide how a graph should be drawn?}
One method of drawing a graph is called the rubber band representation, where some vertices are initially fixed as a strictly convex polygon on the Euclidean plane and all remaining vertices are placed in the barycenter of their neighbours. For the rubber band representation of 3-connected planar graphs, further referred to as the Tutte embedding, Tutte's theorem states that all connected regions that are bounded by edges (called faces) are strictly convex, these faces do not contain vertices or edges.
This research adapted the optimization problem corresponding to the Tutte embedding by changing the objective function, while making sure the embedding remained compliant with Tutte's theorem. In doing so, new methods for graph drawing can be examined and used in various areas, depending on the individual context and application of the drawing.
Two types of objective functions were analysed. The first type, based on existing research, minimizes the difference between the length of the edges and their desired length. The second type was proposed by this research and minimizes the differences between the surface area of all faces within the embedding.
The first type of objective functions yielded embeddings with a similar structure as the Tutte embedding, maintaining the symmetries of the graph, but with different proportions. The embeddings that were yielded by the second type of objective function were different. Some of which do not maintain the symmetric characteristics of the graph. A notable feature is that for some graphs, there exist several local minima with corresponding embeddings that are significantly different from each other.
This report contains the analysis of the different objective functions and their results. The results show that there are multiple ways to draw 3-connected planar graphs compliant with Tutte's theorem. Moreover, it provides options for further analysis of the objective functions and paves the way for further research possibilities.
...
Graphs are mathematical models that contain information about objects (vertices) and relations between those objects (edges). A drawing, also called an embedding, of a graph is made by representing the vertices as points in R2 and the edges as curves between their endpoints. When these curves only intersect in their endpoints, the embedding is planar. Graphs that have such an embedding are planar graphs. There is no fixed set of rules when it comes to drawing a graph. So how to decide how a graph should be drawn?}
One method of drawing a graph is called the rubber band representation, where some vertices are initially fixed as a strictly convex polygon on the Euclidean plane and all remaining vertices are placed in the barycenter of their neighbours. For the rubber band representation of 3-connected planar graphs, further referred to as the Tutte embedding, Tutte's theorem states that all connected regions that are bounded by edges (called faces) are strictly convex, these faces do not contain vertices or edges.
This research adapted the optimization problem corresponding to the Tutte embedding by changing the objective function, while making sure the embedding remained compliant with Tutte's theorem. In doing so, new methods for graph drawing can be examined and used in various areas, depending on the individual context and application of the drawing.
Two types of objective functions were analysed. The first type, based on existing research, minimizes the difference between the length of the edges and their desired length. The second type was proposed by this research and minimizes the differences between the surface area of all faces within the embedding.
The first type of objective functions yielded embeddings with a similar structure as the Tutte embedding, maintaining the symmetries of the graph, but with different proportions. The embeddings that were yielded by the second type of objective function were different. Some of which do not maintain the symmetric characteristics of the graph. A notable feature is that for some graphs, there exist several local minima with corresponding embeddings that are significantly different from each other.
This report contains the analysis of the different objective functions and their results. The results show that there are multiple ways to draw 3-connected planar graphs compliant with Tutte's theorem. Moreover, it provides options for further analysis of the objective functions and paves the way for further research possibilities.
Two-Dimensional Nowhere- Zero Flows on Graphs
Determining Two-Dimensional Flow Numbers for Complete and Cubic Graphs
A nowhere-zero flow on a directed graph is a function that assigns a value to each edge such that each vertex has equal in- and outflow. This concept is generalized to d-dimensional nowhere-zero flows. The two-dimensional flow number of a graph is the smallest number r such that the graph has a two-dimensional nowhere-zero flow using only vectors with lengts between 1 and r-1.
In this paper, two-dimensional flow numbers are determined for several graphs. First, these are determined for all complete multipartite graphs. Second, flow triangulations are researched, and a flow triangulation is found for the Wagner graph. Furthermore, this research addresses the question whether a nice flow triangulation exists for all bipartite cubic graphs. Furthermore, optimization models are used to approximate two-dimensional flow numbers of certain graphs, including snarks.
...
In this paper, two-dimensional flow numbers are determined for several graphs. First, these are determined for all complete multipartite graphs. Second, flow triangulations are researched, and a flow triangulation is found for the Wagner graph. Furthermore, this research addresses the question whether a nice flow triangulation exists for all bipartite cubic graphs. Furthermore, optimization models are used to approximate two-dimensional flow numbers of certain graphs, including snarks.
...
A nowhere-zero flow on a directed graph is a function that assigns a value to each edge such that each vertex has equal in- and outflow. This concept is generalized to d-dimensional nowhere-zero flows. The two-dimensional flow number of a graph is the smallest number r such that the graph has a two-dimensional nowhere-zero flow using only vectors with lengts between 1 and r-1.
In this paper, two-dimensional flow numbers are determined for several graphs. First, these are determined for all complete multipartite graphs. Second, flow triangulations are researched, and a flow triangulation is found for the Wagner graph. Furthermore, this research addresses the question whether a nice flow triangulation exists for all bipartite cubic graphs. Furthermore, optimization models are used to approximate two-dimensional flow numbers of certain graphs, including snarks.
In this paper, two-dimensional flow numbers are determined for several graphs. First, these are determined for all complete multipartite graphs. Second, flow triangulations are researched, and a flow triangulation is found for the Wagner graph. Furthermore, this research addresses the question whether a nice flow triangulation exists for all bipartite cubic graphs. Furthermore, optimization models are used to approximate two-dimensional flow numbers of certain graphs, including snarks.
This thesis addresses the portfolio allocation problem within a financial market featuring one riskless asset and a risky asset exhibiting rough Bergomi volatility. The objective is to maximize the expected utility of terminal wealth with respect to power utility. The volatility process in the model is driven by fractional Brownian motion and does not fit within the Markovian or semimartingale frameworks. To address this issue, we explore Markovian approximations for fractional processes and apply them to the rough Bergomi model, resulting in a multi-factor stochastic volatility model. This approach facilitates the development of a practical simulation scheme employing Gaussian quadrature and Cholesky decomposition, and allows us to address the portfolio optimization problem within a Markovian context. We solve the optimization problem using the Hamilton-Jacobi-Bellman equation, deriving an implicit solution for the case where volatility and stock return are driven by correlated Brownian motions, and providing an explicit solution for the case where they are uncorrelated. The validity of these results is further confirmed through a numerical study. ...
This thesis addresses the portfolio allocation problem within a financial market featuring one riskless asset and a risky asset exhibiting rough Bergomi volatility. The objective is to maximize the expected utility of terminal wealth with respect to power utility. The volatility process in the model is driven by fractional Brownian motion and does not fit within the Markovian or semimartingale frameworks. To address this issue, we explore Markovian approximations for fractional processes and apply them to the rough Bergomi model, resulting in a multi-factor stochastic volatility model. This approach facilitates the development of a practical simulation scheme employing Gaussian quadrature and Cholesky decomposition, and allows us to address the portfolio optimization problem within a Markovian context. We solve the optimization problem using the Hamilton-Jacobi-Bellman equation, deriving an implicit solution for the case where volatility and stock return are driven by correlated Brownian motions, and providing an explicit solution for the case where they are uncorrelated. The validity of these results is further confirmed through a numerical study.
Constructions for the cap set problem
Asymptotic lower bounds on the size of cap sets
The objective of the cap set problem is finding the maximum size of a d-cap: a subset of 𝔽3d not containing three elements in line. This thesis aims to give a comprehensive overview of constructions for the cap set problem, with a focus on improvements of the asymptotic lower bound on the size of caps that have already been made.
Finding an asymptotic lower bound on the size of caps boils down to finding a cap C in a dimension d such that its solidity, given by |D|1/d, is as large as possible. We start with studying caps in low dimensions, of which the maximum sizes are exactly known. Then to further improve the asymptotic lower bound we turn to caps in higher dimensions. Here, the art lies in carefully combining large caps in low dimensions to construct large caps in higher dimensions by taking products. One construction that allows us to do this is the extended product construction, which extends extendable collections of caps with admissible sets.
This thesis explains the extended product construction and gives an overview of how it has been used and expanded to repeatedly increase the asymptotic lower bound. As the literature sometimes lacks detail, this thesis adds to the literature by incorporating examples, explicit constructions of (recursively) admissible sets, and experiments with the extended product construction.
In Chapter 6, we prove the existence of recursively admissible sets of constant weight 2 and 3 for any dimension k by giving explicit constructions and proving that the resulting sets satisfy all necessary conditions. Moreover, we classify all admissible sets in dimensions 2 and 3 and all extendable collections in dimensions 1, 2, and 3. Then, we use these to deduce that the extended product construction is less effective in low dimensions by showing that the largest possible caps we can construct this way in dimensions 4, 6, and 8 are never as large as caps constructed by taking direct products of maximum caps. ...
Finding an asymptotic lower bound on the size of caps boils down to finding a cap C in a dimension d such that its solidity, given by |D|1/d, is as large as possible. We start with studying caps in low dimensions, of which the maximum sizes are exactly known. Then to further improve the asymptotic lower bound we turn to caps in higher dimensions. Here, the art lies in carefully combining large caps in low dimensions to construct large caps in higher dimensions by taking products. One construction that allows us to do this is the extended product construction, which extends extendable collections of caps with admissible sets.
This thesis explains the extended product construction and gives an overview of how it has been used and expanded to repeatedly increase the asymptotic lower bound. As the literature sometimes lacks detail, this thesis adds to the literature by incorporating examples, explicit constructions of (recursively) admissible sets, and experiments with the extended product construction.
In Chapter 6, we prove the existence of recursively admissible sets of constant weight 2 and 3 for any dimension k by giving explicit constructions and proving that the resulting sets satisfy all necessary conditions. Moreover, we classify all admissible sets in dimensions 2 and 3 and all extendable collections in dimensions 1, 2, and 3. Then, we use these to deduce that the extended product construction is less effective in low dimensions by showing that the largest possible caps we can construct this way in dimensions 4, 6, and 8 are never as large as caps constructed by taking direct products of maximum caps. ...
The objective of the cap set problem is finding the maximum size of a d-cap: a subset of 𝔽3d not containing three elements in line. This thesis aims to give a comprehensive overview of constructions for the cap set problem, with a focus on improvements of the asymptotic lower bound on the size of caps that have already been made.
Finding an asymptotic lower bound on the size of caps boils down to finding a cap C in a dimension d such that its solidity, given by |D|1/d, is as large as possible. We start with studying caps in low dimensions, of which the maximum sizes are exactly known. Then to further improve the asymptotic lower bound we turn to caps in higher dimensions. Here, the art lies in carefully combining large caps in low dimensions to construct large caps in higher dimensions by taking products. One construction that allows us to do this is the extended product construction, which extends extendable collections of caps with admissible sets.
This thesis explains the extended product construction and gives an overview of how it has been used and expanded to repeatedly increase the asymptotic lower bound. As the literature sometimes lacks detail, this thesis adds to the literature by incorporating examples, explicit constructions of (recursively) admissible sets, and experiments with the extended product construction.
In Chapter 6, we prove the existence of recursively admissible sets of constant weight 2 and 3 for any dimension k by giving explicit constructions and proving that the resulting sets satisfy all necessary conditions. Moreover, we classify all admissible sets in dimensions 2 and 3 and all extendable collections in dimensions 1, 2, and 3. Then, we use these to deduce that the extended product construction is less effective in low dimensions by showing that the largest possible caps we can construct this way in dimensions 4, 6, and 8 are never as large as caps constructed by taking direct products of maximum caps.
Finding an asymptotic lower bound on the size of caps boils down to finding a cap C in a dimension d such that its solidity, given by |D|1/d, is as large as possible. We start with studying caps in low dimensions, of which the maximum sizes are exactly known. Then to further improve the asymptotic lower bound we turn to caps in higher dimensions. Here, the art lies in carefully combining large caps in low dimensions to construct large caps in higher dimensions by taking products. One construction that allows us to do this is the extended product construction, which extends extendable collections of caps with admissible sets.
This thesis explains the extended product construction and gives an overview of how it has been used and expanded to repeatedly increase the asymptotic lower bound. As the literature sometimes lacks detail, this thesis adds to the literature by incorporating examples, explicit constructions of (recursively) admissible sets, and experiments with the extended product construction.
In Chapter 6, we prove the existence of recursively admissible sets of constant weight 2 and 3 for any dimension k by giving explicit constructions and proving that the resulting sets satisfy all necessary conditions. Moreover, we classify all admissible sets in dimensions 2 and 3 and all extendable collections in dimensions 1, 2, and 3. Then, we use these to deduce that the extended product construction is less effective in low dimensions by showing that the largest possible caps we can construct this way in dimensions 4, 6, and 8 are never as large as caps constructed by taking direct products of maximum caps.