question and answer thread.

Quote:

---

Originally posted by souldog
Yes, but you really don't need to proceed by contradiction. What to do about a connected component with a cycle?

---

Well, I guess the cycle case is the most important, since the path pairing would seem to solve the non-cyclic case fairly easy. I am glad to hear that contradiction is not needed, since transfinite ad absurdum always makes me look twice at the problem (as our discussion on intuitionism a few months back probably illustrates :)!). I somehow think that I should go back to the function foundations and the fact that X and Y are disjoint for bipartite graphs, but I am not yet clear on the connections to be made. The functions in cycles seem to have a relationship that I cannot yet formalize or express in words, but it is based on the fact that every element of the domain must map to an element of the range (not 1 to 2, since they are functions, but 2 to 1 is acceptible).

The brain is bending nicely on this one...

Think of the case with a cycle as a flower. The cycle sits at the middle and at each vertex of the cycle a pettle may be connected. (Of course since the vertex may have valency 2, the pettle may have withered and fallen off). If a pettle is there then it will go twisting off to infinity.

hint: In a bipartite graph a cycle has even length.

Yes! Because the cycle must be finite, no matter the component! So the x to y matching is perfect on the cycle. Then each petal has either an x to y or y to x matching with no edges adjacent to the cycle matching, thus giving a perfect matching. I think where I have been confused is that the proof of the cycle with infinite paths (flower-petal) conformation probably requires a contradiction proof as illustrated in the first attempt. But that is a finite ad absurdum, perfectly acceptable by me!

Is this more along the lines you were thinking? Have I missed an important case?

That is exactly it!. Let me note that in the definitions I gave I implicitely assumed that connected components were countable since the path metric is integer valued. i really don't want to consider any other case.

Let me give a formal proof.

To find a perfect matching in B it suffices to consider the connected components one at a time. So we may assume that B is connected.

Suppose B contains no cycles. Fix a vertex v of B. Given any vertex z of B define the cluster around z to be the set
Cz={e in B| e contains z}. Note that since B has minimum valency 2 every cluster contains at least two edges. A cluster, Cz, is called an n-Cluster if z is of distance n from v. Define the distance between an edge and v to be the minimum of the distances between v and the vertices of e. Since B contains no cycles, any n-Cluster with n>0, has a unique edge closest to v.

To construct a perfect matching choose some edge e in the 0-Cluster Cv. Let I0 = {e} and O0 = Cv\{e}. Having defined I0,...,In-1, Let In and On be the smallest subsets of B extending In-1 and On-1, respectively, such that for any n_Cluster Cz:

1) If the edge in Cz closest to v is in In-1 then all the other edges in Cz are in On.

2) If the edge in of Cz closest to v is in On-1, then there is a unique edge of Cz in In and all other edges are in On.

It is easy to see that I= (union In) is a perfect matching in B.

Suppose B contains exactly one cylce C. Since C is a cycle in a bipartite graph, it has even length. Therefore we may devide the edges in C into two sets Ic and Oc such that if and edge is in one of these sets then the two edges adjacent to it are in the other set. So Ic is a perfect matching in C. Let v1,....v2l be the vertices of C. for i = 1,...,2l let Bi be the subgraph of B determined by the set of edges containing a vertex connected to vi by a path disjoint from C. Since Bi intersection Bj is null for i != j, it suffices to find a perfect matching in Bi union C extending Ic for each i = 1,...,2l. So fix i and let Io = Ic and O0 = (Oc union Cvi)\Ic, and proceed as in the first part of the lemma, considering clusters contained in Bi. This construction gives the desired perfect matching in Bi union C. Finally let I = Union Ii i=1,...,2l



Thats it. Now let me ask the next question. I want to tie this into the subject of ammenability.

DEFINITIONS:

Let a group G act on a set X. The set X is said to be G-paradoxical if for some m,n there are disjoint sets A1,...,An,B1,...Bm contained in X and group elements g1,...,gn. h1,...,hm such that both {g1(A1),...,gn(An)} and {h1(B1),...,hn(Bn)} are partitions of X. The set X is said to be (m,n)-paradoxical under G if in addition {A1,...,An,B1,...,Bm} is a partition of X.

The two notions are actuallu equivalent.

More generally, two subsets A and B of X are said to be G-equidecomposable if there are disjoint sets A1,...An partitioning A and disjoint sets B1,..,Bn partitioning B and group elements g1,...,gn such that gi(Ai)=Bi for i = 1,...,n

