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,566
questions
6
votes
2
answers
266
views
Expectation of period length of functions $f:\{1,\ldots,n\}\to \{1,\ldots,n\}$
For $n\in\mathbb{N}$, let $[n]:= \{1,\ldots,n\}$. Let $\text{Fun}(n)$ denote the set of all functions $f:[n]\to[n]$. To $f\in\text{Fun}(n)$ associate a sequence $\text{seq}(f))$ defined recursively by
...
- 22.9k
2
votes
0
answers
58
views
Tail asymptotics of Durfee square identity
This post is related to the problem Asymptotics of a combinatorial series
According to the Durfee square identity:
$$\sum_{k \ge 0} \frac{q^{k^2}}{(q;q)_k^2} (q;q)_{\infty} = 1,$$
where $(q;q)_k$ is ...
- 51
1
vote
0
answers
36
views
Problem concerning cutting of 2n*2n square into 2 equal area connected figures using various cuts without self crossings
We have a square 2n*2n, where n belongs to N. The main problem is to find how many different equal area connected figures could be produced by cuttings without self-crossings. The orientability of the ...
- 11
2
votes
1
answer
148
views
Directed version of this lemma
On a paper by Shoham Letzter, available Here, there's a lemma that says as follows:
Lemma 0: For every graph $G$, there exist two disjoint sets $U,W\subseteq V(G)$ of equal size, such that there are ...
- 1,666
2
votes
0
answers
296
views
Higher order Leibniz rule and ordered multiindex notation
Although I think this is probably known, I am making here a short exposition on the multiindex notations I am using to make this question self-contained. I note that there is at least two different ...
- 2,612
2
votes
1
answer
140
views
Min-sum and min-max node-disjoint path problems
Given an undirected weighted graph, we seek a pair of node-disjoint path between $2$ nodes $s$ and $t$: if the objective is to minimize the total path cost, the Suurballe algorithm can be applied; now ...
- 436
2
votes
0
answers
129
views
Distinguishable knots (with constraints) over polyhedra
I'm trying to find the number of distinguishable knot projections over certain convex regular polyhedra according to the following constraints. On each face on the polyhedron the knot will have a ...
- 2,518
7
votes
1
answer
504
views
Packing equal-size disks in a unit disk
Inspired by the delicious buns and Siu Mai in bamboo steamers I saw tonight in a food show about Cantonese Dim Sum, here is a natural question. It probably has been well studied in the literature, but ...
- 5,169
0
votes
0
answers
265
views
Is there a permutation $\tau\in S_n$ with $\tau(1)^{\tau(2)}+\cdots+\tau(n-1)^{\tau(n)}+\tau(n)^{\tau(1)}$ a square?
Let $n>1$ be an integer, and let $S_n$ be the symmetric group of all the permutatins of $\{1,\ldots,n\}$.
I'm curious whether there is a permutation $\tau\in S_n$ such that
$$\tau(1)^{\tau(2)}+\...
- 14.5k
2
votes
1
answer
161
views
Low-Hamming weight vectors in low-dimensional subspaces of $\mathbb{F}_p^n$
What is the maximum number vectors of Hamming weight at most $w$ in a $d$-dimensional subspace of $\mathbb{F}_p^n$, where $w,d,p$ are constant and $p$ is odd. (The Hamming weight is the number of ...
- 103k
5
votes
3
answers
595
views
Convergence speed of a random dyadic rational generator
We are given a multiset $M$ of real numbers which initially is equal to $\{0,1\}$. In a sequential fashion, at each round $r\in\mathbb{N}$
two distinct instances $x_r$ and $y_r$ of $M$'s numbers are ...
- 3,809
1
vote
0
answers
196
views
Finding a tree with adjacency matrix near a given matrix
For defining a distance between trees, one can code them into $\mathbb{R}^n$ and use norms in $\mathbb{R}^n$ as distance. (For example we can use adjacency matrices as a tool for this coding) After ...
- 119
1
vote
1
answer
105
views
Almost-parallel corners of the hypercube in high dimensions
Say I would like a collection of k "almost-parallel" boolean vectors $X_1,...,X_k \in \{\pm 1\}^n$, such that $(X_i,X_j)/n \approx 1-\epsilon$ for some small $\epsilon$. How many ways are ...
- 30k
2
votes
2
answers
176
views
growth of the permanent of some band matrix
Consider such special band matrix of dimension $n$. It is a $0-1$ matrix, and only the first few diagonals are nonzero. Specifically,
$$ H_{ij} = 1 $$
if and only if $|i-j| \leq 2$.
How does the ...
- 16.2k
3
votes
0
answers
94
views
When is it possible to extend several linear orders defined "locally" into a single linear order defined "globally"?
This is a somewhat fuzzy question, so I will try my best to give a formulation which includes everything relevant while excluding everything else. I would like to find out if anyone else has studied ...
- 183
1
vote
1
answer
68
views
"Circuit rank" but for vertices
A graph's circuit rank is the minimum number of edges that have to be removed for the graph to become a tree or forest. Is there a term that represents the minimum number of vertices that we must ...
- 5,563
2
votes
1
answer
405
views
Expansion in hypergraphs
Is there a useful concept of expansion in hypergraphs, generalizing the concept for graphs (see: expander graphs)?
Of course, expander graphs can be characterized in several qualitatively equivalent ...
- 19.4k
2
votes
1
answer
202
views
Changing $S_2 \wr S_n$ for $S_n \wr S_2$ in the theory of zonal polynomials
The permutation group $S_{2n}$ has $H_{2,n}=S_2\wr S_n$ as a subgroup. The plethysm $h_n(h_2)=\sum_{\lambda\vdash n}s_{2\lambda}$ is well known.
The zonal spherical functions $\omega_\lambda(g)=\frac{...
- 49.5k
2
votes
0
answers
148
views
Square root of a function on a finite set
Let $S$ be a finite set and $f \colon S \to S$ be an arbitrary function. How can we find all functions $g \colon S \to S$ with $f = g \circ g$?
If $f$ and $g$ are both required to be invertible, the ...
- 2,758
2
votes
2
answers
301
views
sum of odious numbers to the power of k
In number theory, an odious number is a positive integer that has an odd number of $1$s in its binary expansion.
The first odious numbers are:
$1, 2, 4, 7, 8, 11, 13, 14, 16, 19, 21, 22, 25, 26, 28, ...
- 60.4k
3
votes
0
answers
114
views
Asymptotics of a combinatorial series
I am interested in the exact asymptotics of the following combinatorial series (which arises from the study of a Markov chain):
$$F(q):=\sum_{k \ge 1} \frac{q^{k^2}}{(q;q)_k^2}\quad \mbox{as } q \to 1^...
- 51
7
votes
0
answers
1k
views
Example of a group with unsolvable word problem
Today I noticed that the last relator in the 27-relator presentation
of a group with unsolvable word problem given in
Donald J. Collins: A simple presentation of a group with unsolvable word problem.
...
- 185
3
votes
0
answers
78
views
Size of the kernel (minimal ideal) of a finite semigroup
Let $A$ be an irreducible nonnegative $N\times N$ integer matrix with constant row sum $D$. Let $A_1, \dots, A_D$ be nonnegative integer matrices, each with constant row sum $1$, such that $\sum_k A_k ...
- 675
6
votes
0
answers
84
views
Can a spherical simplicial complex have more than one "central" inversion?
Let $\Delta$ be a finite connected simplicial complex. Call a simplicial map $\phi:\Delta\to\Delta$ an inversion if
$\phi$ is an involution, that is $\phi\circ\phi=\mathrm{id}$, and
$\phi$ is not ...
- 12.6k
1
vote
2
answers
275
views
In search of a combinatorial proof for a multinomial sum
There is this sequence listed on OEIS - named Domb numbers. I'm curious about
QUESTION. Is there a direct combinatorial proof for the identity
$$\sum_{k=0}^n\binom{n}k^2\binom{2k}k\binom{2n-2k}{n-k}
=...
- 1,755
-1
votes
1
answer
110
views
Path sequences and isomorphism of graphs
Let $G=(V,E)$ be a finite, simple, undirected graph. For each $v\in V$ we define the path sequence $\text{ps}^G_v: \omega\to \omega$ where $\text{ps}_v(n)$ is the number of vertices that can be ...
- 11.9k
3
votes
1
answer
281
views
Finite sum with falling factorial
I need to evaluate the following finite sum:
$$
\sum_{j=0}^{h}(-1)^j\binom{h}{j}(jx)_{k},\qquad k\geq h,\, x\in\mathbb{R}^{+}
$$
and
$$
(jx)_{k}=jx(jx-1)\cdots(jx-k+1)
$$
is the falling factorial. Any ...
- 16.2k
6
votes
0
answers
146
views
Distribution of iid hypergeometric random variables conditioned on the sum
Let $X_1,X_2,\ldots,X_n$ be iid random variables with hypergeometric distribution. To be specific,
$$ \mathrm{Prob}(X_1=i) = \frac{\binom{N}{i}\binom{M-N}{m-i}}{\binom{M}{m}}.$$
Let $S=X_1+\cdots+X_n$....
- 37.2k
1
vote
0
answers
37
views
Growth of the number of columns $j=1,\dotsc,p$ such that $\|Ae_j\|_1 > p^\alpha$ for symmetric $A$ with bounded spectrum?
Consider the set $\mathcal S(p)$
of symmetric matrices $A$ of size $p\times p$
with bounded spectrum, say, $\lVert A\rVert_\text{op}\le 10$ and $\lVert A^{-1}\rVert_\text{op}\le 10$.
Let $\alpha>0$ ...
- 11.4k
4
votes
2
answers
2k
views
Regular graph colorings
[Since I didn't get any feedback at MSE, I dare to post this question here, too.]
Call a coloring $C:V(G) \rightarrow \lbrace 1,\dots,n \rbrace$ of a graph $G$ regular when every vertex with color $...
- 2,758
2
votes
0
answers
143
views
Maximum number of intersecting subsets with size at most k
My question is assume that we have a set with $n\geq 2k$ elements and we want to find the maximal number of pairwise intersecting subsets of $[n]$ with at most $k$ elements?
- 21
5
votes
2
answers
514
views
Smallest $3$-regular graph with a unique perfect matching
What is the smallest 3-regular graph to have a unique perfect matching?
With a large enough number of nodes, it is possible for a 3-regular graph to have no perfect matching (example can be seen in ...
- 1,424
4
votes
1
answer
191
views
Can't lower bound be improved on number of light edges in planar graph with minimum degree five?
Let an $i$-vertex be a vertex of degree $i$. Let an $i, j-$ edge be an edge joining an $i-$vertex to
a $j-$vertex. Given a plane graph G, let $e_{i,j}$ be the number of $i, j-$edges of $G$.
I found ...
- 68
3
votes
0
answers
502
views
vector version of subset sum
Given a set of vectors $V = \{v_1, v_2, \cdots, v_n\}, v_i \in \mathbb{Z}^2$.
Given a query $\vec{C} = (c_1, c_2), c_i \in \mathbb{Z}$, how can one quickly verify whether if there exists a subset $ S\...
- 183
1
vote
0
answers
48
views
Inequality between union-closed families of sets and corresponding upward-closed families
This question is about an inequality for union-closed families of sets related to Frankl's conjecture and a result by Reimer. It relates the union-closed families and corresponding upward-closed ...
- 1,085
4
votes
0
answers
203
views
Dimension of a certain space of symmetric functions: Part I
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. A partition $\lambda$ is called a $t$-core if none of its hook lengths are multiples of $t$.
QUESTION. Consider the ...
- 41.8k
2
votes
1
answer
146
views
Equal subset-sums of bounded vectors
Let $S\subseteq \{0,\ldots,n\}^d$ be a set of $d$-dimensional vectors of with bounded, natural, coordinates.
We are given that
$$v'+v_1+\ldots+v_t=u'+u_1+\ldots+u_s$$
where $v_1,\ldots,v_t,u_1,\ldots,...
- 103k
2
votes
1
answer
324
views
Best known upper bound for the Ramsey function $R(k,x)$
The Ramsey function $R(k,x)$ is defined as the minimal integer $n$ such that any graph on $n$ vertices contains either a clique of size $k$ or an independent set of size $x$. Miklós Ajtai, János ...
- 97
1
vote
0
answers
90
views
Dimension of a certain space of symmetric functions: Part II
This is the second installment of my earlier MO question.
Let $s_{\lambda}$ denote the Schur polynomial associated to a partition $\lambda$. Denote the set of all partitions with distinct parts by $\...
- 41.8k
2
votes
1
answer
144
views
Lower bound of the probability of singular random matrix over $\{\pm1\}$ in ``Singularity of random Bernoulli matrices"
Suppose $M_{n}$ is an $n \times n$ matrix with independent ±1 entries. Recent breakthrough shows that the probability $\mathbb{P}(M_{n} \text{ is singular})$ is
$$(1) \quad\quad\qquad \mathbb{P}(M_{n} ...
- 9,195
4
votes
1
answer
296
views
On the real and finite field rank of a $0/1$ matrix - I
Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$.
Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\...
- 1,432
1
vote
0
answers
83
views
On the real and finite field rank of a $0/1$ matrix - II
Let $M\in\{-\ell,\dots,-1,0,+1,\dots,+\ell\}^{n\times n}$ be a matrix of rank $r$ where $\ell\geq1$ such that there is a permutation matrix in $\{0,1\}^{m\times m}$ of order $2\ell$.
Fix a permutation ...
- 13.7k
4
votes
1
answer
377
views
Identity involving binomial coefficients and partitions
Working on a problem in the symmetric group I have stumbled upon the following equation:
$$\sum_{\substack{\pi=(1^{c_1},2^{c_2},\ldots,n^{c_n})\\\textrm{partition of }n}}(-1)^{n-\sum_{i=1}^nc_i}\frac{...
- 103k
2
votes
0
answers
44
views
Which edges to delete from cubic graphs to get good cycle covers?
Let $G\left(V,E\subset V\times V,\omega: V\supset \lbrace u,v\rbrace\mapsto w_{uv}\in\mathbb{R}\right);\ \left|e_{uv}\right|:=\omega_{uv}\quad$ be a cubic symmetric graph that contains a vertex-...
- 2,758
2
votes
1
answer
742
views
Is there a term for a subgraph which includes all the edges of a graph?
A subgraph is called spanning when it includes all of the vertices of the given graph.
Is there a term for a subgraph which includes all the edges of a graph?
Thanks.
- 1,424
6
votes
1
answer
416
views
What is the Möbius function of substrings?
Define a poset on the set of all finite binary strings, defined by $a \le b$ whenever $b = uav$ for (possibly empty) binary strings $u, v$.
What is the Möbius function of this poset?
- 33.2k
8
votes
1
answer
382
views
Largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$?
What is known about the largest set of $k$-wise linearly independent vectors in $\mathbb F_q^n$? I am especially interested when $q=2$, and in the regime where $k$ is fixed an $n\to\infty$. Here are ...
- 415
1
vote
1
answer
135
views
Extensions of combinatorially equivalent hyperplane arrangements
Let $A_1,A_2\subset \mathbb{C}^n$ be hyperplane arrangements with equivalent intersection lattices $L(A_1)\cong L(A_2)$. If $A_1\subset B_1$, where $B_1$ is third hyperplane arrangement, does there ...
- 22.9k
2
votes
0
answers
87
views
Is every graph a generalized strict unit distance graph?
A strict unit-distance graph is a graph which can be constructed from a collection of points in the Euclidean plane by connecting pairs of vertices with edges if and only if they have unit distance. ...
- 2,689
7
votes
2
answers
585
views
On a matrix problem in the field $\mathbb F_2$
Given $M$ a symmetric matrix in $\mathbb F_2^{n\times n}$ having $\mathsf{det}_\mathbb R(M)\neq0$ (non-singular in reals) and satisfying $PMP'=(M+J+I)$ or $P(M+J+I)P'=M$ where $P$ is a permutation ...
- 42.8k