arXiv / 2023

Random perfect matchings in regular graphs

Bertille Granet, Felix Joos

Graph LearningML Systems

We prove that in all regular robust expanders $G$ every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.

0 citations0 influential

Full paper

Read the original paper

Open PDF Source page

Learning resources

arXiv PDFPDF arXiv abstract pagearXiv Google Scholar referencesGoogle Scholar Papers with Code searchPapers with Code YouTube explanationsYouTube

Reading state

Discuss in ChatGPT

Uses your own ChatGPT account. The paper context is copied into a tutor prompt before ChatGPT opens.

Preview prompt

You are my AI/ML research paper instructor. I want to deeply understand the paper below.

First, teach it in layers:
1. One-paragraph intuition.
2. Problem statement and why it mattered.
3. Key method, architecture, or algorithm.
4. Important equations or mechanisms, explained intuitively.
5. Experiments and evidence.
6. Limitations, assumptions, and failure modes.
7. How this paper influenced later AI/ML/Deep Learning/GenAI work.
8. A 30-minute study plan with checkpoints.
9. Quiz me with 5 questions and wait for my answers.

When something is not available in the attached context, say what is missing and infer carefully.

### Paper attached as context
Title: Random perfect matchings in regular graphs
Authors: Bertille Granet, Felix Joos
Year: 2023
Venue: arXiv
Categories: Graph Learning, ML Systems
Citations: 0
Paper URL: https://arxiv.org/abs/2301.10131v2
Open PDF: https://arxiv.org/pdf/2301.10131v2

Abstract:
We prove that in all regular robust expanders $G$ every edge is asymptotically equally likely contained in a uniformly chosen perfect matching $M$. We also show that given any fixed matching or spanning regular graph $N$ in $G$, the random variable $|M\cap E(N)|$ is approximately Poisson distributed. This in particular confirms a conjecture and a question due to Spiro and Surya, and complements results due to Kahn and Kim who proved that in a regular graph every vertex is asymptotically equally likely contained in a uniformly chosen matching. Our proofs rely on the switching method and the fact that simple random walks mix rapidly in robust expanders.

Learning resources:
- PDF: arXiv PDF (https://arxiv.org/pdf/2301.10131v2)
- arXiv: arXiv abstract page (https://arxiv.org/abs/2301.10131v2)
- Google Scholar: Google Scholar references (https://scholar.google.com/scholar?q=Random%20perfect%20matchings%20in%20regular%20graphs)
- Papers with Code: Papers with Code search (https://paperswithcode.com/search?q=Random%20perfect%20matchings%20in%20regular%20graphs)
- YouTube: YouTube explanations (https://www.youtube.com/results?search_query=Random%20perfect%20matchings%20in%20regular%20graphs+paper+explained)