# 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,466 questions
Filter by
Sorted by
Tagged with
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 ...
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,531
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
13k views

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

• 3,104
760 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

### 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
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 ...
• 630
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
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
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
9k views

• 23.6k
7k 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
5k views

• 137k
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
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
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 ...