In an earlier post I talked about the work of Mubayi and Verstraete on determining the off-diagonal Ramsey numbers via certain optimal pseudorandom graphs, which are not yet known to exist except for the case of triangles. Beyond this conditional result, they also improved the lower bounds on certain cycle-complete Ramsey numbers using generalized polygons. In some cases they even beat the exponent provided by the general -free process studied by Bohman and Keevash, which
“appears to be the first instance of a graph containing cycles for which random graphs do not supply the right exponent for .”
(I have changed the from their paper to for my own convenience). In this post I will talk about the basics of their construction, hoping that these ideas can be used in future to obtain similar results on Ramsey numbers.
One of the fundamental objects that are studied in finite geometry are partial linear spaces, a.k.a., linear hypergraphs. These are point-line geometries with the property that through any two points there is at most one line, or equivalently, these are hypergraphs in which every two hyperedges share at most one common vertex. A partial linear space has order if ever line contains exactly points and through every point there are exactly lines (in hypergraph terminology we have an -uniform -regular hypergraph). For every partial linear space we can define the collinearity graph on the points by making to points adjacent if they lie on a common line (in hypergraph terminology this is sometimes referred to as the skeleton of the hypergraph). Note that the lines of the partial linear space correspond to cliques of size in the collinearity graph, and any two such cliques meet in at most a vertex. From now on denote the number of points in the partial linear space by and the number of lines by . In several classes of such spaces these numbers are a function of . For example, in the case of a finite projective plane we have and . Note that we always have .
For a graph , the Ramsey number can be defined as the largest number of vertices for which there exists a graph that has no subgraphs isomorphic to , and has independence number (the existence of such a maximum is a special case of Ramsey’s theorem). We would like to know the growth of this function as for various kinds of fixed size graphs . When is the complete graph, then this is the classical off-diagonal Ramsey number that we saw in the earlier post.
The basic idea behind the construction that I want to discuss in this post is as follows:
start with a partial linear space for which all copies of in the collinearity graph are contained inside the cliques corresponding to the lines and then destroy all of these copies of while keeping the independence number under control.
Let’s start with the independence number. If is a set of pairwise non-collinear points, then by an easy double count of pairs where is a point of and is a line through , we get . Therefore, the independence number is always at most .
If the graph contains odd cycles (which is the case we will focus on), then one easy way of getting rid of all the copies of is to convert each clique of size , which is where all copies of lie by our assumption, into a bipartite graph on the same set of vertices by destroying some edges. To be more precise, for each line we take two disjoint subsets of the points on , with and we define a graph on the set of all points where two points and are adjacent if (i) they lie in a common line and (ii) , or . This graph is well defined because we have a partial linear space, that is, no two points can lie in two different lines.
While what we do above ensures that there are no copies of in our collinearity graph, destroying edges would typically increase the independence number of the graph. What we can show though is that there does exist a choice of bipartition on each line so that the independence number cannot increase by much. We will show this by an easy probabilistic argument.
Here is our probability space. For each line , we choose a bipartition of the set of points on uniformly at random (from the set of all bipartitions). Then for any line , the probability that a point of lies in (or ) is equal to . We do this independently for each line.
Let be a subset of points, of size , and for each line let be the number of points of contained in . The probability that is an independent set in the graph obtained by removing all edges within and in the collinearity graph, for each line , is equal to the probability that for every line the set is either a subset of or . Since all these are independent events, with an event corresponding to having probability , the probability that is an independent set is equal to . The probability that there exists an independent set of size is then at most , by the union bound. Therefore, to show the complementary event that there exists a bipartition of each line for which the graph defined above has no independent sets of size , it suffices to show that this probability is . By the inequality , we see that it suffices to show
This is true if and only if . Thus, for, say , we get as there exists an -free graph on vertices with independence number .
This shows that to get a good lower bound on , what we want from our partial linear space of order on points and lines is and , beyond the condition we started with of all copies of being contained in the -cliques.
If you are still with me right now, then here is a concrete example. We know that any triangle in the collinearity graph of a generalized quadrangle (or see this) must be contained in the clique corresponding to a line. We also know that a generalized quadrangle (GQ for short) of order has points and lines. For , we would thus want and for we would want to not be a constant. Considering this, the best choice that we have with us here is , and , as we know that in any GQ one always has . Such GQ’s are known to exist whenever is a prime power (see Chapter 5 of my lecture notes). From them we get the lower bound , which is not that great considering we know . But there is some good news, as Mubayi and Verstraete have shown. If we consider generalized hexagons of order , then we get
and from generalized octagons of order we get
Both of these bounds are better than what one would get from purely probabilistic arguments.
I hope that by using other finite geometries, or by improving the argument above, we would be able to improve bounds on other Ramsey numbers as well.
Pingback: Sp(6, 2)’s Family, Plots, and Ramsey Numbers | Ratio Bound – A Combinatorics Blog
Pingback: Generalized polygons in extremal combinatorics | Anurag's Math Blog
Pingback: Improved lower bounds for multicolour diagonal Ramsey numbers | Anurag's Math Blog