Lv
L. van der Kuil
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
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.
Algebras are vector spaces with a bilinear product. When we fix a finite dimension n and a finite field K with q elements, there are a finite number of non-isomorphic algebras. Seeing as vector spaces are completely determined by the dimension and scalar field, the number of non-isomorphic algebras is the number of ways we can define a bilinear product of vectors. Exploiting the bilinearity of the product we can construct a surjection from vectors of n n by n matrices over K to non-isomorphic n-dimensional algebras over K. This function can be made injective by reducing to orbits under a group action on the set of vectors of matrices, thus providing a bijection. So the number of non-isomorphic algebras is equal to the number of orbits of this group action. In 2020 Verhulst used Burnside's Lemma to count the orbits and thus the number of non-isomorphic algebras. However, the formula he derived still requires a number of complicated calculations.
The aim of this thesis is to implement Verhulst's formula in python. In Table 4.1 you can find the output of the python script. The results for n=1 merely show some trivial cases. The results for n=2 fit the formulas obtained, using completely different methods, by Petersson and Scherer. The results for n=3 and n=4 are, to my knowledge, new. Currently, the limiting factor is computation time. A more powerful computer could squeeze out a few more results, but a more efficient formula is necessary. Based on the results, it seems that the contribution of the identity matrix in Verhulst's formula provides a decently tight lower bound. ...
The aim of this thesis is to implement Verhulst's formula in python. In Table 4.1 you can find the output of the python script. The results for n=1 merely show some trivial cases. The results for n=2 fit the formulas obtained, using completely different methods, by Petersson and Scherer. The results for n=3 and n=4 are, to my knowledge, new. Currently, the limiting factor is computation time. A more powerful computer could squeeze out a few more results, but a more efficient formula is necessary. Based on the results, it seems that the contribution of the identity matrix in Verhulst's formula provides a decently tight lower bound. ...
Algebras are vector spaces with a bilinear product. When we fix a finite dimension n and a finite field K with q elements, there are a finite number of non-isomorphic algebras. Seeing as vector spaces are completely determined by the dimension and scalar field, the number of non-isomorphic algebras is the number of ways we can define a bilinear product of vectors. Exploiting the bilinearity of the product we can construct a surjection from vectors of n n by n matrices over K to non-isomorphic n-dimensional algebras over K. This function can be made injective by reducing to orbits under a group action on the set of vectors of matrices, thus providing a bijection. So the number of non-isomorphic algebras is equal to the number of orbits of this group action. In 2020 Verhulst used Burnside's Lemma to count the orbits and thus the number of non-isomorphic algebras. However, the formula he derived still requires a number of complicated calculations.
The aim of this thesis is to implement Verhulst's formula in python. In Table 4.1 you can find the output of the python script. The results for n=1 merely show some trivial cases. The results for n=2 fit the formulas obtained, using completely different methods, by Petersson and Scherer. The results for n=3 and n=4 are, to my knowledge, new. Currently, the limiting factor is computation time. A more powerful computer could squeeze out a few more results, but a more efficient formula is necessary. Based on the results, it seems that the contribution of the identity matrix in Verhulst's formula provides a decently tight lower bound.
The aim of this thesis is to implement Verhulst's formula in python. In Table 4.1 you can find the output of the python script. The results for n=1 merely show some trivial cases. The results for n=2 fit the formulas obtained, using completely different methods, by Petersson and Scherer. The results for n=3 and n=4 are, to my knowledge, new. Currently, the limiting factor is computation time. A more powerful computer could squeeze out a few more results, but a more efficient formula is necessary. Based on the results, it seems that the contribution of the identity matrix in Verhulst's formula provides a decently tight lower bound.