The number of maximal left-compressed intersecting families

A family of sets (subsets of of size ) is intersecting if every pair of sets in have a common element.  If then every pair of sets intersect, so can be as large as .  If then the Erdős–Ko–Rado theorem states that , which (up to relabelling of the ground set) is attained only by the star  of all sets containing the element .

A hands on proof of the Erdős–Ko–Rado theorem use a tool called compression.  A family is left-compressed if for every , any set obtained from by deleting an element and replacing it by a smaller one is also in .  You can show by repeatedly applying a certain compression operator that for every intersecting family there is a left-compressed intersecting family of the same size.  Thus it suffices to prove the Erdős–Ko–Rado theorem for left-compressed families, which is easy to do by induction.

There is a strong stability result for large intersecting families.  The Hilton–Milner family consists of all sets that contain and at least one element of , together with itself.  This is an intersecting family, and in fact is the largest intersecting family not contained in a star.  The Hilton–Milner family has size , so any family that gets anything like close to the Erdős–Ko–Rado bound must be a subset of a star.

As part of an alternative proof of the Hilton–Milner theorem, Peter Borg partially answered the following question.

Let be an intersecting family and let .  Let .  For which is ?

Borg used that fact that this is true for to reprove the Hilton–Milner theorem.  In Maximum hitting for sufficiently large I completed the classification of for which this is true for large .  The proof used the apparently new observation that, for , every maximal left-compressed intersecting family in corresponds to a unique maximal left-compressed intersecting family of .  In particular, the number of maximal left-compressed intersecting families for is independent of .  For there are such families respectively.  In the rest of this post I’ll explain how I obtained these numbers.

We want to count maximal left-compressed intersecting families of .  The maximal part is easy: the only way to get two disjoint sets of size from is to take a set and its complement, so we must simply choose one set from each complementary pair.  To make sure the family we generate in this way is left-compressed we must also ensure that whenever we choose a set we must also choose every set with , where means “ can be obtained from by a sequence of compressions”.  The compression order has the following properties.

• If and then if and only if for each .
• if and only if .

Here’s one concrete algorithm.

1. Generate a list of all sets from .  This list has one set from each complementary pair.
2. Put all from the list with into .  (These sets must be in every maximal left-compressed intersecting family.)  Note that we never have as contains but doesn’t.
3. Let be the first element of the list and branch into two cases depending on whether we take or .
• If we take , also take all from the list with and for all from the list with . (Since contains and doesn’t, the second condition will never actually trigger.)
• If we take , also take all from the list with and for all from the list with . It is cheaper to test than the second condition to avoid taking complements.
4. Repeat recursively on each of the two lists generated in the previous step.  Stop on each branch whenever the list of remaining options is empty.

The following is a fairly direct translation of this algorithm into Haskell that makes no attempt to store the families generated and just counts the number of possibilities.  A source file with the necessary import’s and the choose function is attached to the end of this post.

r = 5

simpleOptions = [a | a <- choose r [1..(2*r-1)], not [dollar-sign] a simpleLeftOf (simpleComplement a)]

simpleLeftOf xs ys = all id [dollar-sign] zipWith (<=) xs ys

simpleComplement a = [1..(2*r)] \\ a

simpleCount [] = 1
simpleCount (a:as) = simpleCount take + simpleCount leave
where
-- take a
-- all pairs with b < a or b^c < a are forced
-- second case never happens as b^c has 2r but a doesn't
take = [b | b <- as, not [dollar-sign] b simpleLeftOf a]
-- leave a, and so take a^c
-- all pairs with b < a^c or b^c < a^c (equivalently, a < b) are forced
c = simpleComplement a
leave = [b | b <- as, not (b simpleLeftOf c || a simpleLeftOf b)]


This will compute the number of maximal left-compressed intersecting families for in a fraction of a second.  For it would probably find the answer in less than a month.  I obtained the value for in a couple of days on a single core by using a better representation of the sets in our family.

