# 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.

785 questions
20k 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 ...
50k 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 ...
5k 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 ...
8k 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 ...
416 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}$$ ...
1k 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 ...
3k views

274 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 ...
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 ...
796 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 ...
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?
2k views

### Does the hypergraph structure of the set of subgroups of a finite group characterize isomorphism type?

Question Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ ...
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 ‎...
727 views

707 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 ...
5k 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 ...
720 views

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)... 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 ... 2answers 6k 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 ... 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 ... 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 ... 5answers 6k 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 ... 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) ... 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 (... 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 ... 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? 4answers 6k 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? 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 ... 1answer 434 views ### 2-adic Logarithm and Resistance of n-dimensional Cube Resistance across opposite vertices of n-dimensional cube with each edge at one ohm resistance is$$R_n=\sum_{k=0}^{n-1}\frac1{(n-k){n\choose k}}=\frac1n\sum_{k=0}^{n-1}\frac1{{n-1\choose k}}.$$The ... 1answer 602 views ### Reference request: a conjecture of Rota on positive functions of a random variable Rota and Shen's On the Combinatorics of Cumulants ends with a conjecture which I'll restate as follows: Let p \in \mathbb{R}[x_1, x_2, ...] be a polynomial such that, for any sequence X_1, X_2, ... 2answers 971 views ### Minimal graphs with a prescribed number of spanning trees As its long ago since Erdős died and mathoverflow is the second best alternative to him (for discussing personal problems), I'd like to start a fruitful discussion about the following problem ... 4answers 2k views ### Ordinary Generating Function for Bell Numbers In the OEIS entry for Bell numbers, there appears a generating function$$\sum_{k=0}^\infty B_k t^k = \sum_{r=0}^\infty \prod_{i=1}^r \frac{t}{1-it}$$However, I could not locate any proof of ... 1answer 351 views ### Probability of a graph procedure We are going to build K_n one edge at a time. Begin with the empty graph on n vertices. Take a random permutation of the edges of K_n and, one at a time, place the edges onto the graph (so, ... 1answer 320 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 ... 1answer 1k views ### Smith Normal Form of powers of a matrix What invariants of a matrix determine the Smith Normal Form (SNF) of all the powers of a matrix? The question makes sense over any PID R. If we let M = M_n(R) and G=Gl_n(R), then SNF is a ... 0answers 154 views ### A conjectural lower bound for |\{\sum_{k=1}^nka_k:\ a_1,\ldots,a_n\ \text{are distinct elements of }\ A\}| Motivated by Question 315568 of mine, I'm interested in the set$$S(n):=\bigg\{\sum_{k=1}^n k\pi(k):\ \pi\in S_n\bigg\}.$$It is easy to see that$$S(1)=\{1\},\ S(2)=\{4,5\}\ \text{and}\ S(3)=\{10,...
This post is a sequel of Eulerian ordering of the integers modulo n. Let us recall the definition of an Eulerian ordering: Let $n>1$ be an integer. Consider the set $C_n := \{0,1, \dots , n-1\}$....