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.
49
questions with no upvoted or accepted answers
8
votes
0
answers
127
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 ...
8
votes
0
answers
241
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 ...
7
votes
0
answers
346
views
Missing count in number of perfect matchings
Let $f(G)$ give number of perfect matchings of a graph $G$.
Denote $\mathcal N_{2n}=\{0,1,2,\dots,n!-1,n!\}$.
Denote collection of all $2n$ vertex balanced bipartite graph to be $\mathcal G_{2n}$.
...
6
votes
0
answers
282
views
Probability that a random multigraph is simple
Question.
Consider a given sequence of $n$ integers $d_1$, $d_2$, $\cdots$, $d_n$ with $\sum_i d_i$ even and $d_i\le n$ for all $i$. One may sample a random multi-graph having this degree sequence ...
6
votes
0
answers
239
views
Dowker and neighborhood complexes: reference wanted
Let $R$ be a 0-1 matrix whose rows or columns are maximal.
Q1. Is there a name for such a matrix (or, e.g., a corresponding relation)?
From 0-1 matrix corresponding to an abstract simplicial ...
6
votes
0
answers
72
views
Moving subsets of bipartite graph
I am dealing with a bipartite graph $G = (L\cup R, E)$. The left and right sets are both assumed to be regular with degrees $d_L$ and $d_R$. Assume $|L| > |R|$ and hence $d_L < d_R$.
Let $S \...
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). ...
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 $...
4
votes
0
answers
78
views
If all 2-faces of a polytope are $2n$-gons, is the edge-graph bipartite?
This question on MSE has not received a satisfying answer. It can be summarized as follows:
Question: Is is true that the edge-graph of a (convex) polytope is bipartite if and only if all 2-faces ...
4
votes
0
answers
98
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 ...
4
votes
0
answers
150
views
Maximality with respect to having no marriage
Let $A,B\neq \emptyset$ be disjoint and suppose $G = (A\cup B, E)$ is bipartite where for all $e\in E$ we have $e\cap A \neq \emptyset\neq e\cap B$. For $a\in A$ we set $N_G(a) = \{b\in B: (\exists e\...
4
votes
0
answers
207
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$, ...
3
votes
0
answers
88
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?
3
votes
0
answers
105
views
Have partition functions of abstract simplicial complexes been examined?
Many complicated probability distributions arising in electrical engineering and machine learning have a simple expression as a sum of products that can also be encoded in a factor graph. The ...
3
votes
0
answers
100
views
Finding large bicliques in random bipartite graph
I want to find a $k$ by $r$ biclique hidden in an $M$ by $N$ random bipartite graph where edges are present with probability $p \in [0,1]$. I am specifically interested in $p \ll 1$, and large values ...
3
votes
0
answers
115
views
Maximum number of $4$-cycles
Suppose we have a balanced bipartite planar maximum degree $k$ graph.
How many such graphs on $2n$ vertices have at most $f(n)$ maximum number of $4$ cycles for a given function $f:\Bbb R^+\...
3
votes
0
answers
75
views
Fraction of graphs with bound on number of perfect matchings
Asymptotically what is the fraction of balanced bipartite graph on $2n$ vertices with at most $cn^{\beta}$ edges having at most $n^\alpha$ perfect matchings for any fixed $c,\alpha>0$ and fixed $\...
2
votes
0
answers
135
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$ ...
2
votes
0
answers
162
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 ...
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 ...
2
votes
0
answers
84
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 ...
2
votes
0
answers
107
views
Counting the number of simple labelled bipartite graphs 𝐺𝑛,𝑚 with 𝑘 edges such that 𝑑1 vertices have degree 1
I have tried to count the number of simple labelled bipartite graphs $G_{n,m}$ with $k$ edges such that $d_1$ vertices have degree 1.
Has this problem been studied?
So far the only related paper I ...
2
votes
0
answers
129
views
How many edges can be in an unbalanced bipartite graph of girth $>6$?
Let $G = (V, E)$ be a bipartite graph with $n, m$ nodes in its bipartition and girth (shortest cycle length) $>6$.
There is a simple counting argument called the Moore Bounds that gives
$$|E| = O\...
2
votes
0
answers
83
views
Statistics of perfect matching and incremental perfect matchings in bipartite planar graphs?
Planar graph permanent can be reduced to determinants and so statistics should be amenable.
Pick a uniformly random bipartite planar graph $G$ with $n$ vertices of each color and choose new additional ...
2
votes
0
answers
175
views
Minimal size of the maximum biclique
We examine a bipartite graph with two sides $R$ and $L$, and denote by $|L|$ and $|R|$ the number of nodes in each side. We know only that each vertex on side $R$ is connected to $k$ vertices on side $...
2
votes
0
answers
122
views
Bipartite Defect in Graphs
This question is inspired by a recent related question.
Given a bipartition $V=B \cup C$ of the vertices of a graph, call an edge $B$-monochromatic (or $C$-monochromatic) if both ends are in $B$ (or ...
2
votes
0
answers
121
views
Regularity for a bipartite graph
Let $G$ be a bipartite graph with $2^n$ left vertices and $2^n$ right vertices such that:
1) degree of every vertex is not greater then $2^t$
2) number of all edges is greater than $2^{n +t - O(\log ...
2
votes
0
answers
340
views
On symmetric difference of $k$-partite perfect matchings
Given a bipartite graph we know that symmetric difference of any two perfect matchings is union of even cycles.
Conversely when is it true that every union of even cycles comes from symmetric ...
2
votes
0
answers
179
views
Characterize the equivalence class of bipartite graphs obtained from each other by elementary row operations on their adjacency matrices
Let $M$ be an $m\times n$ matrix real matrix. Let $G$ be a bipartite graph, with partitions $A$ and $B$, such that $|A|=m$ and $|B|=n$. A node $i\in A$ is linked to a node $j\in B$ if and only if $M_{...
2
votes
0
answers
277
views
Bipartite independence number
Consider a balanced bipartite graph $G=(U,V,E)$, i.e., a bipartite graph with $|U|=|V|$. An independent set $I$ of $G$ is balanced if $|I \cap U| = |I \cap V|$.
The bipartite independence number of $...
2
votes
0
answers
180
views
Details about Kelman's equivalent form of Barnette's conjecture
Barnette's conjecture states that every cubic planar bipartite 3-connected graph admits Hamiltonian cycles.
Kelman claims that this conjecture is equivalent to a stronger one, which imposes some ...
2
votes
0
answers
274
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 ...
1
vote
0
answers
77
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 ...
1
vote
0
answers
33
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 ...
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 ...
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 ...
1
vote
0
answers
108
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$...
1
vote
0
answers
163
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 ...
1
vote
0
answers
46
views
Optimal preprocessing in the Kuhn-Munkres algorithm
The matrix formulation of the Kuhn-Munkres algorithm for solving the Linear Assignment Problem requires a preprocessing in which the minimal values of a line be subtracted from every value in that ...
1
vote
0
answers
24
views
Hadwiger number in vertex collapse in a bipartite graph
If $G=(V,E)$ is a finite graph, let the Hadwiger number $\eta(G)$ equal the largest integer $n$ such that the complete graph $K_n$ is a minor of $G$.
Is there a bipartite graph $G$ on more than $3$ ...
1
vote
0
answers
107
views
Treewidth related properties of a bipartite graph with bounded local crossing number and diameter
If a bipartite degree at most $3$ graph on $O(n^2)$ vertices with diameter at most $O(\log n)$ has property that every edge intersects at most $O(\log n)$ edges on a planar drawing then does any of ...
1
vote
0
answers
138
views
Is the partition of bipartite graphs NP-hard?
I wonder if the following problem is NP-hard. Is it?
Given a bipartite graph $G = (U, V, E)$ with weights $w : E \to \mathbb{R}_+$, find a partition of $U$ into $U_1, U_2$ and nonempty disjoint ...
1
vote
0
answers
62
views
Cut norm and biclique gap?
Given real $\pm1$ matrix $M\in\Bbb R^{n\times m}$ we have that cut-norm is given by $$\|M\|_C=\max_{\mathcal I\subseteq[n],\mathcal J\subseteq[m]}\Big|\sum_{(i,j)\in\mathcal I\times\mathcal J}M_{ij}\...
1
vote
0
answers
166
views
Expected number of perfect matchings in bounded degree bipartite graphs
Consider collection $\mathcal C_{n,n,\Delta}$ of every $2n$ vertex balanced bipartite graph of average degree $\Delta$.
What is the expected number of perfect matching a graph in $\mathcal C_{n,n,\...
1
vote
0
answers
66
views
Largest number of perfect matchings in bounded genus graphs
What is the largest number of perfect matchings a genus $g$ bipartite graph on $n+m$ vertices have?
1
vote
0
answers
108
views
Curve associated to bipartite graph
Given real biadjacency matrix $A\in\{0,1\}^{n\times n}$ of a bipartite graph with rank $r\in[2,n-1]$, denote $A(x)$ to be matrix where $0$ is replaced by $x$ and $1$ by $1-x$. Denote $$p_1(t,x)=Det(tI-...
1
vote
0
answers
114
views
How many extreme maximal cliques are in an n*m 0-1 matrix?
We can use an n*m 0-1 matrix to denote a bipartite graph. Mining maximal bicliques in such matrix is an open problem.
The extreme maximal clique is a special maximal clique. A clique in such matrix ...
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 ...
0
votes
0
answers
29
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 ...