The dream is to pack all of the elements of our list into a single machine word and perform each comparison in a small number of instructions.  For example, we could encode an element of by writing each element as binary digits then concatenating them in increasing order to obtain a 24 bit word.  But comparing two such words as integers compares the corresponding sets lexicographically rather than pointwise.  Edward Crane suggested that as the lists are so short and the elements are so small we can afford to be quite a lot more wasteful in our representation: we can write each element of our set in unary!  The rest of this section should be considered joint work with him.

The first iteration of the idea is to write each element of as a string of 1’s followed by 0’s, then concatenate these strings to obtain a representation of our set.  This representation has the great advantage that we can compare sets pointwise by comparing strings bitwise, and we can do this using very few binary operations: is contained in if and only if .

Unfortunately this representation uses 72 bits in total, so won’t fit into a 64-bit machine word. Observing that we never use and encoding by 1‘s followed by 0‘s saves only 6 bits. But we can do even better by encoding each element of the set differently. The first element is always at least 1, the second is always at least 2 and so on. Similarly, the first element is at most 7, the second at most 8 and so on. Working through the details we arrive at the following representation.

Identify each element of by an “up-and-right” path from the bottom left to the top right corner of a grid: at the th step move right if is in your set and up if it isn’t. Then if and only if the path corresponding to never goes below the path corresponding to . So we can compare sets by comparing the regions below the corresponding paths. Recording these regions can be done using 36 bits, which happily sits inside a machine word. This representation also has the helpful property that taking the complement of a set corresponds to reflecting a path about the up-and-right diagonal, so the representation of the complement of a set can be obtained by swapping certain pairs of bits followed by a bitwise NOT.

The value for was obtained using this new representation and the old algorithm, with one minor tweak.  It’s a bad idea to start with a lexicographically ordered list of sets, as the early decisions will not be meaningful and not lead to much of a reduction in the length of the the lists.  Optimal selection of which pair to decide at each stage is probably a complicated question.  As a compromise I randomised the order of the list at the start of the process, then took the first remaining pair at each stage.

The Haskell source is here.  There are a few more performance tricks to do with the exact bit representation of the sets, which I’m happy to discuss if anything is unclear.

Counting colourings with containers

On the maximum number of integer colourings with forbidden monochromatic sums, Hong Liu, Maryam Sharifzadeh and Katherine Staden

Maryam spoke about this paper at this week’s combinatorics seminar.

The problem is as follows.  Let be the number of -colourings of a subset of with no monochromatic sum .  What is the maximum of over all ?

One possibility is that we take to be sum-free, so that .  The maximum size of a sum-free set of is around , achieved by the set of odd numbers and the interval , so .

Another possibility is to choose sum-free sets and take all colourings of such that the elements of colour are contained in .  There are

such colourings, where is the number of elements in exactly of the .  For example, we might take half of the to be and half to be .  Then the odd numbers greater than are in every set, and the evens greater than and the odds less than are in half of the sets, so the number of colourings is around

For this matches the previous lower bound; for it is larger.

It’s easy to see that this construction cannot improve the bound for : it only provides good colourings, but as elements contributing to are in , which must be sum-free.

What about ?  Now we get good colourings.  We also have that

But since we have

Moreover, if is not tiny then we are some distance off this upper bound, so the only good constructions in this family come from having all the substantially agree.

How can we get matching upper bounds?  If there weren’t very many maximal sum-free sets then we could say that every good colouring arises from a construction like this, and there aren’t too many such constructions to consider.  This is too optimistic, but the argument can be patched up using containers.

The container method is a relatively recent addition to the combinatorial toolset.  For this problem the key fact is that there is a set of subsets of such that

• every sum-free set is contained in some ,
• each is close to sum-free.  Combined with a “sum-removal lemma” this means in particular that it has size not much larger than .

