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.
86
questions
3
votes
0answers
159 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 ...
1
vote
2answers
87 views
One part of a bipartite graph has max degree 3. Partition the other part to 3 ~equal subsets s.t. just a fraction of first part see all 3 subsets
Let $d \gg 1$. Let $G:=(U, V, E)$ be some bipartite graph such that deg$(u) \le d$ for all $u\in U$ and deg$(v) \le 3$ for all $v \in V$.
Now, is it possible to color vertices in $U$ with 3 colors ...
4
votes
0answers
43 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 ...
2
votes
2answers
75 views
Number of subgraphs with matching of size $n$ for a complete bipartite graph
Say we have a $K_{n,n}$ bipartite graph (i.e. a complete bipartite graph with $n$ nodes on each side). We induce a subgraph by deleting some subset of edges. There are $2^{n^2}$ possible subgraphs. ...
1
vote
0answers
16 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$ ...
2
votes
0answers
34 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\...
1
vote
0answers
34 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 ...
3
votes
1answer
56 views
Partitioning vertex set to maximize weights of inter-class edges?
An interesting problem has come up in my work, and I haven't quite been able to find references to it so I thought I'd ask here.
Suppose we have some complete, weighted graph with vertex set $V$. Is ...
1
vote
1answer
63 views
Maximum number of perfect matchings in a graph of genus $g$ balanced $k$-partite graph
What is the maximum number of perfect matchings a genus $g$ balanced $k$-partite graph (number of vertices for each color in all possible $k$-colorings is within a difference of $1$) can have? I am ...
2
votes
0answers
49 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 ...
3
votes
1answer
245 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
43 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
168 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
74 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 ...
1
vote
1answer
107 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
70 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
118 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
95 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
329 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
168 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
493 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
184 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
112 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
62 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
189 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{...
1
vote
3answers
403 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
471 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
157 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 $...
3
votes
1answer
137 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
66 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
127 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
69 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
624 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
57 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
138 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
259 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
87 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
711 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
97 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
83 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
121 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
197 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
738 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
432 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
329 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
190 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
108 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
119 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
127 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,\...
5
votes
3answers
512 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 ...
