Questions tagged [bipartite-graphs]
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.
133
questions
2
votes
1
answer
129
views
Bipartite matching with a pairwise constraint
A long time ago I remember seeing a very clever construction for the following problem, but I can't find a reference for it anywhere: suppose I have a bipartite graph $G=(U\cup V, E)$, and the ...
- 5,169
7
votes
2
answers
1k
views
Planar layouts of bipartite graphs
Instances of SAT induce a bipartite graph between clauses vertices and variable vertices, and for planar 3SAT, the resulting bipartite graph is planar.
It would be very convenient if there was a ...
- 4,618
0
votes
0
answers
65
views
Interpretation of $|V|\,|E|$ for bipartite graphs
Background: the question is motivated by a result in statistical mechanics. I am working with a generalized exclusion process with a fixed number of particles $k$ on a finite graph $G'=(V,E')$, which ...
- 145
4
votes
0
answers
116
views
Reorganizational matching
Motivation. My friend works in an organization that is re-organizing itself in the following somewhat laborious way: There are $n$ people currently sitting on $n$ jobs in total (everyone has one job). ...
- 45.5k
2
votes
2
answers
93
views
Real-world datasets for testing the maximum edge bi-clique problem
We have proposed a new approach to solve the maximum edge bi-clique problem, however, we couldn't succeed to find real-world datasets (graph or bipartite graph datasets) to test our approach. Does ...
- 29.8k
1
vote
0
answers
79
views
Diameters of random bipartite graphs
Given two partite sets of vertices $U$ and $V$ of size $n$. Each vertex in $U$ uniformly randomly selects $K$ ($K$ is a constant and $K\ll n$) vertices in $V$ without replacement and connects a ...
- 11
2
votes
1
answer
125
views
Existence of adjacent $a, b$ in a general bipartite graph (with a special degree condition) such that $\frac{\deg(a)}{\deg(b)} \ge \frac{|B|}{|A|}$
Suppose a bipartite graph with two parts $A, B$, for every $b \in B$ we know $\deg(b) \ge 1$.
Prove there exists an adjacent $a \in A, b \in B$ such that $\frac{\deg(a)}{\deg(b)} \ge \frac{|B|}{|A|}$.
- 103k
2
votes
0
answers
137
views
Generalizing Hall's marriage theorem to non-perfect matchings
Let $G = (X, Y, E)$ be bipartite graph such that $|X|=|Y|=n$.
A matching $M \subseteq E$ is a subset of disjoint edges
(i.e., there does not exist a pair of edges $(x, y) \in M$ and $(x', y') \in M$ ...
- 121
3
votes
1
answer
227
views
Are "ultra-regular" bipartite graphs complete?
Let $X, Y$ be non-empty, disjoint sets and let $R\subseteq X\times Y$ be a binary relation. For $x\in X$, we set $R(x) = \{y\in Y: (x,y) \in R\}$ and for $y\in Y$, let $R^{-1}(y) = \{x\in X:(x,y)\in R\...
- 37.2k
1
vote
0
answers
34
views
Tightness of the bounding the operator norm of graph by average degree from below
Let $G = (V,E)$ be a simple graph with adjacency matrix $A$. It is well known that the largest eigenvalue
$\lambda_{1}$ of $A$ is contained within the interval $[d, D]$ where $d$ is the average degree ...
- 381
15
votes
1
answer
1k
views
Parity and the Axiom of Choice
Motivation. The three-dimensional cube can be formalized by $\mathcal P(\{0,1,2\})$ where vertices $x,y\in\mathcal P(\{0,1,2\})$ are connected by an edge if and only if their symmetric difference $x\...
- 11.9k
7
votes
1
answer
794
views
Combinatorial optimization problem for bipartite graphs
Let $G(V_1\cup V_2, E)$ be a simple bipartite graph having $n$ vertices and $m$ edges, such that $|V_1|=|V_2|$ (which implies that $n$ is an even number). Given any node $i \in V_1\cup V_2$, we denote ...
CommunityBot
- 1
3
votes
0
answers
90
views
Number of planar bipartite graphs
How many planar bipartite graphs are there with $m$ vertices of one color and $n$ vertices of the other color?
How many non-isomorphic classes exist?
- 13.7k
2
votes
0
answers
166
views
Ramanujan graphs in Polynomial time
I am a research scholar with a computer science background, currently working on graph theory. I am working on a reduction to prove that a problem is NP-complete. I need to include the Ramanujan graph ...
0
votes
0
answers
30
views
Finding a bipartite graph that contains a specific elements of perfect matchings
I am a physicist who is interested in the applications of graph theory.
I've been studying the bipartite graphs and perfect matching finding problems. I see there are several research works on ...
0
votes
1
answer
507
views
Best algorithm for meeting scheduling optimization so that total number of held meetings is minimized
Problem Description
I want to hold meetings where some given number of people will participate.
They have some vacant dates respectively but they don't have the same date on which all of them can ...
CommunityBot
- 1
4
votes
1
answer
146
views
For every partition of $E(K_{n,n})$ into $n$ colour classes of size $n$, there is a vertex incident to at least $\sqrt{n}$ colours
Given a partition of the edges of $K_{n,n}$ into $n$ colours, where each colour appears exactly $n$ times, prove that there exists a vertex incident to at least $\sqrt{n}$ colours.
- 31.5k
0
votes
1
answer
128
views
Entropy of eigenvectors of (traceless) laplacian of a bipartite graph
This problem is motivated by the edge states that sometimes appear (and sometimes not) at the level of Huckel hamiltonians for $\pi$-conjugated benzenoid hydrocarbons. If this sentence is cryptic, ...
- 4,618
3
votes
1
answer
132
views
"Geodesic coherent" partition of a graph
Let $G=(V,E)$ be a finite undirected graph which we equip with its usual graph geodesic distance $d_G$ making $(G,d_G)$ into a metric space; let $1<\#V<\infty$. For a given $1<N< \#V$ ...
- 31.5k
1
vote
0
answers
73
views
Concavity of expected size of a maximum matching (in a bipartite graph) w.r.t. edge probability
Given a n*n bipartite graph where each edge (between any two nodes on the opposite side) is formed i.i.d. with probability $p$, can we show a concavity result on the expected size of a maximum ...
- 53
4
votes
1
answer
1k
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 ...
CommunityBot
- 1
8
votes
0
answers
128
views
Conceptual explanation for the gap in the spectrum of biregular trees
Ramanujan graphs are defined as $(q+1)$-regular graphs for which all nontrivial eigenvalues of the adjacency operator are contained in the interval
$$[-2\sqrt{q}, 2\sqrt{q}].$$
The reason for this ...
- 3,044
2
votes
1
answer
107
views
Minimal cardinality of non-bipartite sub-family of $[\omega]^\omega$
Let $[\omega]^\omega$ the collection of infinite subsets of $\omega$. We say that $E\subseteq [\omega]^\omega$ is bipartite if there is $d\subseteq \omega$ such that for all $e\in E$ the intersections ...
- 17.4k
4
votes
1
answer
112
views
Given a polytope $P$ with bipartite edge-graph, if the bipartition classes are equal in size and lie on spheres, is $P$ inscribed?
Suppose that $P\subset\Bbb R^n, n\ge 3$ is a (full-dimensional) convex polytope with a bipartite edge-graph $G=(V_1\cup V_2,E)$ (for example, a zonotope). Suppose further that there are concentric ...
- 22.2k
1
vote
1
answer
138
views
Discrepancy of random bipartite graphs (2)
This question is a modification of the one asked here, which turned out to ask for something too strong to be true.
Given $k>0$ and a positive integer $n$, let $X, Y$ be two vertex sets of size $n$ ...
- 3,044
4
votes
0
answers
150
views
Independent sets with few neighbours
[Posted this first at math stackexchange, but it probably fits better here.]
I am looking for references about the following problem.
Given a (connected) bipartite graph $G$, find an independent set $...
- 338
0
votes
1
answer
54
views
Hypergraphs such that all finite subhypergraphs are bipartite
The starting point of this question is the following true statement for graphs:
A simple, undirected graph $G = (V,E)$ is bipartite if and only if for all $E_0\subseteq E$ the graph $(V, E_0)$ is ...
- 103k
3
votes
1
answer
181
views
Discrepancy of random bipartite graphs
This is a crosspost from MathStackExchange (original question).
Fix $k>0$ and let $X, Y$ be two vertex sets of size $n$ a positive integer (we're interested in the limit $n\to \infty$).
Define a ...
- 3,044
3
votes
1
answer
528
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 ...
- 12.7k
-1
votes
1
answer
295
views
Are all subdivisions of bipartite graphs also bipartite?
Excuse the poor quality image, but it illustrates my point well enough. I couldn't find the answer anywhere else online.
- 4,439
1
vote
1
answer
205
views
Sequences that represent different drawing of chords?
In combinatorics, there are special kinds of sequences, in which their terms represent the number of different ways that we can draw chords with some properties.
Actually, my question is motivated by ...
- 373
1
vote
1
answer
164
views
$K_{k,m}$ is $k$-choosable if and only if $m<k^k$
This statement is proved by Vizing and Erdos & Rubin (page 30) independently.
But I cannot find Vizing's paper (It's too old) and Erdos & Rubin's paper only says 'It is easily proved'.
I ...
- 103k
2
votes
1
answer
553
views
Connectivity and the minimum degree of bipartite graph
I want to find a condition on $\delta(G)$ (ex. $\delta(G) \geq an$) that guarantees $\kappa(G)=\delta(G)$ where $\kappa(G)$ is the vertex-connectivity of a bipartite graph $G$, and $\delta(G)$ is the ...
- 31.5k
2
votes
0
answers
60
views
Sum of number of perfect matchings and a constant constuction
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.
Is ...
- 13.7k
6
votes
2
answers
7k
views
How many perfect matchings in a regular bipartite graph?
We have a $d$-regular bipartite graph $G = (X,Y,E)$ with $|X| = |Y| = n$ and $|E| = nd$.
What is an upper bound on the number of perfect matchings of $G$?
- 31.5k
8
votes
0
answers
242
views
Sum of perfect matching construction
Suppose we have two bipartite graphs $G_1$ and $G_2$ with perfect matching count $P_1$ and $P_2$ respectively then their disjoint union gives a bipartite graph with perfect matching $P_1P_2$.
Is ...
- 13.7k
1
vote
1
answer
110
views
Succinct polynomial sized representation of balanced bipartite graphs whose perfect matching count is a primorial
Is there a $P$ time definable sequence of succinct polynomial sized representation of balanced bipartite graphs whose number of perfect matchings is a primorial?
For factorial a complete bipartite ...
- 6,571
5
votes
1
answer
811
views
Bipartite graph with exactly one perfect matching
$\textbf{Problem:}$ Find all bipartite graphs $G[X,Y]$ satisfying the following properties:
$1.$ $|X|=|Y|$, where $|X|\ge 2$ and $|Y|\ge 2$.
$2.$ All vertices have degree three except for two vertices ...
- 1,714
3
votes
1
answer
411
views
The number of elements in {1,2,...,a}.{1,2,...,b}, where $ab=n^2$
Let $A_{a,b}$=$\{pq:p\leq a,q\leq b\}$, where $ab=n^2$ and $n^2$ is fixed.
How large is $A_{a,b}$? Does $A_{a,b}$ attain its lower value when $a=b=n$?
The case when $a=b=n$ is settled by Ford, and a ...
- 139
2
votes
1
answer
186
views
Two from cubic subgraph hardness
The Problem
For a given graph $G$, the cubic subgraph problem asks if there is a subgraph where every vertex has degree 3.
The cubic subgraph problem is NP-hard even in bipartite planar graphs with ...
2
votes
1
answer
371
views
At most one perfect matching of a bipartite graph
I. Given biadjacency matrix $A$ of a bipartite graph on $2n$ vertices having $n$ vertices of either color on the constraints the graph either has
$0$ perfect matchings
$1$ perfect matchings
is it ...
- 31.5k
6
votes
1
answer
239
views
Can we construct a dessin of any genus with a cyclic automorphism group of any order?
We consider a dessin d'enfant $D$ as a bipartite graph $D$ on a complex oriented surface $S$, such that the complement $S \backslash D$ is homotopic to a collection of disks.
Definition: Let an ...
- 28.8k
4
votes
0
answers
99
views
Volume interpretation of number of perfect matchings in bipartite planar graphs
Permanent of biadjacency of bipartite graphs is the number of perfect matchings. In the case of planar graphs we can obtain an orientation with sign changes and get away with computing the determinant ...
- 13.7k
2
votes
0
answers
86
views
Computing bipartite matching of size $k$?
Given a bipartite graph with $n$ vertices on each side and an integer $k$, how can we compute all bipartite matchings of size $k$?
The problem of computing all perfect matchings is #P-complete. But I ...
- 241
1
vote
2
answers
2k
views
Rank adjacency matrix bipartite graph
I am interested to know what kind of characterizations are known of the rank of bipartite graphs $G(n,m)$ ($n$ vertices on one side, $m$ on the other, $n \leq m$).
When is the incidence matrix full ...
- 60.4k
1
vote
0
answers
92
views
Number of extremal $\{0,1\}$ matrices having permanent $1$ property
Is there a function which describes the number of $\{0,1\}^{n\times n}\cap\mathbb Z^{n\times n}$ matrices having permanent $1$?
I think it might be $\mathsf{poly}(n!)$ bounded.
Is there a function ...
- 13.7k
1
vote
1
answer
285
views
Unique bipartite perfect matchings and cycles?
Given a graph $G$ which is bipartite and balanced and has unique perfect matching let $G^{e}$ be $G$ without edge $e$. Let $G\cup G_{\pi,\pi'}$ be union of $G$ and $G_{\pi,\pi'}$ where $G_{\pi,\pi'}$ ...
- 1,042
1
vote
0
answers
109
views
Is there a bipartite graph whose determinant corresponds to number of perfect matchings?
Let $M\in\{0,1\}^{n\times n}$ be a square integer matrix. If we consider $M$ as biadjacency of a balanced bipartite graph on $2n$ vertices having $n$ vertices of color $1$ and $n$ vertices of color $2$...
- 13.7k
1
vote
0
answers
168
views
A query on Galvin's theorem for bipartite graphs
The Galvin's theorem is the generalized version of Dinitz conjecture that states that if the maximum degree of any bipartite graph is $\Delta$, then its edges are colorable properly if each of its ...
- 2,027
1
vote
2
answers
658
views
What is a bipartite hypergraph?
Bipartite graphs are very useful, and I am looking for a generalization of this concept to hypergraphs. I found two different definitions of bipartite hypergraphs:
In the Wikipedia page Hypergraph, a ...
