## New answers tagged co.combinatorics

1
vote

### A combinatorial identity counting shellings of $K_n$

Yes, this is equivalent to the hypergeometric identity
$${}_2F_1\biggl(\begin{matrix}a,-b\\c\end{matrix}\bigg|\;1\biggr)
={(a-c)(a-c-1)\dots(a-c-b+1)\over(-c)(-c-1)\dots(-c-b+1)};\quad\text{integer $b\...

5
votes

Accepted

### Denominators of rational polytopes in terms of hyperplane coefficients

Let $x$ be a vertex of $\mathcal{P}$. By Cramer's rule, there is an $n \times n$ matrix $C$ such that each coordinate of $x$ is an integer multiple of $\frac{1}{|\det(C)|}$, and the absolute value of ...

21
votes

Accepted

### Does this expression always vanish?

Recall that
$$
\sum_iA_i^{n-1}\prod_{j\neq i}\frac1{A_i-A_j}=1,
$$
as follows from the Lagrange interpolation of $x^{n-1}$.
Now apply $\prod_i \frac \partial{\partial A_i}$.
We get
$$
\sum_i\left((...

1
vote

### Computing the expectation of a quadratic matrix form involving Bernoulli and Gaussian distributed matrices

$\newcommand{\ka}{\kappa}\newcommand{\si}{\sigma}$We have $\ka^2=ZHZ^TZHZ^T$ and hence, for $i$ and $j$ in $[n]:=\{1,\dots,n\}$,
\begin{equation}
(E\ka^2)_{ij}=\sum_{k,l,m,s,r}EZ_{ik}H_{kl}Z_{ml}...

1
vote

### Tree decomposition of graphs with low height

One way to address this question is to think of a tree decomposition as an unrooted tree. Then, it is easy to see that its diameter is related to the depth by a factor of 2. Searching for diameter, ...

0
votes

### Computing the expectation of a quadratic matrix form involving Bernoulli and Gaussian distributed matrices

If $H$ has iid $N(0,1)$ entries, write $\kappa=\langle Z^TZ, H\rangle$ using the usual Frobenius inner product $\langle A,B\rangle = trace[A^TB]$. Conditionally on $Z$, $\kappa\sim N(0,\|Z^TZ\|_F^2)$ ...

6
votes

Accepted

### Sum of squares of chromatic roots of a bipartite graph

Consider the chromatic polynomial as a sum of monomials:
$$P(G, k) = (k - r_1)(k - r_2)\cdots(k - r_n) = k^n + a_1k^{n-1} + \cdots + a_{n-1}k + a_n$$
It has been shown that $a_2 = \binom{e(G)}{2} - ...

8
votes

Accepted

### Conjecture about partitions of the powerset without the empty set

Here is a counterexample for $n=5$. Partition the non-empty subsets of $\{1, \dots, 5\}$ into the singleton subsets and a sixth family containing all the other non-empty subsets. So, $m=6$ and $|\...

6
votes

### Conjecture about partitions of the powerset without the empty set

Partition the subsets of $\{1,2,\dots, 100\}$ as $\{\mathcal{A_1},\ldots,\mathcal{A_6}\}$ by defining
$$\mathcal{A_i}=\{S\in \mathcal{P}([100]) \setminus \{\emptyset\}: \text{all elements of S are} \,\...

3
votes

### Conceptual reason why the sign of a permutation is well-defined?

Here is a formula I have not seen in the long and excellent list of answers: If $\sigma\in\mathfrak S_n$, then $\mathop{\rm sgn}(\sigma)=(-1)^{n-p}$, where $p$ is the number of orbits of $\sigma$ on $\...

2
votes

### Enumerating all inequivalent planar embeddings of a planar graph

I had this same problem. I couldn't find any actually implemented code after a lot of looking, but I did find some papers describing how to do it.
The most promising was "A linear algorithm for ...

1
vote

### Clique number of $k$-critical graphs

For an upperbound, the clique number of a $k$-critical graph is obviously at most $k$, and this is achieved by the complete graph $K_k$. There is no non-trivial lowerbound for the clique number, and ...

10
votes

### Corners theorem in finite fields

Concerning your second question
...is there a known result of the form $r_\angle(\mathbb{F}_p^n)=O(c^{2n})$ for some $c<p$? This would, for the same reasons, imply that $r_3(\mathbb{F}_p^n)=O(c^n)$...

5
votes

### Combinatorial consequences of de Branges's Theorem?

In these lecture slides, Applications of de Branges–Rovnyak decomposition to graph theory Michio Seto reports on work with Sho Suda and Tetsuji Taniguchi on applications of de Branges–Rovnyak ...

7
votes

### Ordinary partitions vs partitions into odd parts

For what it worth, here is a combinatorial proof.
We start with a known
Lemma 1. Let $m$ be an even positive integer. Then the number of permutations of $[m]$ with only odd cycles equals to the number ...

2
votes

### Reference request for combinatorial problem related to $\max$ relation

I also don't have a reference, but I think one should be able to do this fairly explicitly as follows [it appears that Peter Taylor alludes to this strategy in their comment above]:
First, note that ...

9
votes

### Ordinary partitions vs partitions into odd parts

Yes, they are the same. It is more convenient to write this in terms of compositions instead of partitions. Writing $\mathcal{OC}(n)$ for the set of compositions of $n$ with odd parts, the LHS is $$\...

10
votes

Accepted

### Ordinary partitions vs partitions into odd parts

The g.f. for the right-hand is
$$e^{2x}\cdot e^{2x^2} \cdots = e^{2\frac{x}{1-x}}.$$
For the left-hand side, additionally introducing variable $y$ to account for partition length, we get
$$\sum_{n\...

4
votes

### Enumerating all inequivalent planar embeddings of a planar graph

As suggested by Henrik Rüping in the comments, this problem can be solved in principle using the representation of embeddings by permutations, i.e., using combinatorial maps (aka "rotation ...

1
vote

### Topological characterisations of properties of posets

Recall that an Alexandrov space is a topological space where the intersection of arbitrary collection of open sets is open. Alexandrov duality states that the category of Alexandrov spaces is ...

1
vote

### Perfect 1 error correcting codes non-isomorphic to Hamming codes?

You can find a lot of information in the recent book:
"Perfect Codes and Related Structures," by T. Etzion.
The notes to Chapter 5 contain a long list of references.
In particular, if you're ...

4
votes

### Three-dimensional triangulations with fixed number of vertices

$\def\RR{\mathbb{R}}\def\ZZ{\mathbb{Z}}\def\Hull{\text{Hull}}$
This is a broken answer; it gives a triangulation of the lens space $L(3,1)$, not $S^3$.
Step 1 The cylinder: Inside $\RR^3$, define
$$\...

1
vote

### On algebraic topology of coset complexes without geometry

Regarding your question (ii):
So far as I know, proving the Nerve Lemma requires either a homotopy type argument, or a spectral sequence argument. You can find the spectral sequence argument in Ken ...

0
votes

Accepted

### Upper bounds estimates of Minkowski sum

No. As GH from MO said, there are plenty of sets $A,B\subset \Bbb{Z}$ where $|A+B|=|A||B|$, taking products of these such sets shows you can’t absorb these into the $O_d(\cdot)$.
For example take $d\...

2
votes

### On algebraic topology of coset complexes without geometry

This result is known to me as "Tits Lemma" (I learned it as part of the theory of buildings) and he proved it in
Tits, Jacques, Ensembles ordonnés, immeubles et sommes amalgamées, Bull. Soc....

10
votes

Accepted

### Submodule lattices of preprojective algebras

Here is an answer to question (2), strongly inspired by Dave Benson's comment:
Theorem Let $A$ be any ring and let $M$ be a finite length $A$-module. Then the lattice of $A$-submodules is distributive ...

1
vote

### On the number of intersection points between a curve and a (horizontal, vertical) line inside a unit square

The following claim and its proof answer OP's question, but only under an additional hypothesis on the critical points of the coordinate functions $\gamma_i$ of the curve $\gamma = (\gamma_1, \dots, \...

1
vote

Accepted

### Find an order-embedding of $S_3\times{\bf2}\times{\bf2}$ into ${\mathbb Z}^4$

We present an embedding into $\mathbb Z^3$. It is symmetric with respect to the premutation of the coordinates in $S_3$, so it suffices to show the images of the following elements $((x,y,z),a,b)\in ...

2
votes

### Topological characterisations of properties of posets

I will discuss
Question 1: Is there a nice purely topological characterisation when a connected finite topological space with $T_0$ corresponds to a lattice and when this lattice is distributive?
...

0
votes

### Sequences that don't count algebraic structures on finite sets

Because it's too long for a comment I'll post this as an answer: I just want to provide Omar Antolín's nice proofs of the following facts. These facts probably go back to this paper:
László Lovász, ...

3
votes

### Is matroid realizability computable?

A matroid being representable is equivalent to a certain locally closed subscheme of the Grassmannian, defined by the non-vanishing of the Plücker coordinates corresponding to bases and the vanishing ...

5
votes

### Is "do-almost-nothing" ever winning on large CHOMP boards?

Using this code, I've searched up to $15×15$ and $6×65$. Improved memory management is required to go further. The only large (not $2×n$) boards on which the minimal move is winning in this range ...

9
votes

### Sequences that don't count algebraic structures on finite sets

The original question was:
My question is: can anyone name a sequence $(a_n)_{n\geq 1}$
of natural numbers that grows more slowly than exponentially,
yet is not a model sequence?
Any model sequence $(...

6
votes

Accepted

### Does Kalai's $3^d$ conjecture hold for simplicial spheres?

The reference for Kalai's conjecture for simplicial polytopes is Richard Stanley's paper On the number of faces of centrally-symmetric simplicial polytopes
which includes the theorem:
Let $A$ be a $(...

0
votes

### Sign-reversing involution for $q$-binomial coefficient at $q=-1$

I am recording here the algebraic proof using exterior powers of vector spaces. I think it makes for an interesting comparison to Will Sawin's very nice answer, because here the reverse really appears....

Community wiki

7
votes

Accepted

### Sign-reversing involution for $q$-binomial coefficient at $q=-1$

Here is a uniform proof:
Consider the involution on words $w_1,\dots,w_n$ of length $n$ that takes the first $j$ such that $1 \leq j \leq n/2$ with $w_{2j-1}$ and $w_{2j}$ distinct and swaps $w_{2j-1}$...

4
votes

### On the number of intersection points between a curve and a (horizontal, vertical) line inside a unit square

Let $\varphi: [0,L] \to [0,2\pi)$ give the direction of the curve.
Then the number of intersected horizontal lines (with multiplicities) is given by $\int_0^L |\sin\varphi(t)| dt$.
Similarly, the ...

0
votes

### Khovanskii's theorem on iterated sumsets

Your idea is essentially correct. Suppose $x\in\mathbb N_0^r$ is useless. Then either there does not exist any useless $x_1\in\mathbb N_0^r$ satisfying $x_1\le x$, in which case $x\in X$ and trivially ...

2
votes

### Graph alignment by considering node and edge weights

This is a very interesting problem, although I'm not sure if it's a mathematical problem exactly (as opposed to one of algorithmic modeling). That said, here are some two suggestions.
Suggestion #1: ...

4
votes

Accepted

### Some necessary condition for $\gcd(m,n) $ be a proper divisor of $\gcd(mk_2 +nk_1,mn) $

Yes, Statement 1 does imply Statement 2. With
$$d = \gcd(m, n), \;\; m = de, \;\; n = df, \;\; \gcd(e, f) = 1 \tag{1}\label{eq1A}$$
then
$$\gcd(mk_2 + nk_1, mn) = \gcd(dek_2 + dfk_1, d^2ef) = d\gcd(...

2
votes

Accepted

### Isomorphism of two regular hypergraphs

No. There are already multiple isomorphism classes of regular graphs. Consider two disjoint triangles (i.e., $\{12,23,31\}\cup \{45,56,64\}$), versus a cycle of length 6 ($\{12,23,34,45,56,61\}$).

4
votes

Accepted

### Determining graph Isomorphism: combining invariants

There will be strongly-regular graphs of the same parameters with equal values of all those invariants. Since the parameters determine the eigenvalues, all the invariants determined by the spectrum (...

3
votes

### Reference for group-algebra/exp-log like identites in combinatorics

A good starting point for a literature search on this and related types of inversion formulas is OEIS A036040 which will lead you to a slew of general theorems and generalizations as well as explicit ...

0
votes

### What is a chess piece mathematically?

Rereading the questions, I would simply answer that with the basic rule of chess one can consider the pieces as instances (or initializations on a game board) take from mobility classes that directly ...

12
votes

### Reference for group-algebra/exp-log like identites in combinatorics

The reason this is called the "exp-log" correspondence is that it can be written in terms of formal power series as follows: write $G(z) = \sum g_n z^n, F(z) = \sum f_n z^n$. We need the ...

3
votes

Accepted

### A second attempt at a two-dimensional Higman's Lemma

The answer is still no. Here is a counterexample for three letters $X,Y,Z$; With a bit of care in the arguments, it can be fir into two letters.
For convenience, we present a sequence where indices ...

7
votes

Accepted

### Elegant proof for $xy < yx \Leftrightarrow x^\mathbb{N} < y^\mathbb{N}$

Let $x, y \in \Sigma^+$.
Observe that for all $n \in \mathbb{N}$ the inequality $xy<yx$ implies that $$x^ny^n<y^nx^n$$ by repeatedly swapping pairs of $x$ and $y$. It follows that $x^\mathbb{N}\...

6
votes

Accepted

### Congruences for power-sum of divisors

I wrote an answer in the comment section, so I'll rewrite it here.
The claim of
$$F_1(q)-F_3(q)\equiv F_1(q^p) \pmod p$$
is equivalent to the following two cases
$$p\nmid n: \sum_{d|n} d-nd^3 \equiv ...

9
votes

Accepted

### Estimate of Minkowski sum

This is only a partial answer to your question; I believe there is more current work, and have forwarded your question to someone working in this area to see if they have more recent results.
In ...

5
votes

Accepted

### Arboricity and average degree

Denote $A(G)=A$. Let $H$ be the subgraph for which $\lceil \frac{|E_H|}{|V_H|-1}\rceil=A$. Write $e$ for $|E_H|$, $v$ for $|V_H|$. We have $e/(v-1)>A-1$, thus $e>(v-1)(A-1)$. On the other hand, $...

Top 50 recent answers are included

#### Related Tags

co.combinatorics × 10315graph-theory × 2144

nt.number-theory × 1166

reference-request × 1002

pr.probability × 756

discrete-geometry × 566

rt.representation-theory × 491

linear-algebra × 482

gr.group-theory × 435

enumerative-combinatorics × 369

sequences-and-series × 342

graph-colorings × 326

algorithms × 321

permutations × 320

additive-combinatorics × 302

polynomials × 274

ag.algebraic-geometry × 268

partitions × 268

binomial-coefficients × 246

convex-polytopes × 235

matrices × 233

mg.metric-geometry × 232

computational-complexity × 221

generating-functions × 199

finite-groups × 173