21
votes
Accepted
Parity and the Axiom of Choice
The Parity Principle follows from the axiom $\mathbf C_2$ (defined below) which is weaker than the Axiom of Choice. I don't know whether the Parity Principle implies $\mathbf C_2$, but that's another ...
- 13.4k
11
votes
Accepted
"König's theorem" for $T_2$-spaces?
What you are calling the "matching number" of $X$ is usually called its Souslin number -- the smallest cardinal bounding the size of any collection of pairwise disjoint open subsets of $X$.
What you ...
- 18.5k
10
votes
Minimum modifications to make a graph bipartite
You want to partition the vertices into two parts and minimizing the number of edges between vertices in the same part. In other words you want to maximize the number of edges between the two parts. ...
- 7,875
7
votes
Accepted
Conjecture about minimal number of edge crossings in complete bipartite graphs
The Electronic Journal of Combinatorics has many Dynamic Surveys one of which is The Graph Crossing Number and its Variants: A Survey by Schaefer which first appeared in 2013 and has been updated as ...
- 7,875
7
votes
Accepted
Discrepancy of random bipartite graphs
The expected degree of a vertex is $k$, which we are keeping fixed as $n\to\infty$. As $n\to\infty$, the vertex degree distribution converges to Poisson($k$). In particular, a proportion roughly $e^{-...
- 3,937
6
votes
Accepted
Connectivity and the minimum degree of bipartite graph
This becomes true at $a = \frac{1}{3}$.
Claim. If $G$ is an $n$-vertex bipartite graph such that $\delta(G) \geq \frac{1}{3}n$, then $\delta(G)=\kappa(G)$.
Proof. Let $(A,B)$ be the bipartition of $G$....
- 32.1k
6
votes
Accepted
Are "ultra-regular" bipartite graphs complete?
The complement of a matching generalises. Take $1<k<|X|$ and identify $Y$ with the $k$-subsets of $X$. Let $R(x)$ be the $k$-subsets containing $x$.
Note that the automorphism group acts as the ...
- 37.7k
5
votes
Applications of Hafnians
In fact Hafnians were introduced by Eduardo Caianiello for a "real-world application", namely to simplify calculations in renormalized quantum field theory. As he writes,
Fermi and Bose statistics ...
- 16.5k
5
votes
Applications of Hafnians
In the context of the fractional quantum Hall effect, the ground state wave function $\Psi$ of electrons in a two-dimensional layer (coordinates $z_n=x_n+iy_n$, $n=1,2,\ldots$) in a strong ...
- 188k
5
votes
Accepted
Is bipartite graph genus bound by $O(\mbox{max deg})$?
The answer is no. Hossein Namazi, Pekka Pankka, Juan Souto showed that expander graphs have genus that is linear in the number of vertices. You can construct bipartite, bounded degree expanders.
- 6,711
5
votes
Hamiltonicity and minimal degree in bipartite graphs
Take any $k\ge 1$ and four disjoint sets of vertices $A,B,C,D$ with $|A|=|D|=k+2$, $|B|=|C|=k$. Completely join $A$ to $B$, $B$ to $C$ and $C$ to $D$. This gives a bipartite graph of minimum degree $...
- 37.7k
5
votes
Accepted
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|}$
Let each vertex $b\in B$ have a can of jam of weight 1, and share it with all neighbours from $A$ equally. There should be a vertex $a\in A$ which got at least $|B|/|A|$ of jam, she got at least $|B|/(...
- 109k
4
votes
Accepted
Hamiltonicity and minimal degree in bipartite graphs
The answer is yes.
One may construct a family of examples of $\Gamma$ with the minimal
degree equal to $2$, as follows.
For even integers $a$ and $b$, start with two even cycles $C_a$ and $C_b$.
...
- 396
4
votes
Minimum planar bipartite graph to cover all perfect matching count
Here is a way to build a balanced, planar, bipartite graph that has exactly $k$ perfect matchings and $O(\log^2 k)$ vertices. First, notice that a ladder graph on $2n$ vertices has exactly $F_n$ ...
- 567
4
votes
Accepted
What is a bipartite hypergraph?
Both (and more...) notions are used.
Coloring hypergraphs is annoying, and so we come up with silly names like “property B” and “rainbow” (to be fair, rainbow is a good name).
This also comes up for ...
- 2,720
4
votes
Conjecture about minimal number of edge crossings in complete bipartite graphs
It is a fascinating conjecture. The following might be a good reference for you: In 1997, Richter & Thomassen showed that
$$\lim_{n\to\infty}cr(K_{n,n})\left(\begin{array}{c} n \\ 2 \end{array}\...
4
votes
The number of elements in {1,2,...,a}.{1,2,...,b}, where $ab=n^2$
Ford's methods provide lower bounds for this "asymmetric" multiplication table problem that match the lower bounds for the standard multiplication table problem.
Define $H(x,y,z) := \#\{n \...
- 1,355
4
votes
Accepted
Succinct polynomial sized representation of balanced bipartite graphs whose perfect matching count is a primorial
Consider the graph $G_k$ with vertex set $$\{u_1, \ldots, u_k, v_1, \ldots, v_k\}$$ and edges $$\{(u_1, v_1), \ldots, (u_1, v_k)\} \cup \{(u_2, v_1), \ldots, (u_k, v_{k-1})\} \cup \{(u_2, v_k), \ldots,...
- 7,226
4
votes
Accepted
"Geodesic coherent" partition of a graph
Pilipczuk and Siebertz proved that every planar graph has such a partition with an even stronger property. Namely, each part $V_i$ is a geodesic path, and the graph obtained by contracting each part ...
- 32.1k
4
votes
Accepted
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
Here is a short proof. Thanks to David Speyer for simplifying an earlier proof of mine (see the comments below).
For each colour $i \in [n]$, let $a_i$ be the number of vertices incident to an edge of ...
- 32.1k
4
votes
Accepted
Algorithm to evaluate "connectedness" of a binary matrix
Similarly to what Daniel Weber suggested in the comments, construct a graph $G$ on columns as vertices and connect every pair of vertices with an edge whenever the corresponding columns has at least ...
- 34.3k
4
votes
Algorithm to evaluate "connectedness" of a binary matrix
You can solve the problem via integer linear programming as follows. Let $$E=\left\{(j_1,j_2)\in[n]\times[n]: j_1 < j_2 \land \lnot \bigwedge_{i=1}^m (a_{ij_1} \lor a_{ij_2})\right\}$$ be the set ...
- 5,429
3
votes
Bipartiteness criterion
In "matching theory", by Lovasz and Plummer, I found the following page, which may be helpful:
- 3,549
3
votes
Accepted
Looking for the name or reference regarding a bipartite graph parameter
The problem is equivalent to the set cover problem and thus NP-hard.
The set formulation you gave is:
Given a finite set $\mathcal{X}$, a family $\mathcal{F} \subseteq \mathcal{P}(\mathcal{X})$, ...
- 638
3
votes
Accepted
Hamiltonian paths in bipartite graphs with 2 sets of "almost" same cardinality
No:
The two degree one vertices must be start and end, but they meet.
- 10.7k
3
votes
Accepted
An variation of an assignment problem in combinatorics: assign items to customers
That is a classical assignment problem, that can also be solved with the Kuhn-Munkres algorithm, for which generalizations to rectangular assignment matrices exist.
- 13.2k
3
votes
What is a bipartite hypergraph?
As Pat Devin wrote there are many notions of "bipartite hypergraphs".
There is a chapter about this topic in the Hypergraph book by Berge (it can be found online as a pdf, look at chapter 5)
...
3
votes
At most one perfect matching of a bipartite graph
The answer to Question I is yes. It is true that if a bipartite graph has a unique perfect matching, then the biadjacency matrix can be permuted to be lower triangular. This was proved by Chris ...
- 32.1k
3
votes
Bipartite graph with exactly one perfect matching
There are indeed no such bipartite graphs. In fact:
Proposition. Let $G=(X,Y,E)$ be a bipartite graph with $n:=|X|=|Y|$ in which the degree of each vertex is at least $2$ and at most $3$. Then, $G$ ...
- 1,769
3
votes
Accepted
Given a polytope $P$ with bipartite edge-graph, if the bipartition classes are equal in size and lie on spheres, is $P$ inscribed?
After some simplifications, I arrived to the following general fact (it can be generalized even further).
Paint the vertices in black and white according to the bipartite structure. We prove that, if ...
- 23.7k
Only top scored, non community-wiki answers of a minimum length are eligible