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

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

9
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
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
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^{-...

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

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.

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 $...

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

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

5
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$....

4
votes

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

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$.
...

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

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$ ...

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

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 \...

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,...

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

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

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.

3
votes

### Bipartiteness criterion

In "matching theory", by Lovasz and Plummer, I found the following page, which may be helpful:

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})$, ...

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.

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

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$ ...

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

3
votes

Accepted

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

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

#### Related Tags

bipartite-graphs × 124graph-theory × 90

co.combinatorics × 49

perfect-matchings × 24

matching-theory × 18

graph-colorings × 10

algorithms × 9

enumerative-combinatorics × 7

combinatorial-optimization × 7

random-graphs × 7

reference-request × 6

extremal-graph-theory × 6

permanent × 6

pr.probability × 5

linear-algebra × 5

computational-complexity × 5

hypergraph × 5

set-theory × 4

matrices × 4

determinants × 4

spectral-graph-theory × 4

hamiltonian-graphs × 4

planar-graphs × 4

nt.number-theory × 3

probability-distributions × 3