A Construction:
Suppose X, Y, and C are as in the definition of a bipartite graph and I is a partition of C, <Ca| a in I>. For each a in I Let Ya = union over c in Ca of ran(c). Let YI = union over a in I of (Ya X {a}) this is the cross product. Extend the functions: For each a in I and c in Ca, define c' : X -> Ya X {a} by c'(x) = <c(x), a>. Then let CI = {c': c in C}. Then since YI = Union over c' in CI of ran(c') we have the bipartite graph B(X, YI, CI).

Kind of a funky construction. The first vertex set is just X, while the second vertex set has distinguished (and perhaps duplicated) subset of Y. Note in the case when X and Y are "the same set" and the functions are group elements and so permutations (not partial) then YI will have multiple copies of Y.

END OF DEFINITIONS:

Prove the following

Proposition: Suppose G is a group acting on a set X. Then X is (m,n)-paradoxical under G if and only if there are C={g1,...,gm, h1,...,hn} contained in G and I = {g, h} as in the above definition (i.e. I is index set for partition of C {g1,...,gm} and {h1,..,hn}) such that B(X, XI, CI) contains a perfect matching.

wow alot of writing

You know... from here you could just launch into simplexes, complexes, chains, and homology. Or you could take a dtour into sperner's theorem, sieve algorithms, and more combinatorial results (which have some nice representations as results on 0-1 graphs -- which in many ways have results dual to bipartite graphs). Maybe take a diversion into the Banach-Tarski paradox where group amenability has, in one way, its origins. I don't know, maybe even focus down on the general algebraic results of the actions thus defined...

All I am saying is that this is one of the nicest series of questions to start a tour of modern discrete mathematics I have seen. I mean, truly this should be explored. It beats the work I have in my notebooks for succinctness, and I've been whitling away at just such a foundations for years...

Now to start the actual figuring...

Once you have proven the above proposition you will have basically proven the Banach-Tarski Paradox;) That is where I was heading. I will add that this prop. is pure definition manipulation.

11>4

Quote:

---

Originally posted by solarflare
11>4

---

That's what you think..

Quote:

---

Originally posted by solarflare
11>4

---

Would this be true in certain p-adic fields??

Yes and yes. But I guess this means nobody watches Futurama?? Not that I expected you would...

Quote:

---

Originally posted by solarflare
Yes and yes. But I guess this means nobody watches Futurama?? Not that I expected you would...

---

I do.

Quote:

---

Originally posted by Simon666
I do.

---

First, I must say that I have seen alot of the episodes of Futurama, but I don't recognize the reference, so I appologize deeply for my complete ignorance.

That said, I would like to take a crack at the problem at hand. I think the real problem here for me was I may have been trying at first to over analyze the problem. I think I see now what was meant by it being a defintion type problem. Let me just type out my response for one direction of the iff (bipartite to paradoxical) to see if I'm on the right path. I think if it turns out to be right in this direction, the other direction is about as easy.

You are given G, I, and construct the bipartite graph B(X, YI, CI). I assume here that YI was the intention, since I don't think an XI would have any members of Y, but if this wrong let me know! There is also what seems to be a mixing of X standing for the ull set and standing for the "top" set of the bipartite, but if my interpretation is right, it is fairly clear what is meant.

Assume there exists a perfect matching.

Now look at the functions intoTop and intoBottom of the edges of the perfect partition into, respectively, their X and YI vertices.

Each intoBottom is a member of G since each YI is mapped to by a member of CI of the matching.

Each intoTop is a member of G by existence of inverse in a group.

All vertices of the graph B are covered since it is a perfect matching. Also, this shows all are disjoint.

Thus the existence of a perfect matching implies that B is paradoxical. If this way of looking at things is correct, I think it would be fairly easy to show the other implication...

Yes, that is it! There are some notational problems in my definition. For this construction X and Y are really the same set, but formally distinguished. To make it really explicit let G act on X, Identify X with X x {0} and Y with {0} x X then g( <x,0>) = <0,y> iff g(x) = y, then construct the Bipartite graph from there. I just wanted to avoid this extra confusion.

Let me give an example that will hopefully make it clear what is meant and will be useful.

Example: Consider the action of SO(3), the group of rotations, on the unit sphere S2. Let C = {g1,g2,h1,h2} be four distinct elements of SO(3) and I = {g,h} be the partion (I will identify elements of the partition with the index set) g = {g1,g2} and h = {h1,h2}. Form the bipartite graph B(S2 , S2I, CI).
The first vertex set of B is a copy of S2 while the second vertex set is essentially two copies. Suppose I is a perfect matching in B. let Ig1' , Ig2' , Ih1', Ih2' be the edges in I colored g1', g2', h1', h2' respectively. Let
Ag1 = Proj1(Ig1' ),
Ag2 = Proj1(Ig2' ),
Ah1 = Proj1(Ih1' ),
Ah2 = Proj1(Ih2' ),

Here Proj1 is the projection onto the first vertex set (You were calling this the top set)

The {Ag1,Ag2,Ah1,Ah2}
{g1(Ag1),g2(Ag2)}
{h1(Ah1),h2(Ah2)}

Each give a partition of S2, so if B contains a perfect matching then S2 is (2,2)-paradoxical under rotations.

I hope that example makes it clear what is meant by this construction. You are right that the other direction is just as easy.

I will give you a chance for comments before I ask the next question.

No comments necessary. Once I'd written down the definitions and played with them for a bit, the confusions cleared quite nicely.