Research

The Problem: The odd-Ramsey number number r_odd(G,F) is the minimum number of colors required to edge-color the graph G so that every copy of of the graph F, in G, has a color appearing an odd number times among the edges of F. If F has an odd number of edges to begin with, then you can trivially color every edge of G with a single color, but when F has an even number of edges, this problem ends up being quite more difficult. Many results for odd-Ramsey numbers consider the special case when the host graph G is a complete graph K_n and  F is also a small complete graph. A deviation of this was studied by Bennett, Heath, and Zerbib where they considered the host graph to be the balanced, complete bipartite graph K_n,n and F was the graph K_2,2. They determined that the odd-Ramsey number is asymptotically equal to n/2.

An Example: Shown below is an example of K_4,4 where every copy of K_2,3 has a color appearing an odd number of times. In the figure, 5 colors are used. Can you use fewer?

Our Progress: In Odd Ramsey numbers of  multipartite graphs and hypergraphs, we generalize r_odd(K_n,n , K_2,2) = n/2 and determine the odd-Ramsey number when the host graph is again K_n,n and F is K_2,t for any t at least 2. We show that the odd-Ramsey number is asymptotically equal to n/t. Our proof uses a method known as the conflict-free tripartite matching method. We also generalize the K_2,2 result by computing the first odd-ramsey number for hypergraphs.

Definitions: A (finite) topology is a collections of sets from a (finite) ground set X which contain the empty-set, X itself,  and is  closed under unions and finite intersections. In Graphs generated from minimal sets of finite topologies, we build graphs from a finite topology, where the vertices are the elements in X and two elements are adjacent if they are not "separated". Here we define "separated" from the topological separation axioms (see here). Thus, for every notion of separation: T0,T1,T2,T3, and T4 we build a different graph class.

The Problem: The main goal of our paper is to address the question: which graphs can arise when constructing the Ti-separation graph from various finite topologies? For example: Is there a topology out there whose T2-graph is a cycle on 4 vertices? (The answer to this is actually no!)

An Example: In the figure below we see a visual interpretation for the minimal sets in the topology generated by the minimal sets: {1}, {1,2,3}, {3}, {3,4,5}. Since the minimal set containing 2 ({1,2,3}) intersects with the minimal set containing 4 ({3,4,5}) we add the edge between 2 and 4! If you do this for every pair of vertices, you will get the graph see on the right. This standard notion of intersection is what we refer to as T2-adjacent.

Our Progress: as it turns out, under a different perspective, T1- and T2- graphs are both well studied classes of graphs, the first being comparability graphs and the second are upper-bound graphs (equivalently edge-simplicial graphs). We extend these classical results by exploring the T3-graphs and the clique-like structures these graphs possess.

Definitions: For each vertex v of a graph G, let F(v) denote v's list of forbidden out-degrees. An F-avoiding orientation of a graph G is an orientation of G such that the out-degree of each vertex v is not contained in its forbidden list F(v). For example if  F(v) = {1,3,4} then v having out-degree 1, 3, or 4 is not allowed but v having out-degree 0, 2, 5, 6, ... is allowed.

An Example: The figure below gives a {1,2}-avoiding orientation of a graph G. If F(v) is the same for every vertex we can explicitly write what F is (in this case {1,2}). Since the maximum degree of any vertex is 5, every vertex of G has out-degree either 0, 3, 4, or 5.

The Problem: Akbari, Dalirrooyfard, Ehsani, Ozeki, and Sherkati conjectured that if the size of v's forbidden list is less than half the degree of v, for all vertices, then G admits an F-avoiding orientation. The conjecture is still open even when F is the same for all vertices.

Our Progress: In On orientations with forbidden out-degrees we validate the conjecture when G is 5- and 6-regular and F is the same for all vertices. We use a new technique of modifying orientations using what we term a lasso. We also validate the conjecture for several special families of graphs.

Definitions: An odd k-coloring of a graph is a proper vertex coloring with k colors such that each non-isolated vertex has a color appearing an odd number of times in its neighborhood. Similarly, a proper conflict-free k-coloring of a graph is a proper vertex coloring with k colors such that every non-isolated vertex has a color appearing exactly once in its neighborhood.

An Example: Shown in the above figure is a graph with an odd 5-coloring. Since every vertex has degree 4, if a neighborhood contains a color appearing an odd number of times (once or three times), then it must contain a color appearing once too. This means it is also a PCF 5-coloring!

The Problem: Petruševski and Škrekovski conjecture that every planar graph can be odd colored with at most 5 colors. Similiarly, Fabrici, Luzar, Rindosová, and Soták conjecture that every planar graph can be PCF colored with at most 6 colors. 

Our Progress: In The forb-flex method for odd coloring and proper conflict-free coloring of planar graphs  we show that the minimum number of colors needed to odd color a planar graph with girth at least 10 is 4, and the minimum colors needed to PCF color a planar graph with girth at least 11 is 4.

Definitions: A set of points in the plane is a diameter 1 point-set if the Euclidean distance between any two points is at most 1.

The Problem: Jung's theorem shows that any diameter 1 point-set can be covered by a circle with radius 1/sqrt(3) (which is approximately .577). In On a generalized hexagonal dart board problem, we ask the following fractional generalization. Question: For a fixed radius r between 0 and 1, what percentage of a diameter 1 point-set can a circle with radius r always cover?

Our Progress: A result of Borsuk shows that every diameter 1 set can be covered by a regular hexagon whose opposite sides are distance 1 apart. Such a shape is called a universal cover. Finding congruent circle coverings of universal covers gives lower bounds for the above question, and finding creative diameter 1 point-set constructions gives upper bounds. Along with finding other, it turns out the correct answer for r = 1/2 is 1/3 of the points and for r=1/4 it is 1/7 of the points! 

Definitions: Given a packing of obstacles in the plane P, and two points S and T (not contained in the interior of any obstacle), we say a path from S to T is P-avoiding if  the intersection of  the path and the interior of the obstacles is empty.

The Problem: In the 1970's, L. Fejes Tóth conjectured that if P is a packing of squares with side lengths at most one, and S and T are points not contained in the interior of any squares at a distance d apart, then there exists a P-avoiding path from S to T of length at most (3/2)d+1/2. This bound sharp by the following square packing. Consider vertical strips of unit squares are placed next to each other so that every other strip is translated vertically by 1/2.

History: Tóths conjecture was proved true asymptotically by J. Pach in 1977 and then exactly by G. Fejes Tóth in 1978, of which both proofs show just the existence of such a path. In the 90's Papadimitriou and Yannakakis and independently A. Bezdek found different algorithms which achieves a path of length at most (3/2)d+o(d).

Our Progress: In Short path and short chain problems in the plane, we give a new, elegant algorithmic proof again achieving a path of length at most  (3/2)d+o(d). We also consider the dual problem: finding a short path algorithm in the double-covered areas of a square covering!

History: Sprouts is a 2-player combinatorial game played on a piece of paper (similar to tic-tac-toe, dots & boxes, or SOS) created by John Conway in the sixties. Brussel Sprouts is a well-known variant of sprouts which in which the winning player is completely determines by the parity of the number of initial crosses. Check out the wikipedia page here for the rules of both Sprouts and Brussels Sprouts!

Our Progress: In On Conway's Brussels Sprouts we considered several colored versions of the game and found by just slightly changing the way in which colors are introduced, the outcome of the games change drastically. We solve several colored variations as well as special cases for others, bounding the number of moves and considering both normal and misère play.