This page contains a a selection of a few questions which have come out of various areas of my research. For more questions, take a look at the end of the manuscripts on the Publications page.
I would be very interested to hear if anyone knows of some recursive constructions of k-critical graphs of fixed odd-girth ℓ. Here, by k-critical, I mean that the chromatic number is k, and removing an edge decrease the chromatic number. The odd-girth of a graph is the length of the shortest odd cycle. (Mycielski's operation is such a construction for the case ℓ=5).
In an ‘achievement‘ game played on a hypergraph, players take turns selecting previously unchosen vertices of the hypergraph, with the goal controlling all the vertices of some edge with just their own points. (Example: Tic-Tac-Toe is an achievement game where the hypergraph game has 9 vertices and 8 edges.)
We can define the biased versions of games, where, for example, Player 1 might get to choose 2 points on each turn of an achievement game, while Player 2 can only choose 1 point on each turn. There are many interesting questions and results about these biased games.
We can also define the cooperative bias of an achievement game, where Player 1 gets to select (for example) 2 points on each turn, but they are of different ‘classes’: for example, maybe he gets to color one point blue and one point red on each turn, but to win, he must occupy some edge either only with blue or only with red. In this case, it is as if there are three players of the game, and two of them are ganging up on the third.
We want to consider the behavior of the cooperative bias on some extremely simple k-regular hypergraphs. One which is certainly very simple is the hypergraph where the m edges are all disjoint. Of course in the regular achievement game Player 1 cannot win, and it is easy to see that in the regular 2:1 biased game, Player 1 can win in exactly 2k-1 turns. What about in the 2:1 cooperative bias game? Player 1 can certainly still win, but I cannot tell you exactly how long it takes. Is it exponential in k? Or more like (k!)? I can’t rule out either of these possibilities.
Given a a vertex v in a graph G, call the sequence {fv(k)}, where fv(k) is the number of vertices at distance exactly k from v, the distance sequence of G at v. If G is a vertex-transitive graph (for example, if it is a Cayley graph), then the sequence does not depend on the choice of v, and so we can refer simply to the distance sequence f(k) of G. If G is vertex-transitive of infinite degree, we know that its distance sequence is constant except possibly at the last term.
Now for a set X, let fX(k) be number of vertices u for which the shortest
distance between u and the set X is k. (This sequence now may depend on the set X
even if G is vertex-transitive.) Here is a question: is it perhaps still true, though, that
this sequence is always constant except possibly at the last term, if X is a finite
set? I also don't know the answer in the special case where G is a Cayley graph.