All Questions
Tagged with matching-theory reference-request
10 questions
3
votes
1
answer
140
views
Generalizations of a theorem of Edmonds/Tutte on existence of a perfect matching in a graphs
It is well known that for a bipartite graph $G$ with bi-adjacency matrix $A$, then $\det A \neq 0$ (as a polynomial) iff $G$ has a perfect matching (there is a similar result for general graphs with ...
- 129
1
vote
1
answer
152
views
Hall theorem with non-saturating matching
Hall's marriage theorem states that given a bipartite graph $G=(X+Y,E)$, if there is no $X$-saturating matching, there there exists $W\subseteq X$ such that $|W|>|N_G(W)|$.
Is the following ...
- 11
1
vote
0
answers
81
views
Matchings in infinite, not necessarily bipartite, graphs
Aharoni, Nash-Williams, and Shelah have extended the famous marriage theorem for finite bipartite graphs due to Hall to arbitrary graphs.
Is there a similar generalization of Tutte's theorem on ...
- 48.8k
1
vote
1
answer
311
views
Tutte's Reduction of Minimum Weight d-Factors to Matching
I am currently interested in minimum weight regular d-spanners (i.e. d-factors) of complete graphs. When searching the internet for related articles, I came across this one, which is concerned with ...
- 13.2k
1
vote
0
answers
77
views
Non-adjacent Pair of Edges with Minimal Weight Sum
Given an weighted, undirected Graph $G(V,E)$ without loops or parallel edges,
what is the complexity of determining a pair of non-adjacent edges, whose sum of weights is w.l.o.g. minimal?
is that ...
- 13.2k
3
votes
1
answer
107
views
Probabilistic many-to-one matching
Let $p<1$ be a constant. Consider two sets $A,B$ with $n$ and $nf(n)$ vertices, respectively, where $f(n)$ is an integer. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears ...
- 239
2
votes
2
answers
353
views
Matching with probabilistic edges
Let $p<1$ be a constant. Consider two sets $A,B$, each with $n$ vertices. For each pair $(a,b)\in A\times B$, the edge between $a$ and $b$ appears with probability $p$, independently of the ...
- 239
2
votes
0
answers
78
views
Maximum cardinality general factor of a graph
Given a graph $G=(V,E)$ and a set of integers $B(v)$ associated to each vertex, a general factor of $G$ is a set of edges $F\subseteq E$ such that the degree of each vertex $v\in V$ in the graph $(V, ...
30
votes
2
answers
3k
views
An unfair marriage lemma
I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem:
Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...
- 32.4k
5
votes
1
answer
302
views
Reference sought for Conway's observation on stable matchings
Looking for a reference on the observation that the set of stable matchings form a distributive lattice. This is attributed to Conway by Knuth in "Marriages Stables" but I would like an explicit ...
- 51