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\...
- 308
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 ...
- 30.2k
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((...
- 21.2k
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}...
- 105k
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)$ ...
- 1,069
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} - ...
- 526
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 $|\...
- 30.2k
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} \,\...
- 84.1k
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 $\...
- 12.6k
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 ...
- 21
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 ...
- 30.2k
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)$...
- 11.2k
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 ...
- 38.3k
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 ...
- 96.8k
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 ...
- 305
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 $$\...
- 1,432
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\...
- 29.1k
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 ...
- 3,283
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 ...
- 26.8k
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 ...
- 588
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
$$\...
- 148k
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 ...
- 3,367
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,734
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....
- 4,937
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 ...
- 148k
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, \...
- 7,138
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 ...
- 21.2k
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?
...
- 11.3k
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, ...
- 20.9k
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 ...
- 953
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 ...
- 349
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 $(...
- 11.3k
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 $(...
- 129k
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....
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}$...
- 129k
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 ...
- 18.4k
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 ...
- 308
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: ...
- 3,700
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(...
- 564
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\}$).
- 2,734
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 (...
- 36.1k
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 ...
- 9,377
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 ...
- 1
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 ...
- 113k
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 ...
- 21.2k
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 ...
- 469
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 ...
- 104k
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, $...
- 96.8k
Top 50 recent answers are included