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.
1,476
questions
146
votes
66
answers
38k
views
Important formulas in combinatorics
Motivation:
The poster for the conference celebrating Noga Alon's 60th birthday, fifteen formulas describing some of Alon's work are presented. (See this post, for the poster, and cash prizes offered ...
49
votes
6
answers
10k
views
Generating finite simple groups with $2$ elements
Here is a very natural question:
Q: Is it always possible to generate a finite simple group with only $2$ elements?
In all the examples that I can think of the answer is yes.
If the answer is ...
- 7,521
118
votes
15
answers
97k
views
Sum of 'the first k' binomial coefficients for fixed $N$
I am interested in the function $$f(N,k)=\sum_{i=0}^{k} {N \choose i}$$ for fixed $N$ and $0 \leq k \leq N $. Obviously it equals 1 for $k = 0$ and $2^{N}$ for $k = N$, but are there any other ...
- 1,258
20
votes
8
answers
13k
views
Lower bound for sum of binomial coefficients?
Hi! I'm new here. It would be awesome if someone knows a good answer.
Is there a good lower bound for the tail of sums of binomial coefficients? I'm particularly interested in the simplest case $\...
- 233
18
votes
3
answers
2k
views
Guises of the Stasheff polytopes, associahedra for the Coxeter $A_n$ root system?
Richard Stanley keeps a famous running compilation of different guises of the celebrated Catalan numbers. The number of vertices of the associahedron is one instantiation among the multitude, and the ...
- 9,931
13
votes
2
answers
2k
views
Riemann zeta function at positive integers and an Appell sequence of polynomials related to fractional calculus
I was exploring some raising and lowering operators related to an infinitesimal generator for fractional integro-derivatives and found an Appell sequence of polynomials, i.e., an infinite sequence of ...
- 9,931
9
votes
1
answer
791
views
Combinatorics for the action of Virasoro / Kac–Schwarz operators: partition polynomials of free probability theory
In the background sections below, I establish the relations among characterizations of the action of Virasoro / Kac–Schwarz operators of 2D gravity models presented in terms of Laurent series by ...
- 9,931
46
votes
8
answers
5k
views
Can a problem be simultaneously polynomial time and undecidable?
The Robertson-Seymour theorem on graph minors leads to some interesting conundrums.
The theorem states that any minor-closed class of graphs can be described by a finite number of excluded minors. As ...
- 12.3k
57
votes
3
answers
5k
views
Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$
Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?
- 887
47
votes
6
answers
5k
views
True by accident (and therefore not amenable to proof)
The graph reconstruction conjecture claims that (barring trivial examples) a graph on n vertices is determined (up to isomorphism) by its collection of (n-1)-vertex induced subgraphs (again up to ...
- 12.3k
11
votes
1
answer
2k
views
Cycling through the Zeta Garden: Zeta functions for graphs, cycle index polynomials, and determinants
Zeta functions abound in mathematics. Audrey Terras describes in Zeta Functions and Chaos three zeta functions--the zeta fct. of a projective non-singular algebraic variety; the Artin-Mazur zeta ...
- 9,931
32
votes
0
answers
3k
views
Vertex coloring inherited from perfect matchings (motivated by quantum physics)
Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question.
Added (25.12.2020): I made a youtube video to explain the question in detail.
...
- 155
13
votes
2
answers
978
views
Number of commuting pairs (triples, n-tuples) in GL_n(F_q) (and other groups)?
Question 1 What is the number of pairs of commuting elements in GL_n(F_q) ?
I am aware of many results concerning commuting elements in Mat_n(F_q), but I am interested in GL i.e. non-degenerate ...
12
votes
4
answers
5k
views
Estimating a partial sum of weighted binomial coefficients
There is a well-known estimate for the sum of all binomial coefficients $\binom{n}{k}$ satisfying $k \leq \alpha n$ for some $\alpha$ satisfying $0 < \alpha \leq 1/2$:
$$ \sum_{k=0}^{\alpha n}\...
- 491
20
votes
1
answer
556
views
$q$-(and other)-analogs for counting index-$n$ subgroups in terms of Homs to $S_n$?
The following formula of astonishing beauty and power (imho):
$$ \sum_{n \ge 0} \frac{| \mathrm{Hom}(G,S_n) | }{n! } z^n = \exp\left( \sum_{n \ge 1} \frac{|\text{Index}~n~\text{subgroups of}~ G|}nz^...
18
votes
3
answers
6k
views
Number of unique determinants for an NxN (0,1)-matrix
I'm interested in bounds for the number of unique determinants of NxN (0,1)-matrices. Obviously some of these matrices will be singular and therefore will trivially have zero determinant. While it ...
- 359
7
votes
1
answer
722
views
Difference Sets
Suppose
$$
P \subseteq \{1,2,\dots,N\},\quad |P| = K
$$
We calculate the differences as: $$d=p_i-p_j\mod N,\quad i\ne j$$
Now let $a_d$ denote the number of occurrence of $d$ (for $d = 1, 2, \dots , N ...
- 123
7
votes
0
answers
563
views
Guises of the noncrossing partitions (NCPs)
From "Noncrossing partitions in surprising locations" by Jon McCammond:
Certain mathematical structures make a habit of reoccuring in the most diverse list of settings. Some obvious ...
- 9,931
79
votes
6
answers
4k
views
Does every polyomino tile R^n for some n?
This is a question posed by Adam Chalcraft. I am posting it here because I think it deserves wider circulation, and because maybe someone already knows the answer.
A polyomino is usually defined to ...
- 78.3k
35
votes
5
answers
4k
views
Cliques, Paley graphs and quadratic residues
A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...
- 703
21
votes
4
answers
3k
views
Can you determine whether a graph is the 1-skeleton of a polytope?
How do I test whether a given undirected graph is the 1-skeleton of a polytope?
How can I tell the dimension of a given 1-skeleton?
- 9,628
17
votes
3
answers
709
views
Automated search for bijective proofs
In enumerative combinatorics, a bijective proof that $|A_n| = |B_n|$ (where $A_n$ and $B_n$ are finite sets of combinatorial objects of size $n$) is a proof that constructs an explicit bijection ...
- 78.3k
16
votes
2
answers
1k
views
A combinatorial interpretation for $n$-ary trees for negative $n$
The ordinary generating function $T_n=T_n(x)$ for the $n$-ary trees satisfies the functional equation
$$
T_n=1+xT_n^n.
$$
This is usually defined for $n\ge 0$, but the functional equation can be ...
- 1,170
16
votes
6
answers
1k
views
A Leibniz-like formula for $(f(x) \frac{d}{dx})^n f(x)$?
Let $f(x)$ be sufficiently regular (e.g. a smooth function or a formal power series in characteristic 0 etc.). In my research the following recursion made a surprising entrance
$$
f_1(x) = f(x),\ f_{n+...
- 6,708
15
votes
2
answers
808
views
What are the periodic Dyck paths?
I changed the thread completely so that everything is now elementary linear algebra.
A Dyck path of length $n$ is a list of positive integers $[c_1,c_2,...,c_n]$ with $c_i -1 \leq c_{i+1}$ for all $i$...
- 26.1k
14
votes
1
answer
758
views
Is there a lift of the q-Vandermonde identity to some geometric (motivic) identity for Grassmannians over $F_q$?
The q-Vandermonde identity reads:
$$ \binom{m + n}{k}_{\!\!q} =\sum_{j} \binom{m}{k - j}_{\!\!q} \binom{n}{j}_{\!\!q} q^{j(m-k+j)} $$
The q-binomial coefficients:
$$ \binom{ a }{ b}_{\!\!q} $$
...
14
votes
2
answers
1k
views
The Simultaneous Conjugacy Problem in the symmetric group $S_N$
We are interested in the following notions in the case $G=S_N$, the symmetric group on
$\{1,\dots,N\}$.
Fix a group $G$ and a number $d$. For $(g_1,\dots,g_d)\in G^d$ and $x\in G$, define
$$(g_1,\...
- 3,104
10
votes
1
answer
3k
views
maximum size of intersecting set families
Suppose $n$ is a big number and $k\geq 2$. How many sets $S_1,\dots,S_m\subset [n]$ can we find such that
(1) $|S_i| = k$ for all $i$,
(2) $|S_i\cap S_j| \leq 1$ for all $i\ne j$.
What's the maximum ...
- 620
10
votes
4
answers
1k
views
Meaning of a quote of Doubilet, Rota and Stanley on harmonic analysis and combinatorics
The beginning of the paper On the foundations of combinatorial theory. VI. The idea of generating function (1972) says that
Since Laplace discovered the remarkable correspondence between set ...
- 489
9
votes
2
answers
662
views
Сlosed formula for $(g\partial)^n$
The objective is to obtain a closed formula for:
$$
\boxed{A(n)=\big(g(z)\,\partial_z\big)^n,\qquad n=1,2,\dots}
$$
where $g(z)$ is smooth in $z$ and $\partial_z$ is a derivative with respect to $z$.
...
- 277
7
votes
1
answer
839
views
Bound for largest eigenvalue of symmetric matrices of uniform random variables over $[0,1]$ and fixed $1$s along diagonal and scattered $1$s
Given a $n\times n$ symmetric random matrix whose diagonal elements are all fixed as $1$. In addition, there are $k$ $1$s will be randomly scattered in upper triangular (of course, the corresponding ...
- 272
3
votes
1
answer
531
views
Counting "connected" edge orderings (shellings) of the complete graph [duplicate]
This question is inspired by "Number of collinear ways to fill a grid" by Sebastien Palcoux and the comments of user44191 on this earlier question of Palcoux's.
Let $G=(V,E)$ be a graph. An edge ...
- 13.5k
80
votes
10
answers
9k
views
Existence of a zero-sum subset
Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes:
Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...
- 85.1k
54
votes
2
answers
8k
views
Walsh Fourier transform of the Möbius function
This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly orthogonal to Morse
August Ferdinand Möbius (November 17, 1790 – ...
47
votes
2
answers
4k
views
Collapsible group words
What is the length $f(n)$ of the shortest nontrivial group word $w_n$ in $x_1,\ldots,x_n$ that collapses to $1$ when we substitute $x_i=1$ for any $i$?
For example, $f(2)=4$, with the commutator $[...
- 23.6k
46
votes
7
answers
6k
views
What is an explicit bijection in combinatorics?
A standard way of demonstrating that two collections of combinatorial objects have the same cardinality is to exhibit a bijection between them. Browsing through some examples (here, there, yonder) ...
- 48k
45
votes
5
answers
5k
views
Integer-valued factorial ratios
This historical question recalls
Pafnuty Chebyshev's estimates for the prime distribution function. In his derivation
Chebyshev used the factorial ratio sequence
$$
u_n=\frac{(30n)!n!}{(15n)!(10n)!(6n)...
- 13.4k
39
votes
5
answers
3k
views
Does there exist a comprehensive compilation of Erdos's open problems?
Fan Chung and Ron Graham's book Erdos on Graphs: His Legacy of Unsolved Problems (A. K. Peters, 1998) collects together all of Erdos's open problems in graph theory that they could find into a single ...
- 78.3k
35
votes
5
answers
3k
views
Small simplicial complexes with torsion in their homology?
Fix a prime $p$. What is the smallest integer $n$ so that there is a simplicial complex on $n$ vertices with $p$-torsion in its homology?
For example, when $p=2$, there is a complex with 6 vertices (...
- 4,146
33
votes
4
answers
3k
views
Is it possible to define higher cardinal arithmetics
In number theory there are several operators like addition, multiplication and exponentiation defined from $\omega\times\omega$ to $\omega$. Each of them is defined as an ...
26
votes
3
answers
2k
views
Kasteleyn's formula for domino tilings generalized?
It seems a marvel when a bunch of irrational numbers "conspire" to become rational, even better an integer. An elementary example is $\prod_{j=1}^n4\cos^2\left(\pi j/(2n+1)\right)=1$.
Kasteleyn's ...
- 41.8k
24
votes
6
answers
2k
views
Number of collinear ways to fill a grid
A way to fill a finite grid (one box after the other) is called collinear if every newly filled box (the first excepted) is vertically or horizontally collinear with a previously filled box. See the ...
23
votes
5
answers
1k
views
Sequences with integral means
Let $S(n)$ be the sequence whose first element is $n$, and from then onward,
the next element is the smallest natural number ${\ge}1$ that ensures that the
mean of all the numbers in the sequence is ...
- 149k
21
votes
3
answers
2k
views
Products of Conjugacy Classes in S_n
The conjugacy classes of the permutation group $S_n$ are indexed by partitions like $[6]$ and $[2,2,2] = [2^3]$ describing the cycle type. What happens when you take products of two whole conjugacy ...
- 22.6k
20
votes
2
answers
1k
views
Euler numbers and permanent of matrices
Motivated by Question 402249 of Zhi-Wei Sun, I consider the permanent of matrices
$$e(n)=\mathrm{per}\left[\operatorname{sgn} \left(\tan\pi\frac{j+k}n \right)\right]_{1\le j,k\le n-1},$$
where $n$ is ...
- 844
18
votes
2
answers
1k
views
Explicit invariant of tensors nonvanishing on the diagonal
The group $SL_n \times SL_n \times SL_n$ acts naturally on the vector space $\mathbb C^n \otimes \mathbb C^n \otimes \mathbb C^n$ and has a rather large ring of polynomial invariants. The element $$\...
- 137k
18
votes
1
answer
872
views
Two conjectures about zero inner products and dissociated sets
The following problems come from something I worked on (with my coauthors) related to proving a new time lower bound for streaming problems. Having worked on these problems for some time with little ...
- 3,195
17
votes
1
answer
474
views
Irreducibility of root-height generating polynomial
The height $ht(\alpha)$ of a positive root $\alpha$ in a (finite, crystallographic) root system $\Phi$ is $\sum_{i=1}^n c_i$ where $\alpha = \sum_{i=1}^n c_i \alpha_i$ is its decomposition as a sum of ...
- 2,693
14
votes
1
answer
613
views
A Schur positivity conjecture related to row and column permutations
The problem Counting cycles after permuting within rows and columns reminds me of the
following unpublished conjecture of mine. Let $D$ be any finite
planar diagram (in the sense of Young diagram, ...
- 49.5k
12
votes
1
answer
598
views
Order polynomial of shifted double staircase
This question is related to my earlier question looking for posets with product formulas for their order polynomials.
Recall that the order polynomial $\Omega_P(m)$ of a finite poset $P$ is defined ...
- 22.9k