All Questions
Tagged with combinatorics or co.combinatorics
11,021 questions
3
votes
0
answers
81
views
Can we remove the restriction on a parameter in Talagrand concentration inequality?
Recently I am trying to use Talagrand concentration inequality to do something on graphs. I find a version from the book of Molloy and Reed ''Graph Colouring and Probabilistics Method''. I attached a ...
- 1,190
2
votes
0
answers
95
views
Finding a well-spaced interval of natural numbers
For $b>0$, let us say that a subset $I\subseteq \{1,\ldots,n\}$ is $b$-good if
(1) $\# I\geq b n$,
(2) $\ell_{i+1}-\ell_i\leq \frac{1}{b}$ for all $i=1,\ldots,\#I-1$, where we write $I=\{\ell_i\}_{...
- 502
4
votes
1
answer
190
views
Is the transpose of an infinite Hadamard matrix also Hadamard?
Let $\omega$ be the set of non-negative integers. If $f,g:\omega\to\{-1,1\}$ are maps, then we say $f,g$ are almost orthogonal if there is a positive integer $C_0\in \omega$ such that for all $n\in\...
- 48.8k
5
votes
2
answers
307
views
Majority voting on $\{0,1\}^\mathbb{Z}$
Motivation. Sometimes in life, people seem to do what the majority of their friends are doing. Do we all become more similar over time? Do we split up into pockets of similarity? This post aims to ...
- 48.8k
10
votes
1
answer
207
views
Generating function for A225114
Let $a(n)$ be A225114 (i.e., number of skew partitions of $n$ whose diagrams have no empty rows and columns).
Let $b(n)$ be an integer sequence with generating function $B(x)$ such that
$$
B(x) = \...
- 4,928
1
vote
1
answer
207
views
A candidate for one-way functions
For every $n \geq 3$ consider a bipartite random $3$-regular graph $G_n$ with two parts $X=\{x_1, \dotsc, x_n\}$ and $Y=\{y_1, \dotsc, y_n\}$. For any $i \leq n$ assign either 0 or 1 to each vertex $...
- 11
1
vote
0
answers
87
views
All matroid polytope is a generalized permutohedron
In many texts, the authors say something like "a matroid polytope lives in the family of generalized permutohedra". We can quickly check the veracity of this claim by describing the matroid ...
- 251
9
votes
1
answer
216
views
Distinct closed walks with $2n$ steps in the $n$-dimensional hypercube
I am interested in finding out what are the shortest closed walks that touch all $n$ dimensions in an $n$-dimensional hypercube. Because they must be closed and they must touch all $n$ dimensions, the ...
- 323
4
votes
1
answer
112
views
On a number of compositions of $n$ into positive triangular numbers
Let $a(n)$ be A023361 (i.e., number of compositions of $n$ into positive triangular numbers). Here
$$
a(n) = \sum\limits_{i \geqslant 1, \frac{i(i+1)}{2}\leqslant n} a(n-\frac{i(i+1)}{2}), \\
a(0) = 1....
- 4,928
0
votes
0
answers
81
views
A generalized permutohedron as the sum of the dilatations of the faces of the standard simplex
I am trying to understand the proof of the statement, specifically it refers to a theorem stated by Postnikov in his text on permutohedra. So, this sentence claims the following:
If $\{Y_I \}$ is a ...
- 251
7
votes
1
answer
439
views
Road map and references for combinatorial Hodge theory
I'm a PhD student. I'm familiar with graduate level algebraic geometry and toric varieties.
I wanted to know a road map for getting into combinatorial Hodge theory and other prerequisites that I'll ...
- 839
1
vote
0
answers
121
views
Simple algorithm for A107670
Let $T(n, k)$ be A107670 (i.e., matrix square of triangle A107667). Here we define the triangular matrix $P$ by $P(n, k) = \frac{(n+1)^{2(n-k)}}{(n-k)!}$ for $0 \leqslant k \leqslant n$ and the ...
- 4,928
20
votes
1
answer
556
views
Almost orthogonal maps $f:\omega \to \{-1,1\}$
Let $\omega$ denote the set of non-negative integers. For sets $A,B$, let $B^A$ denote the set of maps $f:A\to B$. For $f,g\in\{-1,1\}^\omega$ we say that $f,g$ are almost orthogonal if there is $C_0\...
- 48.8k
8
votes
0
answers
260
views
Efficient listing of ASMs
Famously, the alternating sign matrix theorem gives a product formula for the number $a(n)$ of ASMs of size $n$. There are multiple proofs of this formula, all somewhat involved. My question is ...
- 17k
4
votes
1
answer
130
views
Intersecting algorithm for A065601
Let $a(n)$ be A065601 (i.e., number of Dyck paths of length $2n$ with exactly $1$ hill). Here
$$
a(n) = \frac{1}{2(n+1)}((3n-2)a(n-1) + 2(9n-19)a(n-2) + 4(2n-3)a(n-3)), \\
a(0) = a(2) = 0, a(1) = 1.
$$...
- 4,928
2
votes
1
answer
219
views
Existence of a special ordering of the elements of a finite group (II)
Let $G$ be a finite non-abelian group of order $n$. Given $g\in G$ we denote its order by $\mathrm{ord}(g)$.
Consider the group algebra $\mathbb{F}[G]$ for some field $\mathbb{F}$.
Given an ordering $...
- 14.6k
8
votes
2
answers
367
views
Existence of a special ordering of the elements of a finite group
Let $G$ be a finite non-abelian group of order $n$. Given $g\in G$ we denote its order by $\mathrm{ord}(g)$.
Consider the group algebra $\mathbb{F}[G]$ for some field $\mathbb{F}$.
Given an ordering $...
- 14.6k
3
votes
1
answer
168
views
Maximal zero-sum free sequences of $C_3^n$
I am working on the Davenport constant for groups, $D(G)$, which is the minimal number $d$ such that every sequence or multiset of $d$ elements of the group $G$ always contains some non-empty zero-sum ...
6
votes
1
answer
282
views
Integer sequences with a periodic pattern
Let $A$ and $B$ be two different integers. Let $S$ be a finite integer sequence with exactly $n_A$ $A$s and $n_B$ $B$s. By repeating $S$ infinitely many times we obtain an infinite integer sequence $P$...
- 93
5
votes
0
answers
112
views
A strengthening of an inequality for posets by Chan-Pak
Suppose that $P$ is a poset, $x$ and $y$ are two minimal elements of $P$, and that $e(P)$ denotes the number of linear extensions of $P$. Chan and Pak use their recent combinatorial atlas technology ...
- 85.6k
3
votes
1
answer
199
views
Mutually equal Hamming distance of members of ${\cal P}(\mathbb{N})$
This is inspired by an older, as of yet unanswered question.
If $X$ is a set and $A,B\subseteq X$, we let the Hamming distance of $A, B$ be defined as $d_H:=\text{card}\big((A\setminus B)\cup (B\...
- 48.8k
2
votes
0
answers
48
views
Maximum coverage of an orthogonal polygon using $k$ rectangles
I have an orthogonal polygon (all edges are horizontal or vertical) which is convex (no holes in any row of column of the polygon).
I would like to cover as much as possible of this orthogonal polygon ...
- 21
3
votes
0
answers
165
views
Elegant algorithm for A140717
Let $T(n, k)$ be A140717 (i.e., triangle read by rows: $T(n,k)$ is the number of Dyck paths $d$ of semilength $n$ such that sum of peakheights of $d$ - number of peaks of $d$ equals $k$ ($n \geqslant ...
- 4,928
0
votes
0
answers
95
views
Nested Set Permutations and their Enumeration
Let $(S_i)_{i \in \mathbb{N}}$ be a sequence of sets defined recursively as follows:
$S_1 = \{1\}$
$S_{i+1} = S_i \cup \{S_i, i+1\} \quad \forall i \in \mathbb{N}$
A permutation $\sigma$ of $S_i$ is ...
- 1
6
votes
1
answer
218
views
Maximizing the mutual Hamming distance in $\big[{\cal P}([n])\big]^n$
If $X$ is a set and $A,B\subseteq X$ we let the Hamming distance of $A,B$ be defined as $d_H(A,B) = \big|(A\setminus B)\cup(B\setminus A)\big|$. If $\newcommand{\S}{{\cal S}}\S\subseteq {\cal P}(X)$, ...
- 48.8k
2
votes
0
answers
64
views
On a $\sum\limits_{n=0}^{\infty}c_n x^n=\sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n+1}(1-f(k)x^k)$ (slightly different question)
Please note that this question differs from one of the previous questions of mine.
Let $f(n)$ be an arbitrary function with integer values.
Let $c_n$ be an arbitrary integer sequence.
Let $a(n)$ be ...
- 4,928
0
votes
1
answer
98
views
Chromatic tiling complexity and the chromatic number conjecture
Let $T$ be a finite set of tiles in $\mathbb{R}^d$. A tiling of $\mathbb{R}^d$ by $T$ is a collection of disjoint translates of tiles in $T$ whose union is $\mathbb{R}^d$. A tiling is $k$-chromatic if ...
2
votes
1
answer
135
views
Number of permutations that map fixed number of elements between boxes
I would like to count the number of permutations with the following restriction:
I have $N$ objects distributed over $d$ boxes. The boxes are labelled by $a=1,..,d$ and I know the number $n_a$ of ...
- 143
1
vote
0
answers
31
views
On a A347205 and related row polynomials
Let $a(n)$ be A347205. Here
$$
a(2^m(2k+1)) = \sum\limits_{j=0}^{m}a(2^j k), \\
a(0) = 1.
$$
Let $\nu_2(n)$ be A007814 (i.e., number of trailing zeros in the binary expansion of $n$). Here
$$
\nu_2(2n+...
- 4,928
11
votes
1
answer
990
views
Choosing a relative large density subsequence from a low density sequence
My question is somewhere in the interface of combinatorics, probability, and measure theory. It is quite ad-hoc, and I wonder if there is a counter example.
Consider for example the unit interval $[0,...
- 502
2
votes
1
answer
262
views
Randomly fixing elements and transcendence degree
Given $f_1,\ldots,f_n \in \mathbb{F}_q[x_1,\ldots,x_m]$ such that $\deg(f_i) \leq d < q$. Suppose we have for some $1 \leq j \leq m$
$$ \operatorname{trdeg}_{\mathbb{F}(x_1,\ldots,x_j)}\{f_1,\ldots,...
- 341
7
votes
3
answers
707
views
Properties of $P_{n}(x)={e}^{-x}\sum_{k=0}^{\infty}\frac{a_{k,n}{x}^{k}}{k!}$
I know this will sound like a general question, but given the structure $$P_{n}(x)={e}^{-x}\sum_{k=0}^{\infty}\frac{a_{k,n}{x}^{k}}{k!}$$ where $$a_{k,n} = \frac{1}{\prod_{i=1}^{n} (k+2i) }, $$ what ...
0
votes
0
answers
73
views
General solution of partial difference equation that generates Eulerian numbers
I have a question on the partial difference equation
$$f(n+1, k) = (k+1) f(n,k) + (n+1-k)f(n,k-1)$$
where $(k, n) \in \mathbb{Z}^2$.
It is well known, that under some boundary conditions this equation ...
1
vote
0
answers
54
views
Finding a path of given length with maximal relative weight
Let $G$ be a directed graph with vertices $V$ and edges $E \subset V\times V$. A path of length $n \geq 2$ in $G$ is a sequence of vertices $(i_{0},i_{1},\ldots,i_{n-1})$ such that $(i_{k},i_{k+1}) \...
- 798
1
vote
1
answer
198
views
Description of the generalized permutahedron
According to Postnikov, we know that the generalized permutahedron are describe as "polytopes obtained by moving vertices of the usual permutohedron so that directions of all edges are preserved&...
- 251
5
votes
1
answer
168
views
On a generating function and vector $\nu$ of length $n$
Let $f(n)$ be an arbitrary function with integer values.
Let $a(n)$ be an integer sequence such that
$$
\frac{1}{1-x}=\sum\limits_{n=0}^{\infty}a(n)x^n\prod\limits_{k=1}^{n+1}(1-f(k)x)
$$
Start with ...
- 4,928
4
votes
1
answer
85
views
Why does the Athansiadis-Linusson bijection encode floors?
The Athanasiadis-Linusson bijection is a correspondence between dominant regions of the $k$-Shi arrangement (in type A) and $k$-parking functions. I'll take $k=1$ here for convenience here.
Let $V$ be ...
- 525
1
vote
0
answers
44
views
Constrained random sampling from partitioned sets with quotas
Let $D$ be a finite set, $\mathcal{P} = \{D_{i,j}\}_{(i,j) \in I \times J}$ a partition of $D$, $N: J \to \mathbb{N}$ a quota function, and $k \in \mathbb{N}^+$. A subset $F \subseteq D$ is considered ...
- 11
9
votes
0
answers
258
views
On a continued fraction and vector $\nu$ of length $n$
Please note that this question has been completely reworked in order not to overload it with unnecessary and useless information.
Let $f(n)$ be an arbitrary function with integer values.
Let $a(n)$ ...
- 4,928
2
votes
0
answers
43
views
Idempotent suplattice endomorphisms which commute
Let $X$ be a suplattice and let $f, g$ be suplattice endomorphisms of $X$. Suppose $$f \circ f = f$$
$$g \circ g = g$$
$$f \circ g = g \circ f$$
What can we say about $f, g$?
- 591
2
votes
1
answer
110
views
Asymptotic behavior in a modular color-cycling problem
Consider the following problem: We have $k$ rooms, each equipped with a light that cycles through three colors – red, green, and blue – in a cyclic order. Initially, all lights are set to red. Each of ...
0
votes
0
answers
120
views
Is there an existing problem related to inferring a hidden node in a graph from its neighbors
My original question was a bit too ambiguous, so I updated it as follows:
Consider a graph $G=(V,E)$. A vertex in $G$ is chosen uniformly at random; then a neighbor $x$ of $v$ is chosen uniformly at ...
- 109
0
votes
0
answers
35
views
How many colors can an almost-unique subcube cover of a boolean cube have?
Consider a boolean cube $\{0,1\}^n$ and a collection of colored subcubes $\{(C_a, \ell_a)\}_{a \in [N]}$, where $C_a \in \{0,1,*\}^n$ is a subcube and $\ell_a \in \mathbb{N}$ is a color. I will ...
- 231
1
vote
0
answers
63
views
On a A162326 and vector $\nu$ of length $n$
Let $a(n)$ be A162326. Here
$$
a(n) = \frac{1}{n}(2(5n-7)a(n-1) - 9(n-2)a(n-2)), \\
a(0) = a(1) = 1.
$$
Also ordinary generating function is
$$
\frac{5 - \sqrt{\frac{1-9x}{1-x}}}{4}.
$$
Let $b(n)$ be $...
- 4,928
1
vote
1
answer
102
views
Multiplicities and double and triple tensor products of simple $\frak{g}$-modules
Given a complex simple Lie algebra $\frak{g}$ and a simple module $V_{\lambda}$ for some dominant weight $\lambda$. Consider the tensor product decomposition
$$
V_{\lambda} \otimes V_{\lambda} \simeq ...
- 419
4
votes
1
answer
182
views
Permutations of the natural numbers with a common conditionally convergent series
Let $S\subset S_{\infty}$ be a set of permutations of $\mathbb{N}$. A real series $\sum_{n\geq0}u_{n}$ will be called $S$-conditionally convergent if it is absolutely divergent and if, for all $\sigma\...
- 105
2
votes
0
answers
124
views
Symmetric matching in special graphs
Let $G$ be a bipartite graph, $L$ ($R$) be the set of vertices in the left (right) part.
Consider a graph $T$ with the set of vertices $R \times L$ ( $L \times R$ ) in the left (right) part. For any $...
1
vote
0
answers
41
views
Unexpected non-uniformity of results from some implementations of Jacobson-Matthews seem to show a strange sensitivity to isotopy class
Questions
Why do some Jacobson-Matthews (J-M) implementations for generating random latin squares exhibit frequencies inconsistent with an underlying uniform distribution?
Further investigation ...
- 41
2
votes
0
answers
187
views
Matrix with elementary symmetric polynomials as entries
Let $n\geq 1$, and for each $j=1,\ldots, n+1$ let $\mathbf{X}_{j}=(X_{j1},\ldots, X_{jn})$ be $n$ variables. Let $M$ be the $(n+1)\times (n+1)$ matrix whose $(i,j)$-th entry is $$M_{ij}=(-1)^i e_{i-1}(...
4
votes
1
answer
406
views
Inverse relationship between Stirling numbers of the first and second kind via generating functions
In combinatorics, a well-known result is that the matrix formed by the Stirling numbers of the second kind $\left(S(n,k)\right)_{n,k\geq 0}$ and the matrix of the signed Stirling numbers of the first ...
- 151