3
$\begingroup$

This question was motivated by a discussion here and is related to a previous question here.

Let $\kappa$ and $\lambda$ be cardinals such that $0<\lambda\leq \kappa$. Let $G=(A\cup B, E)$ be a bipartite graph with $|A|=\kappa=|B|$ such that every vertex has degree $\lambda$. Does $G$ have a perfect matching?

If so, it would in particular imply that a (non-degenerate) projective plane $(\mathcal{P}, \mathcal{L})$ has a bijection $f:\mathcal{L}\to \mathcal{P}$ such that $f(e)\in e$ for all $e\in \mathcal{L}$ without having to first prove that if $|\mathcal{P}|$ is infinite then $|e|=|\mathcal{P}|$ for all $e\in \mathcal{L}$.

$\endgroup$
1
  • $\begingroup$ I love this generalization of my question, @louisd! $\endgroup$ Nov 6, 2020 at 20:23

1 Answer 1

5
$\begingroup$

I believe this is correct (assuming $\lambda\gt0$).

If $\lambda$ is infinite then each connected component of $G$ has $\lambda$ vertices. Since the components can be handled independently, the problem reduces to the $\kappa=\lambda$ case, which can be done by a straightforward transfinite recursion.

If $\lambda$ is a positive integer, this is a classical theorem. First, the existence of a matching of $A$ into $B$ follows by the usual sort of compactness argument (e.g. Tychonoff's theorem) from the fact that every finite subset of $A$ can be matched into $B$, which is a famous result of graph theory with many names. Then, givem a matching of $A$ into $B$ and a matching of $B$ into $A$, we can get a perfect matching from Banach's mapping theorem, which says: Given any two mappings $f:A\to B$ and $g:B\to A$, there are partitions $A=A_1\cup A_2$ and $B=B_1\cup B_2$ such that $f(A_1)=B_1$ and $g(B_2)=A_2$.

$\endgroup$
3
  • 1
    $\begingroup$ You said "if $\lambda$ is infinite then each connected component of $G$ has $\lambda$ vertices. But this seems to imply that if $\lambda<\kappa$, then $G$ is disconnected. Is that true? $\endgroup$
    – Louis D
    Nov 6, 2020 at 19:47
  • 1
    $\begingroup$ Yes. In a $d$-regular graph, the number of verticeswithin a distance at most $n$ from $v_0$ is at most $1+d+d^2+\cdots+d^n$. If $d$ is infinite then $1+d+d^2+\cdots$=d$. Assuming the axiom of choice, of course. $\endgroup$
    – bof
    Nov 6, 2020 at 20:08
  • 1
    $\begingroup$ As someone who usually only thinks about finite graphs and occasionally countably infinite graphs, I somehow never encountered this fact. While it seems obvious to me now that you point it out, I found this surprising at first. Thanks. $\endgroup$
    – Louis D
    Nov 6, 2020 at 22:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.