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.
3
votes
1answer
211 views
Minimum planar bipartite graph to cover all perfect matching count
Given set $\mathcal T_n=\{0,1,\dots,2^n-1\}$ what is the minimum number of vertices $2m$ needed in a planar bipartite balanced graph such that at every $i\in\mathcal T_n$ there is a graph $G\in\...
2
votes
0answers
34 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 ...
5
votes
1answer
152 views
“König's theorem” for $T_2$-spaces?
For any topological space $(X,\tau)$ we define a matching to be a collection of non-empty and pairwise disjoint open sets. We define the matching number $\nu(X,\tau)$ to be the smallest cardinal $\...
3
votes
0answers
62 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 ...
0
votes
0answers
53 views
Hopcroft-Karp Algorithm
I'm studying Hopcroft-Karp algorithm in bipartite graph.
I can understand the theorems about the algorithm, but I want to find a more specific example.
Can I find a bipartite graph that iterates an ...
1
vote
1answer
95 views
An variation of an assignment problem in combinatorics: assign items to customers
Suppose we want to assign $n$ items to $m$ customers ($n \geq m$). Each assignment of an item $i$ to a customer $j$ has an associated cost $c(i,j)$. Find an assignment that maximizes the total cost. ...
-1
votes
2answers
69 views
On a condition concerning the number of neighbors in bipartite graphs
For any undirected simple graph $G=(V,E)$ we define for $v\in V$ the set $N(v) = \{w\in V: \{v,w\}\in E\}$.
Suppose $A, B$ are finite, disjoint sets, and $G = (A\cup B, E)$ is a bipartite graph with ...
1
vote
0answers
104 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 ...
0
votes
1answer
77 views
Maximum partition of bipartite graph
Let $G = (U, V, E)$ be a bipartite graph. Let $w: E \to \mathbb{R}$ be a weight function on the edge set $E$. Given subsets $U_1,\ldots, U_k \subset U, U_i\cap U_j = \emptyset$ and a partition $V_1,\...
1
vote
1answer
100 views
Algorithm to find a $k$-partite graph
Is there any algorithm which finds any $k$-partite graph of a given graph which is known to be a $k$-partite graph?
For example, you are given a graph $G$ with vertices $V$ and edges $E$, and you ...
6
votes
0answers
123 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 ...
4
votes
1answer
393 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 ...
5
votes
3answers
148 views
How many $40$-vertex cubic bipartite graphs have determinant $\pm 3$?
To get some feel for the size of a particular computation, I would like to know the approximate number of (pairwise-nonisomorphic) cubic bipartite graphs on $40$ vertices whose bipartite adjacency ...
2
votes
1answer
90 views
Existence of bipartite subgraphs satisfying degree and edge cardinality constraints
How can we prove the following conjecture?
Given any simple unweighted bipartite graph $G(V_1, V_2, E)$, there always exists a subgraph $G'(V_1, V_2, E')$ of $G$ such that the two following ...
0
votes
1answer
48 views
Canonical form for a bipartite graph
I have a bipartite graph, including V1 and V2 vertices, and I would like to convert it to a canonical form. One simple method is converting this graph to a general graph by expanding its adjacency ...
1
vote
2answers
136 views
Hamiltonicity and minimal degree in bipartite graphs
Given an integer $k>1$, is there a connected bipartite graph $\Gamma = (A, B, E)$ where $A\cap B = \emptyset$ and $E \subseteq \big\{\{a, b\}:a\in A, b\in B\big\}$ such that
$|A| = |B|$,
$\text{...
0
votes
3answers
186 views
Hamiltonian paths in bipartite graphs with 2 sets of “almost” same cardinality
Suppose we have two finite disjoint sets $A, B \neq \emptyset$ such that $|A|$ and $|B|$ differ by at most $1$, and let $\Gamma = (A\cup B, E)$ where $E\subseteq \big\{\{a,b\}: a\in A, b\in B\big\}$ ...
7
votes
1answer
322 views
Graph to Bipartite conversion preserving number of perfect matchings
Given a graph $G$ on $n$ vertices is there a technique to convert to a balanced bipartite graph $B$ with $O(n^c)$ vertices at some fixed $0<c$ in $O(n^{c'})$ time at some fixed $0<c'$ such that ...
2
votes
0answers
136 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
1answer
129 views
Minimal size of the maximal 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 node on side $R$ is connected to $k$ nodes on side $L$, ...
5
votes
0answers
64 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 \...
3
votes
1answer
103 views
Is bipartite graph genus bound by $O(\mbox{max deg})$?
We know that planar graphs have $O(1)$ degree.
We know balanced (each color has same number of vertices) complete bipartite graphs have genus $O(n^2)$.
If maximum and average degree are $O(n^\...
6
votes
1answer
63 views
Looking for the name or reference regarding a bipartite graph parameter
I'm writing a paper about a math puzzle and the thing I'm studying ends up equivalent to finding the following parameter of a bipartite graph G with parts X and Y:
The largest $k$ such that any $k$ ...
3
votes
2answers
448 views
Applications of Hafnians
I am learning about Hafnians but I am struggling to find real-world applications of them. I understand the applications of determinants, permanents, and even pfaffians but I am at a loss for Hafnians. ...
1
vote
0answers
56 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}\...
4
votes
0answers
132 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\...
-1
votes
1answer
166 views
Marriages in infinite bipartite graphs with many neighbors
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\...
2
votes
1answer
84 views
Minimum number of edges to add in order to have a biclique cover
Given a bipartite graph G and a number N, what's the minimum number of edges I have to add to G in order to be able to cover the resulting graph with no more than N complete bipartite subgraphs?
For ...
1
vote
2answers
364 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 ...
2
votes
0answers
78 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 ...
3
votes
0answers
72 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
1answer
113 views
Matching in a bipartite graph that saturates all vertices
Let $G=(S,T;E)$ be a bipartite graph without isolated vertices.
For every edge $e\in E$, e $=$ $st$ $($ s $\in S$, $ t\in T$) happens the inequality $dG(s)$ $>=$ $dG(t)$.
Prove that in $G$ ...
5
votes
1answer
164 views
Number of bipartite graphs with a neighborhood property
Consider a bipartite graph of order $2n$ with equal bipartitions $C_1$ and $C_2$, where, $$C_i = \{v_{i,1}, v_{i,2}, v_{i,3} \dots v_{i,n}\}; i = 1, 2.$$
Given two vertices $v_{i,p}$ and $v_{i,q}$, $...
2
votes
2answers
522 views
Maximum number of edges in bipartite graph without cycles of length 4
Let $ex(n,H)$ denote the maximum number of edges of a graph on $n$ vertices not containing a copy of $H$. Let $ex(n,m,H)$ denote the maximum number of edges of a bipartite graph with parts' sizes $m$ ...
0
votes
1answer
123 views
Minimum modifications to make a graph bipartite
Let's say I have a graph that is not bipartite. Let's say it is colored red and black and there are some conflicts where two vertices of the same color share an edge. I can introduce a new vertex ...
7
votes
0answers
280 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}$.
...
3
votes
1answer
177 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 ...
3
votes
0answers
102 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^+\...
1
vote
1answer
118 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$.
1
vote
0answers
84 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,\...
4
votes
3answers
326 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 ...
2
votes
0answers
101 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 ...
1
vote
0answers
56 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?
3
votes
0answers
70 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 $\...
1
vote
0answers
183 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
1answer
140 views
A graph assignment problem
Consider bipartite graph with vertex set $V_1\cup V_2$ where $|V_1|=\frac{n(n-1)}2$ and $|V_2|=n$. The vertices in $V_1$ all have degree $2$ and connected to two vertices in $V_2$. The vertices in $...
2
votes
1answer
273 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 ...
6
votes
2answers
302 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 of ...
7
votes
1answer
407 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 ...
1
vote
0answers
102 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-...
