Questions tagged [co.combinatorics]
Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.
10,560
questions
7
votes
1
answer
374
views
Large sets of nearly orthogonal integer vectors
This question is motivated by the Question 5 from the 2017 Asia Pacific Mathematical Olympiad. To paraphrase, the question asks what is the largest cardinality of a set $S \subset \mathbb{Z}^n$ such ...
- 25.5k
7
votes
1
answer
175
views
Origin of the abacus bijection
What is the origin of the abacus bijection (aka the rim hook bijection, aka the Stanton-White bijection, aka James's bijection)?
Igor Pak, in his 2000 article "Ribbon tile invariants" (...
- 19.4k
7
votes
1
answer
249
views
Real world applications of graph limits
It is well known that the area of graph limits (initiated by Lovász and coauthors) had provided a very powerful framework to deal with problems arising, for instance, in extremal combinatorics and ...
- 1,543
7
votes
1
answer
175
views
$d$-ball approximation for $d\gg 1$ with a convex hull of random points on its boundary
Given a $d$-ball $\mathcal{S}^{d}$, let $P_n$ a set of $n$ points selected uniformly at random on the boundary $\mathcal{S}^{d-1}$ of $\mathcal{S}^{d}$. Let $\mathcal{C}_n$ the convex hull of $P_n$. ...
- 1,677
7
votes
1
answer
227
views
Chromatic number and vertex connectivity
A conjecture of Mader implies that for any positive integer $n\geq2$, every graph with average degree at least $3n-4$ contains an $n$-connected subgraph. Mader himself proved this for $n=2,3,4,5,6,7$. ...
- 123
7
votes
1
answer
311
views
Looking for a $q$-analogue of a binomial identity
The following identity is well-known and there are a few proofs to it (see Bijective proof problems, by R P Stanley, for this and similar formulae):
$$\sum_{k=0}^n\binom{2k}k\binom{2n-2k}{n-k}=4^n \...
- 41.8k
7
votes
1
answer
194
views
Trace of a matrix associated to posets
Let $P$ be a finite connected poset with $n$ elements. Let $C=(c_{x,y})$ be the $n \times n$ matrix with entry 1 in case $x \leq y$ and 0 else.
The Coxeter matrix of $P$ is defined as the matrix $M_P=-...
- 26.1k
7
votes
1
answer
233
views
Asymptotics of sum involving Stirling numbers
I've encountered the following sum:
$$
s_n = \sum_{j=1}^n {n \brace j}(\alpha n)_j \beta^j.
$$
Here $\alpha$ and $\beta$ are positive constants, $(\alpha n)_j$ is a falling power, and ${n \brace j}$ ...
- 1,112
7
votes
1
answer
356
views
Jack function in power symmetric basis
In Macdonald's book, the Jack symmetric function $J_{\lambda}(x_1,\ldots, x_n)$ for a partition $\lambda$
is defined by three properties (orthogonality, triangularity, and normalization). In the ...
- 685
7
votes
3
answers
487
views
Minimum number of swaps needed to 'group' a sequence?
Let a finite sequence $s=\{s_1,\dots,s_N\}$ (the characters of which are chosen from a finite set $\{c_1, \cdots, c_M\}$) be called "grouped" if for any $s_i=s_j$, $i<j$, we have $s_k=s_i=s_j$ for ...
- 1,196
7
votes
1
answer
186
views
3 term van der Waerden with large step size
Let $P(n)$ be the statement "any $n$ coloring of $\mathbb{N}$ contains a monochromatic progression $a, a+d, a+2d$ such that $d>a$".
For which $n$ is $P(n)$ true?
It's easy to see that $P(2)$ is ...
user151767
7
votes
1
answer
430
views
Two conjectural series for $\pi$ involving the central trinomial coefficients
For each $n=0,1,2,\ldots$, the central trinomial coefficient $T_n$ is defined as the coefficient of $x^n$ in the expansion of $(x^2+x+1)^n$. It is easy to see that $T_n=\sum_{k=0}^{\lfloor n/2\rfloor}\...
- 14.5k
7
votes
1
answer
526
views
Wreath product $S_k\wr S_n$ inside $S_{kn}$
I want to understand wreath products a little better.
Currently, my intuition about them is as follows. Take $nk$ disks, pile them in order forming $n$ piles of $k$ disks (one pile contains disks {1,...
- 1,417
7
votes
1
answer
156
views
Does a bounded branching/log depth dihotomy hold for rooted trees?
Let $T$ be a rooted tree. For any subtree $T' \subset T$ write $L(T')$ for the number of leaves of $T'$.
Further, for $T' \subset T$ define the branch-depth of a node $v \in T'$ as the number of ...
- 950
7
votes
1
answer
139
views
equidistributed parameters on graphs
Let $\mathcal G_n$ be the set of (isomorphism classes of unlabelled) simple graphs on $n$ vertices.
I wonder whether there are any 'interesting' combinatorial parameters $a,b: \mathcal G_n\to \mathbb ...
- 5,563
7
votes
2
answers
3k
views
The largest Wasserstein distance to uniform distribution among all probability distributions with uniform marginals
I am looking for the largest Wasserstein distance to the uniform distribution among all probability distributions with uniform marginals.
More specifically, let $\Xi=\{1,2,\ldots,N\}^2$, and let $\nu$...
- 412
7
votes
1
answer
203
views
Algorithm to generate random commuting permutations
I am seeking to understand the properties of a typical pair of permutations $(\sigma,\tau) \in \mathrm{Sym}(n)^2$ chosen uniformly at random from all pairs such that $\sigma$ and $\tau$ commute. In ...
- 1,689
7
votes
1
answer
230
views
counting monomials and integrality
For $n\in\mathbb{Z}^{+}$, consider the polynomials
$$P_n(x)=\prod_{k=0}^{n-1}(x^n-x^k).$$
QUESTION. Is it possible to find a closed formula for the number of monomials in $P_n(x)$, after expansion?
...
- 41.8k
7
votes
1
answer
315
views
How to find a permutation of [n] so that $\sum\{\min(i-l[i],r[i]-i)\}$ is maximized?
Given a sequence $a_1, a_2,\dots,a_n$, define the two sequences
$$l_i=\max_{1 \leq j < i, a_j \geq a_i} j$$
or $0$ if it does not exist; and
$$r_i=\min_{i < j \leq n, a_j > a_i} j$$
or $n+...
- 173
7
votes
1
answer
302
views
Does an expander remain an expander after removing few vertices and edges?
Consider a sequence of expander graphs ($G_n$); say $G_n$ has $n$ vertices.
Remove $o(n)$ vertices (and the edges emanating from these vertices) and cut $o(n)$ edges. Call $G'_n$ the largest connected ...
- 73
7
votes
1
answer
190
views
Schur positivity on 2 letter alphabets implies Schur-positivity on n letters?
Suppose we have a symmetric polynomial $P$ in $n$ variables.
We can partition this alphabet into sets with one or two letters, e.g. ${ {x_1}, {x_2, x_3}}.
We can thus see $P$ as an element in $Q[x_1]...
- 15.6k
7
votes
1
answer
432
views
Can every trace preserving isomorphism of unital self-adjoint matrix algebras be realized as conjugation by a unitary?
In this paper, Friedland shows (in Lemma 3.4) that if $\phi$ is an isomorphism of coherent algebras, then there exists a unitary $U$ such that
$$ \phi(M) = UMU^\dagger$$
for all $M$. I am wondering if ...
- 2,289
7
votes
1
answer
188
views
New base of matroid from old
Let $M$ be a matroid of rank 3 and $E_1, E_2, E_3$ 3 basis of $M.$ Let $e_{i,j}$ be the $i$-th element of base $E_j$.
Is it true that you can always find a permutation $s: \{1,2,3\} \to \{1,2,3\}$ ...
- 603
7
votes
1
answer
423
views
Recursive sequence of binomial random variables
Fix $p>0$ and define a recursive sequence of random variables with $X_1 =1$ and
$$X_{k+1} = X_k + \text{Bin}(X_k,p).$$
Thus, $\mathbf E [ X_k ] = (1+p)^k$.
I would like a left tail bound. Perhaps, ...
- 181
7
votes
1
answer
417
views
Flooding a cycle digraph via chip-firing: $n^{k-1} + n^{k-2} + \cdots + 1$ bound (a Norway 1998-99 problem generalized)
Let $k > 1$ and $n$ be positive integers. Let $\mathbb{N} = \left\{0,1,2,\ldots\right\}$. Let $D$ be a digraph which has exactly $k$ vertices $v_0$, $v_1$, ..., $v_{k-1}$ and exactly $k$ arcs $v_0 \...
- 33.2k
7
votes
1
answer
219
views
A polytope with a bound on the sum of any $k$ variables
Let $2\le k\le n-1$ and define the polytope
$$P_k(n) = \lbrace (x_1,\ldots,x_n) \in \mathbb{R}^n :
-1\le x_{i_1}+\cdots +x_{i_k} \le 1 \text{ for all } 1\le i_1\lt\cdots\lt i_k\le n\rbrace.$$
There ...
- 37.2k
7
votes
1
answer
341
views
Origin of the numbers game
The numbers game is a (one-player) game played on a finite graph with an initial assignment of numbers to its vertices, studied by Alon, Bj\"orner, Brenti, Donnelly, Eriksson, Krasikov, Mozes, Peres, ...
- 19.4k
7
votes
1
answer
273
views
What is the Essential Reason that allows a PTAS for the EUCLIDEAN TSP?
Questions:
Is there some understanding of the reason, why the euclidean TSP allows a PTAS, whereas the metric TSP in general does not and, is the PTAS stable under sufficiently small perturbation of ...
- 12.7k
7
votes
1
answer
335
views
Under which constraints are there only finite numbers of irreducible eta product identities?
For the Dedekind eta function, defined as usual by $\eta(q) = q^{\frac1{24}} \prod\limits_{n=1}^{\infty} (1-q^{n})$, let for brevity $e_k:=\eta(q^k)$.
An eta product identity (or eta identity for ...
- 13.2k
7
votes
1
answer
129
views
Generalising the adherence operator and its closure properties with regard to regular (rational) languages
Let $X$ be an alphabet and denote by $X^{\omega}$ the set of all infinite sequences (i.e. words) in $X$. A subset $L \subseteq X^{\omega}$ is called $\omega$-regular if it is acceptable by some Büchi-...
- 798
7
votes
1
answer
259
views
How "accidental" are equalities between parts of Ehrhart quasi-polynomials? When do they persist to Euler-Maclaurin?
Background
What I think of Ehrhart theory (http://en.wikipedia.org/wiki/Ehrhart_polynomial) asserts that if we take a lattice polytope $P$, and count the number of lattice points in the $t$th ...
- 2,362
7
votes
1
answer
668
views
fixed points of products of permutations
This question is related to that (if $s$ is co-prime with prime $p$ and a permutation in $S_s$ has order $p$, then it fixes a point).
Let us fix two (finite) numbers $p\gg 1, n\gg 1$. Say, $p=47, n=...
user6976
7
votes
1
answer
1k
views
When is a complete fan a normal fan?
Is there a characterization for when a complete fan in $\mathbf{R}^n$ is the normal fan of a polytope? Thanks!
- 71
7
votes
4
answers
524
views
Low rate c-uniform pairwise intersecting set systems
Let $U$ be some (unbounded) universe of elements, and let $\mathcal{S}$ be a collection of subsets of size $c$ each, such that any two elements from $\mathcal{S}$ have a non-empty intersection. Let $C ...
- 723
7
votes
1
answer
561
views
Upper bound for size of subsets of a finite group that contains a sum-full set
Problem
I'm looking for an upper bound for the number $k(G)$ of a finite group $G$, defined as follow:
Let $\mathcal{F}_k$ be the family of subsets of $G$ with size $k$, and we
define $k(G)$ be ...
- 1,250
7
votes
2
answers
465
views
A quadratic form
Let $q$ be a power of 2. Let $P$ be the set of polynomials in
$F_q [x]$ of degree d or less.
Let $\mathbb{Z}$ be the ring of integers. For any $f \in P$, let $\psi(f)$ be the
number of distinct ...
- 503
7
votes
1
answer
135
views
Nearest neighbors on random complete graph
Consider the complete graph on $2n$ vertices, where the ${2n \choose 2}$ edges have distinct lengths in uniform random
order. So each vertex $v$ has a nearest neighbor $N(v)$, across the shortest ...
- 216
7
votes
1
answer
251
views
Set of points covered by subspaces of small dimensions
Let $S \subset \mathbb R^d$ be finite set of points. We say that $S$ is $2$-covered if $S$ lies in a union $V_1\cup V_2$ of affine subspaces such that $\dim(V_1)+\dim (V_2)\leq d-1$. For example, if $...
- 30.3k
7
votes
1
answer
163
views
A formula for the generating function of Hoggatt binomials or of some Young tableaux
Let ${\left\langle\matrix {n \cr k}\right\rangle}_r$ denote the $r-$Hoggatt binomials defined by
$${{\left\langle\matrix {n \cr k}\right\rangle}_r=\frac{\langle n \rangle_r!}{\langle k \rangle_r! \...
- 5,572
7
votes
1
answer
241
views
$(q,t)$-Fibonacci polynomials: area & bounce statistics
This is related to my earlier (unanswered) MO post. Preserve notations from there.
We take advantage of the one-to-one correspondence between the $(s,s+1)$-core partitions and $(s,s+1)$-Dyck paths. ...
- 41.8k
7
votes
1
answer
276
views
3D Edge matching puzzle generation
I have this weird idea for a puzzle/toy (or torture device, depending on how you look at it) I've been trying to make for years now.
I happen to be worse at this kind of math as I thought; and I'd be ...
- 79
7
votes
1
answer
923
views
Elementary precise estimate of the covering number of euclidean balls by hypercubes
I am looking for a straightforward way to upper bound the covering number of a $d$-dimensional euclidean ball by $\ell_\infty$-balls of radius $\varepsilon$, which I will call cubes of sidelength $2\...
- 172
7
votes
1
answer
442
views
Geometric foundation of the Grothendieck polynomials
Grothendieck polynomials were firstly defined in
Alain Lascoux and Marcel-Paul Sch¨utzenberger. Structure de Hopf de l’anneau de cohomologie et de l’anneau de Grothendieck d’une vari´et´e de drapeaux....
- 719
7
votes
2
answers
389
views
On a statistic for permutations
Given a permutation $\pi$ we can write $\pi=s_{i_1} ... s_{i_l}$ as a product of simple transpositions $s_i=(i,i+1)$ in a minimal way.
Question 1: Is there an "official" name for the permutation ...
- 26.1k
7
votes
1
answer
264
views
Lipschitz-continuity of convex polytopes under the Hausdorff metric
Recently, I proved the following Lipschitz-continuity like result for convex polytopes:
Let $A\in\mathbb R^{m\times n}$ and $b,b'\in\mathbb R^m$ be given such that $\{x\,:\,Ax\leq 0\}=\{0\}$ (which ...
7
votes
1
answer
306
views
Changing tiles by swapping squares
In an $n\times n$ table, initially there is a $1\times n$ tile in each row. A swap is an operation that involves choosing two tiles, move one square from the first to the second tile, and ...
- 1,199
7
votes
1
answer
142
views
Set-theoretic solutions of YBE for $n=3$
Is there a list of all set theoretic solutions $S:X \times X \to X \times X$ of the YBE for $X=\{1,2,3\}$? Or is it known how many solutions there are? I mean, $S_9$ is big but maybe not too big to ...
- 1,661
7
votes
1
answer
245
views
Collecting proofs of the birth of the giant component
I want to collect different proofs of Erdös-Rényi result on the double jump of the largest connected component on $G(n,p)$ (or in $G(n,M)$.
I know the original proof of Erdös-Rényi, the proof that ...
- 1,543
7
votes
2
answers
244
views
complicated combinatorial algorithms with good descriptions
For educational purposes, I am looking for an example of a complicated, elementary, but very well-explained combinatorial algorithm.
Such an example might be a bijection between two easily described ...