# Tagged Questions

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that no two vertices in the same set are adjacent.

634 views

### Gale-Shapley 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 ...
351 views

### When does a `distinguished matching' exist?

Suppose I have a bipartite graph on a pair of vertex sets $X$ and $Y$. Definition: A distinguished matching is a subset $DX\subseteq X$ and a subset $DY\subseteq Y$ such that: For all $y\in Y$, ...
1k 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 ...
281 views

### extremal bipartite graph

I'm facing the following question: Given a bipartite graph $G = (L \cup R, E)$. Let $n = |L|$, $m = |R|$, and a parameter $k \in \mathbb{N}$, $n > m > k$. What is a minimal possible number ...
137 views

### Analysis of the Laplacian of a random bipartite graph

My analysis of an engineering problem reduced to analysis of the Laplacian of a (random) bipartite graph. There are a few particular questions I am interested in, but not sure which direction to take ...
160 views

### Does high min degree and high odd girth imply near bipartiteness?

Say $G$ has odd girth at least $k$ and min degree $2n/k$. There is a classical result by Andrasfai, Erdos, and Sos that says that $G$ is bipartite. (Odd girth is the length of the shortest odd cycle ...
196 views

### Bipartiteness criterion

A graph is bipartite if and only if it does not contain odd cycles. Is there a similar criterion for hypergraphs? (A hypergraph is called bipartite if its vertices can be colored in two colors so that ...
165 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$, ...
487 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 ...
113 views

### What is the densest bipartite graph with unique Hamiltonian cycle?

In a prior post regarding perfect matching, it was stated that the densest graph with a unique perfect matching cannot have more than $n^2$ edges, if graph has $2n$ vertices. Analogously, what is the ...
660 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 ...
63 views

560 views

### bipartite graph coloring

Hi, I don't know much about graph theory so I would need to know if the following problem has a positive answer or a reference. There is a bipartite graph G with the two vertex sets V1, V2. Each ...
238 views

### Bipartite graphs with prescribed Matching $M$ and genus $g$.

Let $B_{n,n}$ be a bipartite graph on $2n$ vertices with $n$ vertices of each color. Given two integers $g$ and $M$, construct the smallest genus $g$ $B_{n,n}$ with exactly $M$ matchings. My first ...
333 views

### Obstructions to genus $g+1$ bipartite graph having genus $g$

Say $B_{n,n}$ is a bipartite graph on $2n$ vertices with each color assigned to $n$ vertices. Say I know $g \le \operatorname{genus}(B_{n,n}) \le g+1$. What obstructions prevent $B_{n,n}$ from being ...
115 views

### Bipartite dimension of an almost crown graph

A crown graph is a complete bipartite graph from which a perfect matching has been removed. The bipartite dimension of a graph is the minimum number of complete bipartite subgraphs needed to cover ...
133 views

### Searching for equal subsets in a bipartite graph

Let $(U,V)$ be a finite bipartite graph of two parts $U$ and $V$. For any subset $u\subset U$ define the image $Im(u)$ in $V$ consisting of all vertices of $V$ connected to at least one vertex of $u$. ...
379 views

### Finding maximal k-degenerate subgraphs

Given a graph $G$, let $H$ be a $k$-degenerate (not necessarily induced) subgraph of maximal size. Are there any known lower bounds on $|E(H)|$ for particular classes of $G$ and values of $k$? I've ...
85 views

138 views

### Minimum number of perfect matchings in a regular bipartite graph

Is there a lower bound on the number of perfect matchings in a $k$-regular bipartite graph? One can use Hall's marriage theorem and induction on $k$ to derive the lower bound of $k$. I can't come up ...
90 views

179 views

### Structure of almost all bipartite graphs

I am studying some properties related to bipartite graphs and it would be useful for me to know if there is anything known about the structure of almost all bipartite graphs. For example, is it true ...
132 views

### On number of perfect matchings

Consider $2n$ vertex balanced bipartite graph. If total number of edges is $n^2$ then we have $n!$ perfect matchings. Fix $c\in(0,\frac12)$ and consider collection of $2n$ vertex balanced bipartite ...
104 views

### Counting bounded genus non-isomorphic graphs

What is the number of non-isomorphic $2n$ vertex balanced bipartite graphs of degree at most $d$ and genus $g$? I am most interested in $d\leq3$ and $g=0$.
367 views

### Expected matching in a bipartite graph

Consider a random bipartite graph constructed on vertex classes of size $n$ with each edge present independently with probability $p$. How could I go about calculating the size of the expected ...
145 views

### Sequences that represent different drawing of chords?

In combinatorics there are there are special kind of sequences, in which their terms represent the number of different ways that we can draw chords with some properties. Actually my question is ...
504 views

### Similarity measure between 2 bi-partite graph.

Hello there, i need to solve this problem: I have 2 different bi-partite weighted graph, g1 and g2 and i would like to measure their similarity, g1 and g2 may have different number of vertex and edges ...