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>
6 records found
1
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.