WC
W.P.S. Cames van Batenburg
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>
2 records found
1
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 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.
...
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 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.
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.