Authors: Nicholas Selgas
Faculty Mentor: Dr. Dana Bartosova
College: College of Liberal Arts and Sciences
Hypertournaments are a structure to which you can arrive by combining ideas from two related structures, the tournament and the hypergraph. When equipped with a linear order on their vertices, the hypertournaments form a class with certain properties we’d like to investigate. The two questions of interest to us are as follows: is this class Fraïssé and is this class Ramsey? The former question pertains to the closure of the class with respect to different sorts of embeddings. More specifically, we would like to show that whenever we have something embedded into a hypertournament, then that thing is actually a hypertournament and that for any two hypertournaments, there is a third into which both can be embedded. If our class satisfies these properties and a couple others, we say it’s Fraïssé. The main problem, though, is regarding whether or not our class is Ramsey: that is, whenever we have A embedded in B we can find a C with B embedded in it so that when we color all the copies of A in C by some finite number of colors, we can find a monochromatic copy of B in C.
Here’s a zoom ID 126-291-150 if you’d like to see me draw some relevant pictures and explanations for these things
If it asks for a password, it should be 342579
Hi Nicholas,
This looks very interesting: from what I recall, the canonical Ramsey problem deals with monochromatic complete subgraphs of a finitely-coloured complete graph. What is the correct interpretation of “Ramsey” in this context? Is there some categorical notion of “Ramseyness”?
Chinmay
Yes actually! “Ramseyness” is very much recognized in category theory and it’s fairly common for results to be proven using the language of category theory. I’m not sure how familiar you are with category theory, but by a “class being Ramsey” we mean that given an embedding A into B from our class, and integers k greater than or equal to 2, there exists an object C from our class with B embedded into C such that for all colorings c of copies of A in C by k colors, there exists a copy of B in C such that all the copies of A in B are monochromatic.
I see. Say I’m in the category G, where the objects are complete graphs and the morphisms are presumably regular functions that preserve the adjacency matrix. Now G is Ramsey, right? What do the A, B and C correspond to in the case of the classical Ramsey number R_{m,n}?
So the categories I’ve been looking at the most are that of linearly ordered graphs, tournaments, and hypergraphs where the morphisms are embeddings – or injections that completely preserve the structure. I can’t recall specifically seeing a category of the kind you’ve described, but all the ones I’ve listed do have the Ramsey property. This Ramsey property for categories is a generalization of other Ramsey theorems and so don’t nicely correspond to the specific cases like when you look at complete graphs where R_{m,n} is well defined. In other words, the only part that seems to correspond to the less general Ramsey theorem for colorings of edges of complete graphs is the C we’re looking for, as the category C satisfying that coloring property is our solution to the Ramsey question. Once you have that such a C exists for all A embedded in B and k at least 2, you could ask what is the smallest such C that works whenever “small” means something in the same way that you ask what is the smallest number n of vertices such that coloring all the edges of a complete graph will yield a monochromatic clique of some sort.