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.

Continue reading "Block partitions of sequences"

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.

Continue reading "The Namer-Claimer game"

Nowhere zero 6-flows

A flow on a graph is an assignment to each edge of of a direction and a non-negative integer (the flow in that edge) such that the flows into and out of each vertex agree.  A flow is nowhere zero if every edge is carrying a positive flow and (confusingly) it is a -flow if the flows on each edge are all less than .  Tutte conjectured that every bridgeless graph has a nowhere zero -flow (so the possible flow values are ).  This is supposed to be a generalisation of the -colour theorem.  Given a plane graph and a proper colouring of its faces by , push flows of value anticlockwise around each face of .  Adding the flows in the obvious way gives a flow on in which each edge has a total flow of in some direction.

Seymour proved that every bridgeless graph has a nowhere zero -flow.  Thomas Bloom and I worked this out at the blackboard, and I want to record the ideas here.  First, a folklore observation that a minimal counterexample must be cubic and -connected.  We will temporarily allow graphs to have loops and multiple edges.

We first show that is -edge-connected.  It is certainly -edge-connected, else there is a bridge.  (If is not even connected then look at a component.)  If it were only -edge-connected then the graph would look like this.

2connected

 

Contract the top cross edge.

2connectedcontracted

If the new graph has a nowhere zero -flow then so will the old one, as the flow in the bottom cross edge tells us how much flow is passing between the left and right blobs at the identified vertices and so the flow the we must put on the edge we contracted.  So is -edge connected.

Next we show that is -regular.  A vertex of degree forces a bridge; a vertex of degree forces the incident edges to have equal flows, so the two edges can be regarded as one.  So suppose there is a vertex of degree at least .

deg4

We want to replace two edges and by a single edge to obtain a smaller graph that is no easier to find a flow for.  The problem is that in doing so we might produce a bridge.

The -edge-connected components of   are connected by single edges in a forest-like fashion.  If any of the leaves of this forest contains only one neighbour of then there is a -edge-cut, so each leaf contains at least two neighbours of .

leaves

If there is a component of the forest with two leaves then choose and to be neighbours of from different leaves of that component.

twoleaves

Otherwise the -edge-connected components of are disconnected from each other.  Now any such component must contain at least neighbours of , else there is a -edge-cut.  If some contains neighbours of then we can choose and to be any two of them.  Otherwise all such contain exactly neighbours of , in which case there must be at least two of them and we can choose and to be neighbours of in different components.

twoislands

So is -regular and -edge-connected.  If is only -connected then there is no flow between -connected components, so one of the components is a smaller graph with no nowhere zero -flow.  If is only -connected then because is so small we can also find a -edge-cut.

Finally, we want to get rid of any loops and multiple edges we might have introduced.  But loops make literally no interesting contribution to flows and double edges all look like

doubleedge

and the total flow on the pair just has to agree with the edges on either side.

We'll also need one piece of magic (see postscript).

Theorem. (Tutte) Given any integer flow of there is a -flow of that agrees with the original flow mod .  (By definition, flows of in one direction and in the other direction agree mod .)

So we only need to worry about keeping things non-zero mod .

The engine of Seymour's proof is the following observation.

Claim. Suppose that where each is a cycle and the number of new edges when we add to is at most .  Then has a -flow which is non-zero outside .  

Write for the set of edges added at the th stage.  We assign flows to in that order.  Assign a flow of in an arbitrary direction to  ; now the edges in have non-zero flow and will never be touched again.  At the next stage, the edges in might already have some flow; but since there are only two possible values for these flows mod .  So there is some choice of flow we can put on to ensure that the flows on are non-zero.  Keep going to obtain the desired -flow, applying Tutte's result as required to bring values back in range.

Finally, we claim that the we are considering have the above form with being a vertex disjoint union of cycles.  Then trivially has a -flow, and times this -flow plus the -flow constructed above is a nowhere-zero -flow on .

For , write for the largest subgraph of that can be obtained as above by adding cycles in turn, using at most two new edges at each stage.  Let be a maximal collection of vertex disjoint cycles in with connected, and let .  We claim that is empty.  If not, then the -connected blocks of are connected in a forest-like fashion; let be one of the leaves.

seymourlast

By -connectedness there are three vertex disjoint paths from to . At most one of these paths travels through ; let and be endpoints of two paths that do not.  These paths must in fact be single edges, as the only other way to get to would be to travel through .  Finally, since is -connected it contains a cycle through and , contradicting the choice of .

