[math-fun] Pairings in bipartite graphs
I thought of this problem when musing about Wilson's grid problem. Suppose we have a bipartite graph, with N vertices in each of two sets A and B. Further suppose that the graph is regular of degree k. For what values of N and k can we prove that there exists a bijection f between A and B such that a vertex and its partner are always connected by an edge of the original graph? The application to Wilson's problem is that there exists some radius r for which the points of one grid are always within r of at least k points of the other grid. This creates an infinite bipartite graph, and if such graphs always support pairings, that would establish r as an upper bound on the distance in Wilson's problem.
I thought of this problem when musing about Wilson's grid problem.
Suppose we have a bipartite graph, with N vertices in each of two sets A and B. Further suppose that the graph is regular of degree k.
For what values of N and k can we prove that there exists a bijection f between A and B such that a vertex and its partner are always connected by an edge of the original graph?
k >= 1 is a necessary and sufficient condition (proof: Hall's marriage).
The application to Wilson's problem is that there exists some radius r for which the points of one grid are always within r of at least k points of the other grid. This creates an infinite bipartite graph, and if such graphs always support pairings, that would establish r as an upper bound on the distance in Wilson's problem.
No, because you need the graph to be k-regular, not merely have minimum degree k. Sincerely, Adam P. Goucher
<< No, because you need the graph to be k-regular, not merely have minimum degree k. >> Why is this? Hall's theorem makes no mention of regularity (in any sense). WFL On 5/31/15, Adam P. Goucher <apgoucher@gmx.com> wrote:
I thought of this problem when musing about Wilson's grid problem.
Suppose we have a bipartite graph, with N vertices in each of two sets A and B. Further suppose that the graph is regular of degree k.
For what values of N and k can we prove that there exists a bijection f between A and B such that a vertex and its partner are always connected by an edge of the original graph?
k >= 1 is a necessary and sufficient condition (proof: Hall's marriage).
The application to Wilson's problem is that there exists some radius r for which the points of one grid are always within r of at least k points of the other grid. This creates an infinite bipartite graph, and if such graphs always support pairings, that would establish r as an upper bound on the distance in Wilson's problem.
No, because you need the graph to be k-regular, not merely have minimum degree k.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
I was merely commenting that k-regularity of a graph G is a sufficient condition for a matching to exist. Claim: If G is a finite k-regular bipartite graph, and k >= 1, then a matching exists. Proof: Let the vertex classes be X and Y, and let A be an arbitrary subset of X. Then there are k|A| edges incident with vertices in A, so there must be at least k|A|/k = |A| vertices in Y incident with those edges. Hall's condition is satisfied and the result follows. Claim: If G is a (not necessarily finite) k-regular bipartite graph, and 1 <= k < infinity, then a matching exists. Proof: For each edge e in the graph, let P_e denote the proposition `the edge e is involved in the matching'. Then for each vertex v in the graph, let the incident edges be denoted e_1, ..., e_k. Then write down the axiom (e_1 or e_2 or ... or e_k) and the axioms ((not e_i) or (not e_j)) (for all 1 <= i < j <= k). Then any finite subset of the axioms is consistent, due to the result for finite graphs. Hence the theory is consistent and we have a model (which is a matching for the original graph G) by completeness of propositional logic. Sincerely, Adam P. Goucher
Sent: Sunday, May 31, 2015 at 2:12 PM From: "Fred Lunnon" <fred.lunnon@gmail.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Pairings in bipartite graphs
<< No, because you need the graph to be k-regular, not merely have minimum degree k. >>
Why is this? Hall's theorem makes no mention of regularity (in any sense). WFL
On 5/31/15, Adam P. Goucher <apgoucher@gmx.com> wrote:
I thought of this problem when musing about Wilson's grid problem.
Suppose we have a bipartite graph, with N vertices in each of two sets A and B. Further suppose that the graph is regular of degree k.
For what values of N and k can we prove that there exists a bijection f between A and B such that a vertex and its partner are always connected by an edge of the original graph?
k >= 1 is a necessary and sufficient condition (proof: Hall's marriage).
The application to Wilson's problem is that there exists some radius r for which the points of one grid are always within r of at least k points of the other grid. This creates an infinite bipartite graph, and if such graphs always support pairings, that would establish r as an upper bound on the distance in Wilson's problem.
No, because you need the graph to be k-regular, not merely have minimum degree k.
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
On Mon, Jun 1, 2015 at 3:05 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
I was merely commenting that k-regularity of a graph G is a sufficient condition for a matching to exist.
Claim: If G is a (not necessarily finite) k-regular bipartite graph, and 1 <= k < infinity, then a matching exists.
Proof: For each edge e in the graph, let P_e denote the proposition `the edge e is involved in the matching'. Then for each vertex v in the graph, let the incident edges be denoted e_1, ..., e_k. Then write down the axiom (e_1 or e_2 or ... or e_k) and the axioms ((not e_i) or (not e_j)) (for all 1 <= i < j <= k).
Then any finite subset of the axioms is consistent, due to the result for finite graphs.
Why is that? Just because the hypothesis is satisfied for an infinite graph G, that doesn't mean the hypothesis is satisfied for a finite subgraph A of G. There may be edges from vertices in A to vertices not in A, and when you ignore those vertices, then A won't have enough edges to have a matching; it may have no edges at all! This sort of argument works to show, for example, that if any finite subgraph of a graph is colorable with N colors, then so is the entire graph. But I don't think it works here. Hall's theorem is in fact true for infinite graphs, but the proof is more difficult than this. Andy
Sent: Monday, June 01, 2015 at 11:50 AM From: "Andy Latto" <andy.latto@pobox.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Pairings in bipartite graphs
On Mon, Jun 1, 2015 at 3:05 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
I was merely commenting that k-regularity of a graph G is a sufficient condition for a matching to exist.
Claim: If G is a (not necessarily finite) k-regular bipartite graph, and 1 <= k < infinity, then a matching exists.
Proof: For each edge e in the graph, let P_e denote the proposition `the edge e is involved in the matching'. Then for each vertex v in the graph,
(of course I meant each vertex v in the vertex class X)
let the incident edges be denoted e_1, ..., e_k. Then write down the axiom (e_1 or e_2 or ... or e_k) and the axioms ((not e_i) or (not e_j)) (for all 1 <= i < j <= k).
Then any finite subset of the axioms is consistent, due to the result for finite graphs.
Why is that?
Take the induced subgraph consisting of all vertices in A and all of the neighbours thereof, where A is the subset of X consisting of all endpoints of edges mentioned [in the finite subset of the axioms]. Sincerely, Adam P. Goucher
On Mon, Jun 1, 2015 at 7:49 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
Sent: Monday, June 01, 2015 at 11:50 AM From: "Andy Latto" <andy.latto@pobox.com> To: math-fun <math-fun@mailman.xmission.com> Subject: Re: [math-fun] Pairings in bipartite graphs
On Mon, Jun 1, 2015 at 3:05 AM, Adam P. Goucher <apgoucher@gmx.com> wrote:
I was merely commenting that k-regularity of a graph G is a sufficient condition for a matching to exist.
Claim: If G is a (not necessarily finite) k-regular bipartite graph, and 1 <= k < infinity, then a matching exists.
Proof: For each edge e in the graph, let P_e denote the proposition `the edge e is involved in the matching'. Then for each vertex v in the graph,
(of course I meant each vertex v in the vertex class X)
let the incident edges be denoted e_1, ..., e_k. Then write down the axiom (e_1 or e_2 or ... or e_k) and the axioms ((not e_i) or (not e_j)) (for all 1 <= i < j <= k).
Then any finite subset of the axioms is consistent, due to the result for finite graphs.
Why is that?
Take the induced subgraph consisting of all vertices in A and all of the neighbours thereof, where A is the subset of X consisting of all endpoints of edges mentioned [in the finite subset of the axioms].
That induced subgraph is not k-regular, since it contains the neighbors, but not the neighbors of the neighbors. This induced subgraph won't have a perfect matching; it doesn't even have the same number of vertices in the two parts! You can make this work, but the theorem you want to use for finite graphs is not one that says there's a perfect matching, but the related one that says that if given any subset of the first part of the graph, the set of vertices in the second part adjacent to at least one of them is at least as big as the subset, then there is a matching from the first part to a subset of the second part. This gives you, by the compactness argument, a matching from the first half to some subset of the second half, but this matching might not be onto (something that comes for free in the finite case, but not the infinite case. To complete the proof, reverse it, so you have a different matching between all of the second part and a subset of the first part, and then use the Shroeder-Bernstein trick to piece these together to produce a complete matching. Andy
Sincerely,
Adam P. Goucher
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
-- Andy.Latto@pobox.com
Virtually the same question arose in something I was working on just a few years ago. Though I didn't ask it in terms of N and k but just in terms of which regular graphs had such a perfect matching. In this case I meant for "regular" to denote that for any two vertices there is an automorphism of the whole graph taking one to the other in k "cyclically rotated" ways. I got as far as noticing that there is a perfect matching for the 5 regular polyhedra. I'm also curious about the answer for infinite regular graphs (that is, which have a perfect matching). I almost see intuitively that such must exist, but haven't written a proof. Dan
On May 31, 2015, at 5:41 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I thought of this problem when musing about Wilson's grid problem.
Suppose we have a bipartite graph, with N vertices in each of two sets A and B. Further suppose that the graph is regular of degree k.
For what values of N and k can we prove that there exists a bijection f between A and B such that a vertex and its partner are always connected by an edge of the original graph? . . . . . . . . .
Though as I just realized I was not assuming any bipartiteness of the graph. —Dan
On May 31, 2015, at 5:55 AM, Dan Asimov <asimov@msri.org> wrote:
Virtually the same question arose in something I was working on just a few years ago.
Though I didn't ask it in terms of N and k but just in terms of which regular graphs had such a perfect matching.
In this case I meant for "regular" to denote that for any two vertices there is an automorphism of the whole graph taking one to the other in k "cyclically rotated" ways.
I got as far as noticing that there is a perfect matching for the 5 regular polyhedra.
I'm also curious about the answer for infinite regular graphs (that is, which have a perfect matching). I almost see intuitively that such must exist, but haven't written a proof.
Dan
On May 31, 2015, at 5:41 AM, Allan Wechsler <acwacw@gmail.com> wrote:
I thought of this problem when musing about Wilson's grid problem.
Suppose we have a bipartite graph, with N vertices in each of two sets A and B. Further suppose that the graph is regular of degree k.
For what values of N and k can we prove that there exists a bijection f between A and B such that a vertex and its partner are always connected by an edge of the original graph? . . . . . . . . .
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com https://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (5)
-
Adam P. Goucher -
Allan Wechsler -
Andy Latto -
Dan Asimov -
Fred Lunnon