Research

Let me begin by asking several questions that I would like to know the answer to.

Super-cyclic bipartite graphs

All graph theorists have heard of Hall's theorem: if G is a finite bipartite graph with bipartition (X, Y), there is a matching in G that saturates X if and only if, for every subset S of X, the condition

|N(S)| > |S|

holds, where N(S) is the set of vertices in Y with a neighbor in S. This condition is definitely necessary: the matching we want to find gives us a set of |S| vertices with neighbors in S. The surprising thing is that it is sufficient.

What if, instead of the matching, we would like to find a cycle in G of length 2|X|? What if we want more than that: what if we want it to be true that, for any subset S of X, there is a cycle of length 2|S| that passes through every vertex in S? We call bipartite graphs with this property "super-cyclic", and in order for a graph to be super-cyclic, there is another definitely necessary condition:

|Λ(S)| > |S|

where Λ(S) is the set of vertices in Y with at least two neighbors in S. Is this necessary condition also sufficient? I think it is, though so far we've only been able to prove it in special cases.

The Hales–Jewett numbers

As you probably know, if you play tic-tac-toe on a 3×3 board, and both players are at least a little careful about the moves they make, the game will probably end in a draw.

On the other hand, if you play four-dimensional tic-tac-toe on a 3×3×3×3 board, there are just too many lines - even if both players would really like a draw, they will not be able to achieve one! (A player that wants to win should probably play in the center, but that's not the sort of thing I'm interested in.)

The Hales–Jewett theorem is (aside from some quibbles meant to make the question easier to state formally and to generalize) the statement that for any "side length" t, we can pick a sufficiently large dimension for a t×t×t×t×...×t tic-tac-toe board on which a draw is similarly impossible. I'm interested in it because there is a huge gap between the dimension we know is sufficiently large (which requires nested "power towers" to state) and the dimensions we know is not sufficiently large (which is merely exponential).

For a 4×4×...×4 board in particular, I've had some luck getting better (merely astronomically large) bounds that by avoiding the repeated use of the pigeonhole principle as seen in classical arguments, in favor an approach that relies on averaging inequalities. Maybe some kind of clever harmonic analysis tricks can help us here? Maybe we can describe combinatorial lines in a grid using flag algebras, and generalize that way? Maybe we can tackle some small cases with a SAT solver?

Will any of these tricks be enough for 5×5×...×5?

Ramsey games in ordered graphs

The ordered graph game is played by two players, traditionally named Builder and Painter. An empty infinite graph on vertices 1, 2, 3, 4, 5, ... is their game board. This graph is ordered, meaning that when we take subgraphs, we keep track of the relative order of the vertices of the subgraph.

On each turn, Builder adds edge in the graph, and Painter gives that edge a color (red or blue, perhaps, though we can consider what happens if the color supply is bigger). The game ends once one of several monochromatic subgraphs (chosen in advance) is created. Painter always wins, and wants to win as quickly as possible; Builder, upset by this unfair state of things, wants to delay Painter's inevitable victory for as long as possible.

I would like to know how long it takes Painter to win, especially in the following special cases:

• Painter wins when a red or blue ordered path of a given length is created. (A path is ordered if the numbers of the vertices increase along the path.) This is in some sense the most fundamental version of the ordered graph game, and we still do not know the precise growth rate of the answer.
• Painter wins when a red ordered path of a given length is created, or a blue ordered 4-cycle: a blue subgraph with vertices w < x < y < z and edges wx, xy, yz, zw. This is the first case in which we do not know if the number of turns scales linearly with the length of the ordered path!
• Can we describe the ordered graphs H such that, if the goal is to create either a red ordered path of length n or a blue copy of H, then Painter can win in n + C turns, where C is a constant that does not depend on n? We know that if this is true, then H must be a "non-intersecting matching", and we suspect that this condition is also sufficient.

So what is my research about?

My research is primarily in graph theory. I like thinking about extremal graph theory: trying to find the minimum or maximum value of a graph parameter, under certain conditions. A lot of the time, this leads me to Ramsey theory (questions like the second and third question above), which I am also interested in even when graphs are not involved.

Somehow, I often find myself thinking about questions regarding paths and cycles in graphs.

For a complete list of my submitted and published papers, see: https://misha.fish/research/.