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$ Commented 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
    Commented 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
    Commented 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
    Commented Nov 6, 2020 at 22:39

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .