Skip to main content
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 ...
bof's user avatar
  • 12.6k
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 ...
Will Brian's user avatar
  • 17.6k
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. ...
John Machacek's user avatar
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 ...
John Machacek's user avatar
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^{-...
James Martin's user avatar
  • 3,797
6 votes
Accepted

On number of perfect matchings

Even if you have $0.999n^2$ edges, as $n \to \infty$ there can't be $0.0001n!$ matchings. For fixed $c, d \in (0,1)$ and large enough $n=n(c,d)$, among the bipartite graphs with $cn!$ perfect ...
Douglas Zare's user avatar
  • 27.8k
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$....
Tony Huynh's user avatar
  • 31.7k
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 ...
Brendan McKay's user avatar
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 $...
Brendan McKay's user avatar
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 ...
Zurab Silagadze's user avatar
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 ...
Carlo Beenakker's user avatar
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.
Ori Gurel-Gurevich's user avatar
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|/(...
Fedor Petrov's user avatar
4 votes
Accepted

What is the densest bipartite graph with unique Hamiltonian cycle?

The OP asks for the densest bipartite graph having a exactly one Hamiltonian cycle. We remark that in Graphs with exactly one Hamiltonian cycle, John Sheehan shows that a graph on $n$ vertices with ...
John Machacek's user avatar
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$. ...
Matjaž Krnc's user avatar
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$ ...
Puck Rombach's user avatar
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 ...
Pat Devlin's user avatar
  • 2,660
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}\...
ZsuzsannaMath's user avatar
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 \...
mathworker21's user avatar
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,...
Peter Taylor's user avatar
  • 6,776
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 ...
Tony Huynh's user avatar
  • 31.7k
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 ...
Tony Huynh's user avatar
  • 31.7k
3 votes

Bipartiteness criterion

In "matching theory", by Lovasz and Plummer, I found the following page, which may be helpful:
Erel Segal-Halevi's user avatar
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.
Moritz Firsching's user avatar
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})$, ...
Janne Kokkala's user avatar
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.
Manfred Weis's user avatar
  • 12.8k
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) ...
Isabel Beckenbach's user avatar
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 ...
Tony Huynh's user avatar
  • 31.7k
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$ ...
Algernon's user avatar
  • 1,714
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 ...
Ilya Bogdanov's user avatar

Only top scored, non community-wiki answers of a minimum length are eligible