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