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.
922
questions
113
votes
61answers
24k 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 ...
17
votes
7answers
9k 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 $\...
80
votes
11answers
59k 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 ...
40
votes
6answers
6k 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 ...
10
votes
2answers
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 ...
47
votes
3answers
4k 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)$?
18
votes
3answers
4k 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 ...
10
votes
1answer
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 ...
7
votes
1answer
667 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 ...
34
votes
5answers
3k 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 ...
17
votes
4answers
2k 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?
20
votes
1answer
1k views
Vertex coloring inherited from perfect matchings (motivated by quantum physics)
Added (24.08.2019): As I consider this question important for quantum physics, I have announced a 3000 Euro award on its solution, see here for more details.
Added (19.09.2019): This problem can be ...
14
votes
1answer
481 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} $$
...
13
votes
2answers
765 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 ...
8
votes
3answers
3k 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}\...
7
votes
1answer
386 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 ...
70
votes
6answers
3k 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 ...
23
votes
1answer
813 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 ...
20
votes
3answers
1k 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 ...
15
votes
3answers
1k 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 ...
29
votes
4answers
2k 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 ...
13
votes
2answers
832 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,\...
20
votes
1answer
399 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^...
9
votes
4answers
6k views
Mean minimum distance for N random points on a unit square (plane)
A previously posted question "mean minimum distance for N random points on a one-dimensional line" produced an elegant answer: for a line of length L, the expected minimum distance (between random ...
22
votes
3answers
726 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 ...
15
votes
2answers
849 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 $$\...
3
votes
0answers
168 views
Metrics on finite groups and generalizations of central limit theorems for balls volumes (à la Diaconis-Graham)
In wonderful lectures by P. Diaconis "Group representations in probability and statistics, Chapter 6. Metrics on Groups, and Their Statistical Use" metrics on permutation groups are considered and ...
8
votes
1answer
269 views
Loday's characterization and enumeration of faces of associahedra (Stasheff polytopes)
From "The multiple facets of the associahedra" by Loday:
Let us consider the formal power series
$$f(x) = x+a_1 x^2 +a_2 x^3 + \cdots+ a_n x^{n+1} + \cdots$$
and let
$$ g(x) = x+b_1 ...
4
votes
1answer
288 views
Is there an integral fusion ring which is not of Frobenius type?
Combinatorially, a fusion ring $\mathcal{F}$ is nothing but a finite set $B=\{b_1, \dots, b_r\}$ (generating the $\mathbb{Z}$-module $\mathbb{Z} B$) together with fusion rules: $$ b_i \cdot b_j = \...
4
votes
1answer
958 views
The property of Kendall-Mann numbers
The sequence A000140 is studied
http://oeis.org/A000140
(Kendall-Mann numbers: the maximum number of permutations on n letters having the same number of inversions )
and I am looking for a proof ...
98
votes
5answers
7k views
integral of a “sin-omial” coefficients=binomial
I find the following averaged-integral amusing and intriguing, to say the least. Is there any proof?
For any pair of integers $n\geq k\geq0$, we have
$$\frac1{\pi}\int_0^{\pi}\frac{\sin^n(x)}{\...
43
votes
15answers
8k views
Strengthening the Induction Hypothesis
Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This ...
62
votes
6answers
6k views
How to recognise that the polynomial method might work
A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let $(a_1,b_1),\dots,(...
43
votes
4answers
4k 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)...
36
votes
5answers
4k views
Groups, quantum groups and (fill in the blank)
In the study of special functions there are three levels of objects, classical, basic and elliptic. These correspond to classical hypergeometric functions, basic (q-) hypergeometric functions, and ...
29
votes
2answers
8k views
Mean minimum distance for N random points on a one-dimensional line
Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. I was wondering if there was a simple/straightforward method (not involving long ...
20
votes
6answers
8k views
A balls-and-colours problem
A box contains n balls coloured 1 to n. Each time you pick two balls from the bin - the first ball and the second ball, both uniformly at random and you paint the second ball with the colour of the ...
47
votes
2answers
7k 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
!
Harold Calvin Marston Morse (24 March ...
26
votes
5answers
7k views
Erdos Conjecture on arithmetic progressions
Introduction:
Let A be a subset of the naturals such that $\sum_{n\in A}\frac{1}{n}=\infty$. The Erdos Conjecture states that A must have arithmetic progressions of arbitrary length.
Question:
I ...
18
votes
10answers
4k views
Applications of infinite Ramsey's Theorem (on N)?
Finite Ramsey's theorem is a very important combinatorial tool that is often used in mathematics. The infinite version of Ramsey's theorem (Ramsey's theorem for colorings of tuples of natural numbers) ...
26
votes
3answers
4k views
Is the sum $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0?$
I am trying to prove $\sum\limits_{j=0}^{k-1}(-1)^{j+1}(k-j)^{2k-2} \binom{2k+1}{j} \ge 0$. This inequality has been verified by computer for $k\le40$.
Some clues that might work (kindly provided by ...
27
votes
5answers
2k 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 (...
22
votes
6answers
3k 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 ...
17
votes
5answers
1k 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 ...
36
votes
2answers
2k views
A question on maps from $\mathbb{Z}/p\mathbb{Z}$ to itself
Let $p\geq 3$ be a prime number, and let $u:\mathbb{Z}/p\mathbb{Z}\to \mathbb{Z}/p\mathbb{Z}$ be a map such that, for all $l\in \mathbb{Z}/p\mathbb{Z}$,$l\neq 0$, the map $k\mapsto u(k+l)-u(k)$ is a ...
19
votes
3answers
1k views
mixing convex and concave for convexity
Let $n\in\mathbb{N}$ and $0<x<1$ be a real number. Is the following a convex function of $x$?
$$G_n(x)=\log\left(\frac{(1+x^{4n+1})(1+x^{4n-1})(1+x^{2n})(1-x^{2n+1})}{(1+x^{2n+1})(1-x^{2n+2})}\...
15
votes
2answers
1k views
Number of isomorphism types of finite groups
Are there some good asymptotic estimations for the number $F(n)$ of non-isomorphic finite groups of size smaller than $n$?
14
votes
4answers
9k views
How many $p$-regular graphs with $n$ vertices are there?
Suppose that there are $n$ vertices, we want to construct a regular graph with degree $p$, which, of course, is less than $n$. My question is how many possible such graphs can we get?
16
votes
4answers
8k views
Exact formulas for the partition function?
I am curious, what kind of exact formulas exist for the partition function $p(n)$?
I seem to remember an exact formula along the lines $p(n) = \sum_k f(n, k)$, where $f(n, k)$ was some extremely ...
19
votes
3answers
1k views
The sum of integers being a bijection
What are the pairs $(P,Q)$ of subsets of $\mathbb N$ for which the map
\begin{eqnarray*}
P\times Q & \rightarrow & {\mathbb N} \\\\
(p,q) & \mapsto & p+q
\end{eqnarray*}
is a bijection ...
