Open Problem Garden - The Berge-Fulkerson conjecture - Comments

log(n) bound (re: The Berge-Fulkerson conjecture)

Andrew King — Wed, 23 Nov 2011 01:27:51 +0100

The proof is basically the same as Lovász' proof that : It is well-known that the fractional chromatic number of a bridgeless cubic graph is 3. Therefore there is a probability distribution on the perfect matchings of such that given a random matching from this distribution, an edge is hit with probability 1/3.

Now let be and take perfect matchings from this distribution, and consider the probability that an edge is in none of them. This is , so by the union bound, the probability that every edge is in one of the matchings is greater than . Therefore there is some choice of perfect matchings that cover the graph.

Best known upper bound (re: The Berge-Fulkerson conjecture)

Anonymous — Tue, 22 Nov 2011 14:28:20 +0100

I believe that the best known upper bound is given here http://arxiv.org/abs/1111.1871

Reference for log(n) bound (re: The Berge-Fulkerson conjecture)

Emilio Brazil — Sun, 16 Oct 2011 17:28:16 +0200

I'm working with bridgeless cubic graphs and this bound is a good theoretical bound for my purposes. I'd like to know references for this bound.

proof of log(n) (re: The Berge-Fulkerson conjecture)

Anonymous — Fri, 14 Oct 2011 21:51:47 +0200

Do you know a reference for a proof this log(n) boundary? I looked for it in text book but I don't have any clue.

equivalent conjecture (re: The Berge-Fulkerson conjecture)

Louis Esperet — Mon, 04 Apr 2011 18:02:00 +0200

It was recently proved by G Mazzuocolo (The Equivalence of Two Conjectures of Berge and Fulkerson, J. Graph Theory (2010) doi:10.1002/jgt.20545), that Berge-Fulkerson is indeed equivalent to the statement that for any 3-graph G, the edge-set of G can be covered by 5 perfect matchings. This might be worth mentioning it.

Sure (re: The Berge-Fulkerson conjecture)

mdevos — Wed, 04 Mar 2009 14:07:18 +0100

Okay, sure, but the proof that there exists a fractional 3-edge-coloring is either a corollary of Edmond's Theorem or something essentially equivalent to it (such as the approach Seymour uses in his paper on r-graphs). In short, I agree that we are talking about essentially the same argument.

I believe that your first question is open. It is a well known conjecture (elsewhere on this site) that there should be 2 perfect matchings whose intersection does not contain an odd cut.

The second question has been resolved (using Edmond's theorem) by Kaiser, Kral, and Norine and I will add a link to the paper in the reference section.

Matchings and odd cuts (re: The Berge-Fulkerson conjecture)

Andrew King — Mon, 02 Mar 2009 13:56:33 +0100

I like thinking about this problem in terms of fractional colourings. A roughly equivalent proof (to the one you mentioned) is as follows. In a fractional 3-edge-colouring, every matching must be a perfect matching. The weights on the matchings, when divided by 3, give you a probability distribution. If you pick matchings from this distribution, the union bound tells you that with positive probability you hit every edge. This method is powerful enough to prove that the fractional and integer chromatic numbers are always within a factor of of one another.

Here are two even weaker questions:

Is there some such that any bridgeless cubic graph contains perfect matchings whose intersection does not contain an odd cut?

Does every bridgeless cubic graph contain two perfect matchings that together hit no 5-cut 8 or 10 times?

I suspect both of these are open as well.

I believe this is best known (re: The Berge-Fulkerson conjecture)

mdevos — Wed, 25 Feb 2009 18:08:04 +0100

The bound you mention (a consequence of Edmond's perfect matching polytope theorem) is, to my knowledge, the best known lower bound.

Covering with perfect matchings (re: The Berge-Fulkerson conjecture)

Andrew King — Wed, 25 Feb 2009 13:24:28 +0100

It is not hard to show that you can cover the edges of a bridgeless cubic graph with perfect matchings. Is there some smaller-order function that suffices?

The Berge-Fulkerson conjecture

mdevos — Wed, 07 Mar 2007 13:41:22 +0100

Author(s): Berge; Fulkerson

Subject: Graph Theory » Basic G.T. » Matchings

Conjecture If is a bridgeless cubic graph, then there exist 6 perfect matchings of with the property that every edge of is contained in exactly two of .