For questions about matchings in graph theory. A matching on a graph is a set of edges such that no two edges share a common vertex.
5
votes
0answers
194 views
When does a “stable” assignment of buyers into goods exist?
Consider a setting of $n$ buyers and $m$ goods.
We have a value matrix $V\in[0,1]^{n\times m}$ specifying how much each buyer values each good (everything is open information here and there is no ...
2
votes
2answers
86 views
Matching polynomials and Ramanujan graphs
Is it purely coincidental that the same number $2\sqrt{d-1}$ appears in these two following apparently disparate concepts?
A $d-$regular graph is said to be called Ramanujan if its adjacency ...
2
votes
1answer
274 views
Solving assignment problem using Hungarian method vs min cost max flow problem
The traditional solution for the assignment problem is the Hungarian method - it's complexity is O(V^4) or O(V^3) if using Edmonds method.
However, it can also be reduced to a min cost max flow ...
3
votes
1answer
198 views
Polygamous stable marriage/ assignment problem
I'm not sure under which 'algorithm' it falls under, but here is the problem:
I need to match each person to 5 people from the opposite gender (each guy gets 5 girls, each girl gets 5 guys). Not all ...
6
votes
2answers
277 views
Matching number and chromatic number
If $G$ is a (finite) graph, denote with $\mu(G)$ the size of any maximum matching in $G$ (this number is also called the "matching number" of $G$).
For odd integers $n$ we have $n=\chi(K_n) = ...
5
votes
2answers
306 views
Roots of matching polynomial of graph
At the end of this preprint, I make the following conjecture concerning the roots of the matching polynomial:
If a graph $G$ is connected and contains a cycle, then the spectral radius of $G$ ...
3
votes
0answers
93 views
Counting perfect matchings with integrals
Has anyone used the Joni-Rota-Godsil integral formula (see details below) to count perfect matchings of square-grid graphs, Aztec diamond graphs, hexagon-honeycomb graphs, etc.? (Or even just to ...
0
votes
1answer
100 views
Converse of Petersen's 2-Factorization Theorem
Definition: A $k$-factor of a graph is a spanning $k$-regular
subgraph.
Definition: A $k$-factorization of a graph is a partition of the edge
set into $k$-factors.
Petersen's celebrated ...
0
votes
1answer
250 views
Counting matchings in a bipartite matching-covered graph
A graph is called matching-covered if every edge is containd in a perfect matching. (Such graphs are also sometimes called "elementary", e.g. in Chapter 4 of "Matching Theory" by Lovasz & ...
0
votes
1answer
194 views
Good lower bound on matching in bipartite graph
Suppose a bipartite graph $G=(V_1 \cup V_2, E)$ is given, and one is interested in matching vertices $V_1$ to vertices $V_2$. Assume Hall's condition does not hold, so a perfect matching does not ...
1
vote
1answer
86 views
Would a graph with such maximum weighted matchings exist?
Edit Tony's answer is quite nice, but I meant something else. Sorry for editing again, I meant edges.
I am looking for a graph with 3 distinguished edges $xx'$,$yy'$,$zz'$ where ...
6
votes
1answer
389 views
How does this algorithmic proof of Edmonds-Gallai work?
Sorry, this is going to be technical and dirty. I am not looking for a proof of the Edmonds-Gallai structure theorem (I understand two of them, even if they are rather similar); I am trying to ...
3
votes
1answer
252 views
Degree conditions for k-factor
I am looking for a simple degree conditon that ensures the existence of a k-factor in a graph. The k is supposed to be relatively high and I don't mind the condition being a bit strict. Ideally, ...
2
votes
0answers
77 views
A non-distinct system of representative edges.
I have the following problem:
Let $ \mathcal{G} = (G_{i})\_{i} $ be a collection of graphs. I would like to find a "system of representative edges" $ f : \mathcal{G} \rightarrow \bigcup_{i} E(G_{i}) ...
4
votes
0answers
148 views
Bounds on numbers of matchings of given sizes in bipartite graphs
I am interested in the following question:
For which sets ${m_1,\ldots m_k}$ of positive integers do there exist bipartite graphs having exactly $m_i$ matchings of size $i$ for each $1\leq i \leq k$, ...
9
votes
2answers
488 views
Gale-Ryser stable marriage theorem: can we entrust matchmaking to monkeys?
Disclaimer: This is a question I have not done any real research about. I asked it myself some 5 years ago, and back then I had no idea where to start. Now I have some texts on stable matchings lying ...
6
votes
2answers
740 views
Condition on a bipartite graph to have an $m$-factor
This might be the most stupid question I am ever posting here: I am asking for a proof or a counterexample to a problem I proposed on MathLinks long ago.
Let $G$ be a bipartite graph, i. e., a graph ...