Postscript. It turns out that Tutte's result is far from magical; in fact its proof is exactly what it should be.  Obtain a directed graph from by forgetting about the magnitude of flow in each edge (if an edge contains zero flow then delete it).  We claim that every edge is in a directed cycle.

tutte

Indeed, choose a directed edge .  Let be the set of vertices that can be reached by a directed path from and let be the set of vertices that can reach by following a directed path.  If  is not in any directed cycle then and are disjoint and there is no directed path from to .  But then there can be no flow in  , contradicting the definition of .

So as long as there are edges with flow value at least , find a directed cycle containing one of those edges and push a flow of through it in the opposite direction.  The total flow in edges with flow at least strictly decreases, so we eventually obtain a -flow.

Ultrafilter quantifiers and Hindman's theorem

A filter on is a consistent notion of largeness for subsets of . "Largeness" has the following properties.

  • if is large and then is large
  • if and are large then is large
  • the empty set is not large

At most one of and is large; an ultrafilter is a filter which always has an opinion about which it is.

  • either or is large

The usual notation for " is large" is , where is the ultrafilter. This casts ultrafilters as sets, rather than notions of largeness. To bring the notion of largeness to the foreground we can use ultrafilter quantifiers; we write , read "for -most , holds" (where we have also identified with the predicate "is a member of ").

  • if and then
  • if and then

From this point of view says that the set of elements with property is everything, and that the set of elements with property is non-empty. behaves like a mixture of and , with the considerable advantage that logical operations pass through unchanged without having to worry about De Morgan's laws.

Adding ultrafilters

It turns out that the set of ultrafilters on is a model for the Stone–Čech compactification of . is embedded as the set of principal ultrafilters (" is large if and only if "), and the addition on extends to :

(Here should be interpreted as .) But to use this addition with quantifiers all we need to know is that . If you can see that from the first definition then your brain is wired differently from mine.

It is a fact that there exist idempotent ultrafilters, with . Given such a , we can play the following game. Suppose that . Then , so and therefore (by ANDing with the original assertion, and the original assertion with the dummy variable replaced by ). In particular, . But now we can fix a good choice of and repeat the whole process with in place of to get that

Iterating, we eventually obtain an infinite sequence such that holds for every sum of finitely many of the . Together with the observation that whenever is finitely coloured exactly one of the colour classes is -large this proves Hindman's theorem, that we can always find an infinite sequence such that every sum of finitely many terms has the same colour.

A version of this argument with more of the details filled in is on the Tricki.

Piecewise syndetic and van der Waerden

Joel Moreira has just proved that whenever the natural numbers are finitely coloured we can find and such that , and are all the same colour.  He actually proves a much more general result via links to topological dynamics, but he includes a direct proof of this special case assuming only a consequence of van der Waerden's theorem related to piecewise syndetic sets.  I want to record the details here so that I remember them in future.

Syndetic, thick and piecewise syndetic

A set of natural numbers is thick if it contains (arbitrarily) long intervals, and syndetic if it has bounded gaps. It is piecewise syndetic if it has bounded gaps on long intervals (the same bound for each interval).

Piecewise syndetic sets are partition regular:

Claim. If is piecewise syndetic then either or is. (This extends to partitions into more parts by induction.)

Proof. Choose intervals of length on which the gaps in are bounded by . Suppose that is not piecewise syndetic. Then for every there is an such that has a gap more than points wide. So contains an interval of length on which its gaps are bounded by .

It follows that, whenever the natural numbers are finitely coloured, one of the colour classes is piecewise syndetic. So to prove van der Waerden's theorem it would suffice to show that every piecewise syndetic set has long arithmetic progressions. We'll prove this apparent strengthening, assuming van der Waerden's theorem itself.

Claim. If is piecewise syndetic, then it contains long APs.

Proof. If has long intervals with gaps bounded by , then the union of the translates of contains long intervals. So can be viewed as a -colouring of a set of long intervals, hence one of them contains long APs by van der Waerden's theorem. But they are all translates of , so contains long APs.

In fact we can say much more: for every there is a such that the set of such that the AP of length and common difference starting at is contained in is piecewise syndetic. To see this, let be a block of consecutive integers sufficiently long that whenever it is -coloured it contains an AP of length . Pack translates of greedily into the intervals in . For each translate of there is a triple such that contains the AP of length and common difference starting at . Now the set of is piecewise syndetic (it has long intervals with gaps bounded by ). And there are only finitely many choices for (at most ) and (at most ). So by the first claim there is some choice of such that the corresponding are piecewise syndetic. That is, the set is piecewise syndetic. This is Theorem 5.1 in Moreira's paper, with and . The case of general follows by taking .