# 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
Filter by
Sorted by
Tagged with
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 ...
9k views

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 ...
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?
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 ...
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}$$ ...
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 ...
3k views

399 views

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 ...
269 views

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 ...
7k views

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 ...
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 ...
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 ...
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 ...
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 ...
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) ...
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 ...
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 (...
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 ...
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 ...
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 ...
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})}\...
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$?
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?
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 ...
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 ...