We now consider running the above construction with each an element of .  Since the containers are not themselves sum-free, this will produce some bad colourings.  But because every sum-free set is contained in some element of , every good colouring of a subset of will arise in this way.  And since there are most choices for the sets the number of colourings we produce is at most a factor greater than the biggest single example arising from the construction.

This is the big idea of the paper: it reduces counting colourings to the problem of optimising this one construction.  For the authors are able to solve this new problem, and so the original.

Linear programming duality

The conventional statement of linear programming duality is completely inscrutable.

• Prime: maximise subject to and .
• Dual: minimise subject to and .

If either problem has a finite optimum then so does the other, and the optima agree.

do understand concrete examples.  Suppose we want to pack the maximum number vertex-disjoint copies of a graph into a graph .  In the fractional relaxation, we want to assign each copy of a weight such that the weight of all the copies of at each vertex is at most , and the total weight is as large as possible.  Formally, we want to

maximise subject to and ,

which dualises to

minimise subject to and .

That is, we want to weight vertices as cheaply as possible so that every copy of contains (fractional) vertex.

To get from the prime to the dual, all we had to was change a max to a min, swap the variables indexed by for variables indexed by and flip one inequality.  This is so easy that I never get it wrong when I’m writing on paper or a board!  But I thought for years that I didn’t understand linear programming duality.

(There are some features of this problem that make things particularly easy: the vectors and in the conventional statement both have all their entries equal to , and the matrix is -valued.  This is very often the case for problems coming from combinatorics.  It also matters that I chose not to make explicit that the inequalities should hold for every (or , as appropriate).)

Returning to the general statement, I think I’d be happier with

• Prime: maximise subject to and .
• Dual: minimise subject to and .

My real objection might be to matrix transposes and a tendency to use notation for matrix multiplication just because it’s there.  In this setting a matrix is just a function that takes arguments of two different types ( and or, if you must, and ), and I’d rather label the types explicitly than rely on an arbitrary convention.

Random Structures and Algorithms 2017

A partial, chronologically ordered, list of talks I attended at RSA in Gniezno, Poland. Under construction until the set of things I can remember equals the set of things I’ve written about.

Shagnik Das

A family of subsets of that shatters a -set has at least elements. How many -sets can we shatter with a family of size ? A block construction achieves . (Random is much worse.) Can in fact shatter constant fraction of all -sets. When , identify the ground set with , and colour by for .

Claim. A -set is shattered if and only if it is a basis for .

Proof. First suppose that is a basis. Then for any sequence , there is a unique vector such that . (We are just solving a system of full rank equations mod 2.)

Next suppose that are linearly dependent; that is, that they are contained in a subspace of . Choose orthogonal to . Then for any and any we have , so two of our colourings agree on .

We finish with the observation that random sets of vectors are fairly likely to span : the probability is

Blowing up this colouring gives a construction that works for larger .

At the other end of the scale, we can ask how large a family is required to shatter every -set from . The best known lower bound is , and the best known upper bound is , which comes from a random construction. Closing the gap between these bounds, or derandomising the upper bound, would both be of significant interest.

Andrew McDowell

At the start of his talk in Birmingham earlier this summer, Peter Hegarty played two clips from Terminator in which a creature first dissolved into liquid and dispersed, then later reassembled, stating that it had prompted him to wonder how independent agents can meet up without any communication. Andrew tackled the other half of this question: how can non-communicating agents spread out to occupy distinct vertices of a graph? He was able to analyse some strategies using Markov chains in a clever way.

Tássio Naia

A sufficient condition for embedding an oriented tree on vertices into every tournament on vertices that implies that almost all oriented trees are unavoidable in this sense.

Clique decompositions of multipartite graphs and completion of Latin squares

A Latin square of order is an grid of cells, each of which contains one of distinct symbols, such that no symbol appears twice in any row or column.  There is a natural correspondence between Latin squares of order and partitions of into triangles.  We identify the three vertex classes of with the rows, columns and symbols of the Latin square.  A triangle corresponds to the symbol appearing in the intersection of row and column of the Latin square.  Since each cell contains exactly one symbol, and each symbol appears exactly once in each row and each column, the triangles corresponding to a Latin square do indeed partition .

