All Questions
Tagged with combinatorics or co.combinatorics
11,021 questions
18
votes
4
answers
1k
views
Generalization of a mind-boggling box-opening puzzle
Motivation. Suppose we are given $6$ boxes, arranged in the following manner:
$$\left[\begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 6 \end{array}\right]$$
Two of these boxes contain a ...
- 48.8k
2
votes
1
answer
431
views
Shadows of partitions of lcm
$\DeclareMathOperator\lcm{lcm}$Fix an integer $n\geq1$. Denote the least common multiple $L_n=\lcm(1,2,\dots,n)$.
QUESTION. Is the following true? For each integer partition $\lambda=(\lambda_1,\...
- 43.2k
7
votes
1
answer
195
views
The tilde species
Consider a combinatorial species $F$, that is, an action of the symmetric group $\mathfrak S_n$ on a finite set $F[n]$. Recall that the elements of $F[n]$ are called structures. Furthermore, recall ...
- 5,822
2
votes
1
answer
276
views
Estimating a sum over set partitions
Let $[n]:=\{1,\dots,n\}$. Fix a set partition $\rho$ of $[n]$, with an abuse of notation we shall use $\rho\vdash [n]$.
I would like to estimate the following alternating sum.
QUESTION. Is this true?
...
- 43.2k
1
vote
1
answer
90
views
Characterizing the family of maximal cliques of a cograph
Preamble #1
There are two common equivalent definitions of cographs:
the smallest class that includes $K_1$ and is closed under disjoint union and complementation (or join);
the finite $P_4$-free ...
- 113
1
vote
0
answers
89
views
Test for odd prime triples in a $2p-1$ progression
Let $a(n)$ be A057326 (i.e., first member of a prime triple in a $2p-1$ progression).
Let $b(n) = B$ after $n-1$ iterations where we start with $A=n, B=1$ and for $i$ from $1$ to $n-1$ simultaneously ...
- 4,928
2
votes
0
answers
172
views
How many maximal length snakes are there?
This problem was motivated by the classic phone game Snake.
Consider the square grid graph with vertex set $V := \{1, \dots, N\}^2$, for fixed odd positive integer $N$, and an edge between $(x, y)$ ...
- 6,155
4
votes
1
answer
228
views
A definite integral of a hypergeometric series related to the enumeration of fusenes
If my calculations are correct, the number of (not necessarily planar) fusenes of perimeter $2n$ grows asymptotically like $\mu^n$ where
\begin{equation}
\mu = \frac{6}{\int_0^{1/6} H(t)\mathrm{d}t} = ...
- 3,927
4
votes
0
answers
90
views
Definition of Loop in an Oriented Matroid
I had posted this on Stackexchange because I don't believe this is a particlarly difficult question, but there were no answers, so I'm posting it on here now.
I just had a quick question about the ...
- 61
0
votes
1
answer
90
views
Finite projective geometry and the Krasner hyperfield
The Krasner hyperfield is an algebraic structure of two operations on $K=\{0,1\}$ called $+\colon K\times K\to \mathcal{P}(K)$ and $\cdot\colon K\times K\to K$ with
$0+0=0$
$0+1=1+0=1$
$1+1=\{0,1\}$
...
- 10.4k
2
votes
0
answers
111
views
Map between Weyl modules in terms of Young tableaux
The irreducible algebraic representations of $\text{GL}_n$ over the complex numbers are given by highest weight representations of dominant weights $\lambda=(k_1,k_2,\ldots,k_n): k_1 \ge k_2 \ge \...
- 461
4
votes
0
answers
145
views
Is it easier to exit a box to the right of a box in $\mathbb{Z}^2$ if I remove some edges to the left?
Suppose that I am given the graph $G = (V,E)$ where
$V = \{ 1, 2, \dots 2N+1 \} \times \{ 1, 2, \dots 2N+1 \} $
and there is an edge between two vertices $(n,m)$ and $(n',m')$ if and only if
$\vert n-...
- 1,054
4
votes
0
answers
124
views
LIS-based permutation property
Let $S_n$ be the set of all permutations of $\{1, \ldots, n\}$, thereafter treated as integer sequences. Let $A_n$ be the set of all such permutations $\sigma \in S_n$ that we can choose two ...
- 5,590
2
votes
0
answers
113
views
Numbers of positive terms in polynomials equal A069999
Let $a(n)$ be A069999 (i.e., number of possible dimensions for commutators of $n \times n$ matrices; it is independent of the field). OEIS states that no generating function is known.
Let $P(n,k)$ be ...
- 4,928
0
votes
0
answers
128
views
The smallest dihedral angle of convex polyhedrons
Given a set of points $\{x_{k}\}_{k=0}^{m} \subset \mathbb{R}^n$, is it always possible to find a constant $c=c(m,n)>0$, depending only on the dimension $n$ and the number $m$, such that, after ...
- 705
2
votes
0
answers
30
views
An algorithm to decompose a directly indecomposable permutation group into a wreath product
I am considering the following two binary operations on permutation groups:
the direct product, and
the wreath product.
It turns out that there is an efficient algorithm to factor a given ...
- 5,822
1
vote
0
answers
47
views
Harmonic numbers multifold convolution
I have a question. If I define the multifold convolution of Harmonic numbers as
$\sum_{n_1=1}^{\infty} \cdots \sum_{n_k=1}^{\infty} H_{n_1} \cdots H_{n_k} \mathbf{1}_{\{n\}}(n_1+\dots+n_k)$
for the $k$...
- 471
1
vote
1
answer
60
views
Optimal transport for sum of two costs
Let $X$ be a finite set and $\sigma_0$, $\sigma_1$ two fixed measures on $X$ with $\sigma_0(X)=\sigma_1(X)$. A transportation plan is a measure $\mu$ on $X\times X$ whose projections on the first and ...
- 1,074
4
votes
0
answers
91
views
Reference for fact about flags of vexillary permutations
Vexillary permutations are an important family of permutations in Schubert calculus. There are several definitions, for example that they avoid the pattern 2143.
Recall the Lehmer code of a ...
- 1,989
2
votes
2
answers
210
views
Rank of adjacency matrix of a graph on a sphere all of whose faces have four vertices
Let $G$ be a graph drawn on the sphere such that every face of $G$ has exactly four vertices. Question: can anything be said about the rank of the adjacency matrix of $G$ in terms of other (preferably ...
- 2,964
8
votes
4
answers
1k
views
Counting with trees
Let $\mathcal{U}_n$ denote the set of unrooted unlabelled trees with $n$ edges. For $T\in\mathcal{U}_n$, let $1^{u_1}2^{u_2}\cdots n^{u_n}$ be its degree distribution, that is, $u_i=\#$ of vertices ...
- 43.2k
6
votes
0
answers
164
views
Can one naturally transform Tamari lattices into distributive lattices with the same number of elements?
Many of the zillions of combinatorial objects counted by Catalan numbers come with various lattice structures.
The $n$th Tamari lattice $T_n$, as originally defined, is the lattice of all those maps $...
- 18.4k
5
votes
0
answers
185
views
Gaps in sumsets and difference sets
a) Let $S\subset \{1,2,\dotsc,N\}$ be a fairly thick set (with at least $N^{1-\epsilon}$ elements, say). Suppose that the intersection of, say,
$$3 S - 3 S = \{a_1+a_2+a_3-(a_4+a_5+a_6): a_1,\dotsc,...
- 20.2k
0
votes
1
answer
123
views
Petersen graph does not have a nowhere-zero 4-flow
I try to prove that the Petersen graph does not have a nowhere-zero 4-flow (i.e., over $\mathbb{Z}_4$), but I don't know how a proof could work...
I'm happy about every hint, thank you in advance!
6
votes
3
answers
550
views
Conjecture about commutative semigroups
Conjecture: given any commutative semigroup $S$ of order $n \ge 4$, there exist $a, b \in S$ with $a \ne b$, an integer $m \ge \lfloor (n-1)/2 \rfloor$, and two $m$-element subsets $X = \{x_1, \ldots, ...
- 990
4
votes
0
answers
114
views
A slight strengthening of the union-closed sets conjecture
Consider a union-closed family $\mathcal{F}=\{A_1,…,A_n\}$ of $n \gt 1$ finite sets.
I was not able to find a counterexample to the following conjecture:
there exist two sets $A,B \in \mathcal{F}$ ...
- 990
1
vote
1
answer
106
views
Iterated optimal transport
Suppose we are interested in two consecutive transport plans (in the Kantorovich formulation). That is, we are given finite sets $X$, $Y$ and $Z$, endowed with probability measures $\mu_X$, $\mu_Y$ ...
- 13
1
vote
0
answers
82
views
Generating functions related to generating function of Catalan numbers
Let $C_n$ be A000108 (i.e., Catalan numbers). Here generating function is $C(x)$ such that
$$
C(x) = \frac{1-\sqrt{1-4x}}{2x}.
$$
Let $a(n)$ be an integer sequence with generating function $A(x)$ such ...
- 4,928
0
votes
0
answers
84
views
Generate two bijectively mapped sets subject to certain conditions on choice of elements
$\DeclareMathOperator\setsum{setsum}$Let there be two sets of numbers of size $n$ each given by $S_1, S_2$.
Let there be a one-to-one onto mapping $f: S_1 \rightarrow S_2$.
Let us denote the sum of ...
1
vote
1
answer
196
views
Probability distribution on Python-dictionary-like objects?
I would like to examine information-theoretical properties of random variables that take as values objects which are akin to dictionaries in the Python programing language.
That is, each sample of the ...
- 11
7
votes
0
answers
195
views
"Center" of a set of binary strings
For a finite set $A$ in a metric space define its diameter ${\rm diam} (A)$ as the maximal distance between two points in $A$ and radius $r(A)$ as the minimal radius of a ball containing $A$. ...
2
votes
1
answer
100
views
Clique number and a special partition
Let $G=(V,E)$ be a finite, simple, undirected, connected graph, and let $\omega(G)$ denote its clique number. Assume that $G$ has a partition into $m$ independent subsets $U_1,\dots, U_m$ such that ...
- 21
2
votes
1
answer
226
views
Expanders except for commutativity?
What would you call a graph that is an expander except for commutativity, in the following sense?
Say that, from every vertex, you have $d$ edges ($d$ large) labelled $x_1,\dotsc, x_d$. Say that your ...
- 20.2k
0
votes
0
answers
64
views
Algorithm and equivalent recursion for A258173 (related to Dyck paths)
Let $a(n)$ be A258173 i.e. sum over all Dyck paths of semilength $n$ of products over all peaks $p$ of $y_p$, where $y_p$ is the $y$-coordinate of peak $p$.
A Dyck path of semilength $n$ is a $(x,y)$-...
- 4,928
2
votes
1
answer
210
views
Maximum number of ones in a full rank matrix with a restriction
Consider $n \times n$ binary matrices. I am interested in the largest number of ones possible in an $n \times n$ binary matrix with full rank over the field of integers mod 2 with the following ...
- 3,377
2
votes
1
answer
173
views
What do we know about the action of the symmetric group by conjugation on the set of permutation groups?
Motivation:
I have co-authored a package for sagemath to compute with combinatorial species, also known as sequences of group actions of the symmetric groups. In an effort to find good tests for that ...
- 5,822
5
votes
1
answer
344
views
Are parabolic Kazhdan-Lusztig polynomials truncations of the usual Kazhdan-Lusztig polynomials?
Let $(W,S)$ be the affine Weyl group associated to a simple root system.
For $x,y \in W$ we have the usual Kazhdan--Lustig polynomials $h_{y,x} \in \mathbb{Z}[v]$ in Soergel's normalisation, and if ...
- 10.5k
0
votes
0
answers
60
views
Algorithm for $q$-Bell numbers
Let $T(n,k)$ be A126347 (i.e., triangle, read by rows, with row polynomials $B(n, q)$). Here
$$
B(n, q) = \sum\limits_{k=0}^{n-1}\binom{n-1}{k}B(k, q)q^k, \\
B(0, q) = 1.
$$
Start with vector $\nu$ of ...
- 4,928
7
votes
0
answers
208
views
How biased is $(x_i x_j)_{i,j}$, $x_i\in \mathbb{F}_2$?
Let $N = \frac{n (n-1)}{2}$. Let $V$ be the $N$-dimensional vector space over $\mathbb{F}_2$ consisting of tuples $(x_{(i,j)})_{1\leq i <j \leq n}$, $x_{(i,j)}\in \mathbb{F}_2$. Let $S$ be the set ...
- 20.2k
-2
votes
1
answer
298
views
Is polynomial not bijective, on this finited field?
Let $(a,b,c) \in \mathbb F_p,p=2^{127}-1$ and $P(x)=x^{16}+ax^{11}+bx^{5}+c$.
Is it true that $P(x)$ not bijective on $\mathbb F_p$?
I have asked this question here (*), but no answer.
(*) : https://...
- 4,074
0
votes
0
answers
98
views
Number of tetrahedra inside a sphere with boundary A
I understand, that there are some combinatorial problems which are not yet solved regarding gluing triangulations in 3D. At least last time I checked, it was not yet known exactly how many ...
- 183
1
vote
1
answer
177
views
Algorithm for A127782
Let $a(n)$ be A127782 (i.e., an integer sequence with generating function $A(x)$ such that $A(x)=1+xA(x+x^2)$). Here
$$
a(n) = \sum\limits_{k=0}^{\left\lfloor\frac{n-1}{2}\right\rfloor} \binom{n-k-1}{...
- 4,928
23
votes
4
answers
2k
views
Identity for an infinite product
Here is an experimental "result" exhibiting the difference of two (formal) infinite products that "almost factorizes".
QUESTION. Is this true?
$$\prod_{n\geq1}(1+x^{2n-1})^{24} - \...
- 43.2k
4
votes
1
answer
195
views
Optimal partition of $n$ points
Given an integer $n$, and 3 real sequences $\{x_1, \dots, x_n\}, \{y_1, \dots, y_n\}$ and $\{w_1, \dots, w_n\}$ with $x_k, y_k, w_k > 0$, for all $k \in \{1, \dots, n\}$. For a fixed $p < n$ ...
- 43
1
vote
0
answers
151
views
Decide if a group is abelian
Let $G = \langle X: R\rangle$ be a finitely presented group. The following problem seems very natural to me, yet I cannot find any reference for it: Decide if $G$ is abelian or not.
With a reduction ...
- 11
3
votes
0
answers
61
views
Is this bipartite equivalent of 1-walk-regular graphs known?
A graph $G$ is 1-walk-regular if
for each vertex $v$ the number of closed walks of length $\ell$ starting (and ending) at $v$ depends only on $\ell$ but not on $v$.
for each edge $vw$ the number of ...
- 13.6k
2
votes
1
answer
221
views
A question on signed Stirling numbers of the first kind
Let $(x)_0=1$ and $(x)_n=x(x-1)\cdots(x-n+1)$ for $n=1,2,3,\ldots$. The signed Stirling numbers of the first kind, $s(n,k)$ with $n\ge k\ge0$, are defined by
$$(x)_n=\sum_{k=0}^ns(n,k)x^k.$$
Question. ...
- 15.6k
1
vote
1
answer
75
views
Probability of correctly guessing the maximum event probability of a multinomial distribution
I have a sample from multinomial distribution with $n$ trials, and $k=3$ options. I know that one of the event probabilities $p_i$ is larger than the two others (who are equal). I'm trying to guess ...
- 267
1
vote
0
answers
118
views
Can we construct the circular permutation from partial partition info?
Imagine a circular permutation of n points on a circle, if we draw a line connecting any pair of points, the rest of the points are divided into two sets that are on the same side. We can partition a ...
- 11
0
votes
1
answer
155
views
Combinatorial problem in $G(54, \, 5)$ - Reprise
This post is a follow-up to my previous post MO479127. I am trying to concentrate on a subset of relations, hoping to find some structure on the set of solutions that explains why the whole set of ...
- 66.3k