# Tag Info

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 ...
• 10.1k
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 ...
• 17k

### 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,610
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,610
Accepted

• 36.1k

### 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.2k

### 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 ...
• 168k
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$....
• 30.2k

### Solving assignment problem using Hungarian method vs min cost max flow problem

Actually, the two techniques might actually be basically the same. If you read Schrijver's Combinatorial Optimization: Polyhedra and Efficiency, Section 17.2 (where it talks about the Hungarian method)...
• 1,178
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
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 ...
• 7,610

### 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
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,650

• 5,752
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 ...
• 30.2k
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 ...
• 30.2k
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.5k

### Bipartiteness criterion

In "matching theory", by Lovasz and Plummer, I found the following page, which may be helpful:
• 3,521
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})$, ...
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.
• 12.3k

### 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) ...

### 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 ...
• 30.2k

### 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,674
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 ...
• 21.3k
### Minimal cardinality of non-bipartite sub-family of $[\omega]^\omega$
The cardinal $\mathfrak{nb}$ is equal to the reaping number $\mathfrak{r}$. An unsplit family is a collection $\mathcal R$ of infinite subsets of $\omega$ such that there is no set $D \subseteq \omega$...