What about partitions of into ‘s?  Identify the vertex classes of with rows, columns, red symbols and  blue symbols.  Then a corresponds to a red symbol and a blue symbol in the intersection of row and column .  If we look at just the red symbols or just the blue symbols then we see a Latin square.  But we also have the extra property that each pair of red and blue symbol appears in exactly one cell of the grid.  Two Latin squares with this property are called orthogonal.  So pairs of orthgonal Latin squares of order correspond to decompositions of into ‘s.  More generally, a sequence of  mutually orthogonal Latin squares of order  corresponds to a partition of the complete -partite graph on vertex classes of size into ‘s.

Suppose now that we have a partial Latin square of order , that is, a partially filled in grid of cells obeying the rules for a Latin square.  Can it be completed to a Latin square?  In the early 1980s several researchers proved that the answer is yes provided at most cells have been filled in total.  This is best possible, as if we place ‘s and a single on the main diagonal there is no legal cell in which to place the th .  The same example shows that it is not enough to ask only that each row and each column contains only a small number of non-empty cells.  But what if each row, column and symbol has been used at most times?  Can we then complete to a Latin square?  Daykin and Häggkvist conjectured that we can, provided .

What does this mean on the graph side?  Let be a subgraph of obtained by deleting a set of edge-disjoint triangles such that no vertex is in more than triangles.  Then should have a triangle-decomposition if .  In this paper we prove that has a triangle-decomposition provided .

In fact we prove something more general.  The ‘s obtained in this way have the properties that (i) each vertex has the same number of neighbours in each other vertex class and (ii) each vertex sees at least a proportion of the vertices in each other class (a partite minimum degree condition).  We prove that all such graphs have triangle-decompositions when .

The proof is based on that of the similar result for non-partite graphs in Edge decompositions of graphs with high minimum degree.  However, it is not simply a translation of that proof to the partite setting.  In the partite case we not only have to ensure that all of our gadgets can be embedded in partite graphs, we must also take care to ensure a stronger notion of divisibility is preserved throughout our decomposition process.  This makes the proof extremely technical.

We also prove the analogous result for -decompositions of complete -partite graphs, with the less impressive bound .  The connection to mutually orthogonal Latin squares is more complicated for , as the partially filled in cells only correspond to ‘s in the case where each non-empty cell contains one of each symbol, but we still show that there is some such that if each row, column and coloured symbol is used at most times then partial mutually orthogonal Latin squares can be complete.

As for the non-partite case, the bounds on are currently limited by available fractional or approximate decomposition results.  Improvements to these would lead automatically to improvements of the bounds in this paper.

Matchings without Hall’s theorem

In practice matchings are found not by following the proof of Hall’s theorem but by starting with some matching and improving it by finding augmenting paths.  Given a matching in a bipartite graph on vertex classes and , an augmenting path is a path from to such that ever other edge of is an edge of .  Replace by produces a matching with .

Theorem.  Let be a spanning subgraph of .  If (i) or (ii) is -regular, then has a perfect matching.

Proof. Let be a maximal matching in with .

(i) Choose , .  We have and .  Since there is an such that is adjacent to and is adjacent to .  Then is an augmenting path.

(ii) Without loss of generality, is connected.  Form the directed graph on by taking the directed edge  () whenever is an edge of .  Add directed edges arbitrarily to to obtain a -regular digraph , which might contain multiple edges; since is connected we have to add at least one directed edge.  The edge set of decomposes into directed cycles.  Choose a cycle containing at least one new edge of , and let be a maximal sub-path of containing only edges of .  Let , be the start- and endpoints of respectively.  Then we can choose and , whence  is an augmenting path, where is the result of “pulling back” from to , replacing each visit to a in by use of the edge of .

