Ramsey Property for the Class of Linearly Ordered Hypertournaments

Nicholas Selgas

Authors:  Nicholas Selgas

Faculty Mentor: Dr. Dana Bartosova

College:  College of Liberal Arts and Sciences

Abstract

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.

Poster Pitch

Click the video below to view the student's poster pitch.

Poster

Click the image to enlarge.
6 Responses
  1. Nicholas Selgas

    Here’s a zoom ID 126-291-150 if you’d like to see me draw some relevant pictures and explanations for these things

  2. Pranav Chinmay

    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

  3. Nicholas Selgas

    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.

    1. Pranav Chinmay

      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}?

  4. Nicholas Selgas

    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.