# Questions tagged [permanent]

The permanent tag has no usage guidance.

44
questions

**2**

votes

**0**answers

85 views

### Mod $2$ of $\#PM(G)$ for arbitrary G?

Permanent mod $2$ of biadjacency gives polynomial time algorithm of $\#PM(G)\mod 2$ of perfect matchings of bipartite graph. Is there a similar efficient strategy for general graphs?

**1**

vote

**0**answers

44 views

### Planar graphs with perfect matching count in linear time?

We can find Pfaffian orientation and take determinant to compute permanent in $O(n^\omega)$ time where $\omega$ is exponent of matrix multiplication.
We know that permanent of $O(n)$ vertex planar ...

**0**

votes

**0**answers

34 views

### Biadjacency permanent upper bound in terms of genus of graph?

Take $M$ to be biadjacency of a planar balanced bipartite on $2n$ vertices with genus $g$.
Is it true for every $\epsilon\in(0,1)$ there is a $c_\epsilon>0$ such that $$\log\log(permanent(M))\leq\...

**0**

votes

**0**answers

10 views

### On statistics of perfect matchings between planar $4$ colorable and planar $3$ colorable

Does the mean for number of perfect matchings of random graphs that are planar and $3$ colorable much higher than graphs that are planar are not $3$ colorable?
Does a planar graph if $3$ colorable ...

**1**

vote

**1**answer

51 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

**0**answers

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

**6**

votes

**0**answers

227 views

### Is the permanent of the matrix $[(\frac{i+j}{2n+1})]_{0\le i,j\le n}$ always positive?

Recall that the permanent of an $n\times n$ matrix $A=[a_{i,j}]_{1\le i,j\le n}$ is defined by
$$\operatorname{per}A=\sum_{\sigma\in S_n}\prod_{i=1}^n a_{i,\sigma(i)}.$$
In 2004, R. Chapman [Acta ...

**2**

votes

**0**answers

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

**9**

votes

**0**answers

196 views

### On the permanent $\text{per}[i^{j-1}]_{1\le i,j\le p-1}$ modulo $p^2$

Let $p$ be an odd prime. It is well-known that
$$\det[i^{j-1}]_{1\le i,j\le p-1}=\prod_{1\le i<j\le p-1}(j-i)\not\equiv0\pmod p.$$
I'm curious about the behavior of the permanent $\text{per}[i^{j-...

**3**

votes

**2**answers

307 views

### On the sum $\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$

Motivated by Question 316142 of mine, I consider the new sum
$$S(n):=\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$$
for any positive integer $n$, where $S_n$ is the symmetric group of all the ...

**7**

votes

**3**answers

327 views

### Distribution of sum of two permutation matrices

Determinant and permanent of sum of two $n\times n$ permutation matrices can be arbitrarily different.
What is the distribution of determinant of sum and difference of two $n\times n$ permutation ...

**3**

votes

**0**answers

48 views

### Rank relation to maximum subpermanent and subdeterminant?

Given a $\pm1$ matrix $M$ of rank $r$ let the largest subdeterminant be $d$ and let the largest subpermanent be $p$.
Are there relations/bounds that connect $r$, $d$ and $p$?
Are there geometric and ...

**3**

votes

**1**answer

119 views

### Multi-dimensional permanent

Is there a particularly natural / "correct" way of generalizing permanents to tensors? (I mean of course, 'square' tensors.) There seem to be very few resources on the matter. There needs to be a ...

**3**

votes

**1**answer

198 views

### On particular sumset properties of permanent?

Denote $\mathcal R_2[n]=\mathcal R[n] + \mathcal R[n]$ to be sumset of integers in $\mathcal R[n]$ where $\mathcal R[n]$ to be set of permanents possible with permanents of $n\times n$ matrices with $...

**2**

votes

**1**answer

233 views

### How hard is it to compute these prime factor related problems?

We know that computing number of prime factors implies efficient factoring algorithm (How hard is it to compute the number of prime factors of a given integer?).
Let $\omega(n)$ be number of distinct ...