Matchings and minimum degree

A Tale of Two Halls

(Philip) Hall’s theorem.  Let be a bipartite graph on vertex classes , .  Suppose that,  for every , .  Then there is a matching from to .

This is traditionally called Hall’s marriage theorem.  The picture is that the people in are all prepared to marry some subset of the people in .  If some people in are only prepared to marry into some set of people, then we have a problem; but this is the only problem we might have.  There is no room in this picture for the preferences of people in .

Proof. Suppose first that  for all .  Then we can match any element of arbitrarily to a neighbour in and obtain a smaller graph on which Hall’s condition holds, so are done by induction.

Otherwise  for some .  By induction there is a matching from to .  Let .  Then for any we have

hence and Hall’s condition holds on .  So by induction there is a matching from to , which together with the matching from to is a matching from to .

Corollary 1.  Every -regular bipartite graph has a perfect matching.

Proof. Counted with multiplicity, .  But each element of is hit at most times, so in the conventional sense.

Corollary 2. Let be a spanning subgraph of with minimum degree at least .  Then has a perfect matching.

This is very slightly more subtle.

Proof. If there is nothing to check.  Otherwise there is a .  Then and , so .  But for every .

Schrijver proved that a -regular bipartite graph with vertices in each class in fact has at least perfect matchings.  For minimum degree we have the following.

(Marshall) Hall’s theorem.  If each vertex of has degree at least and there is at least one perfect matching then there are at least .

This turns out to be easy if we were paying attention during the proof of (Philip) Hall’s theorem.

Proof. By (Philip) Hall’s theorem the existence of a perfect matching means that (Philip) Hall’s condition holds.  Choose a minimal on which it is tight.  Fix and match it arbitrarily to a neighbour .  (Philip) Hall’s condition still holds on and the minimum degree on this subgraph is at least , so by induction we can find at least perfect matchings.  Since there were at least choices for we have at least perfect matchings from to .  These extend to perfect matchings from to as in the proof of (Philip) Hall’s theorem.

Thanks to Gjergji Zaimi for pointing me to (Marshall) Hall’s paper via MathOverflow.

Block partitions of sequences

Let be a line segment of length broken into pieces of length at most . It’s easy to break into blocks (using the preexisting breakpoints) that differ in length by at most (break at the nearest available point to , etc.).

In the case where each piece has length and the number of pieces isn’t divisible by , we can’t possibly do better than a maximum difference of between blocks.  Is this achievable in general?

In today’s combinatorics seminar Imre Bárány described joint work with Victor Grinberg which says that the answer is yes.

The Namer-Claimer game

Consider the following game played on the integers from to .  In each round Namer names a forbidden distance , then Claimer claims a subset of that does not contain any two integers at distance .  After finitely many rounds, Claimer will have claimed sets that cover the whole of , at which point the game ends.  How many rounds will there be with best play?

I’ve run this question out at a number of workshops and open problems sessions, and haven’t yet heard back about a success.  I’ll explain the known upper and lower bounds below the fold, but encourage you to spend a few minutes thinking about it before taking a look.

Partition regularity and other combinatorial problems

This is the imaginative title of my PhD thesis.  It contains four unrelated pieces of work.  (I was warned off using this phrasing in the thesis itself, where the chapters are instead described as “self-contained”.)

The first and most substantial concerns partition regularity.  It is a coherent presentation of all of the material from Partition regularity in the rationals, Partition regularity with congruence conditions and Partition regularity of a system of De and Hindman.

The remaining three chapters are expanded versions of Maximum hitting for sufficiently large, Random walks on quasirandom graphs and A note on balanced independent sets in the cube.1

1 “A note … ” was fairly described by one of my examiners as a “potboiler”.  It was also my first submitted paper, and completed in my second of three years.  Perhaps this will reassure anybody in the first year of a PhD who is worrying that they have yet to publish.