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

791 questions
2k views

### What is the sandpile torsor?

Let G be a finite undirected connected graph. A divisor on G is an element of the free abelian group Div(G) on the vertices of G (or an integer-valued function on the vertices.) Summing over all ...
4k views

### Why are there 1024 Hamiltonian cycles on an icosahedron?

Fix one edge $e$ of the graph (1-skeleton) of an icosahedron. By a computer search, I found that there are 1024 Hamiltonian cycles that include $e$. [But see edit below re directed vs. undirected!] ...
3k views

### Show that this ratio of factorials is always an integer

show the formula always gives an integer $$\frac{(2m)!(2n)!}{m!n!(m+n)!}$$ I don't remember where I read this problem, but it said this can be proved using a simple counting argument (like observing ...
2k views

### Shimura-Taniyama-Weil VS Grothendieck's dessins

When listening to the beautiful lectures by Gilles Schaeffer at the SLC68, the following (perhaps crazy) question occurred to me: did anyone attempt (succeed?) to combinatorially prove modularity of ...
2k views

### “Circular” domination in ${\mathbb R}^4$

The following problem is related to (and motivated by) the first open case of this MO question. It is difficult to believe that this is a hard problem; and yet, I do not have a solution. For two ...
5k views

### Number of valid topologies on a finite set of n elements

I've heard that the problem of counting topologies is hard, but I couldn't really find anything about it on the rest of the internet. Has this problem been solved? If not, is there some feature that ...
4k views

### The Matrix-Tree Theorem without the matrix

I'm teaching an introductory graph theory course in the Fall, which I'm excited about because it gives me the chance to improve my understanding of graphs (my work is in topology). A highlight for me ...
2k views

### A group-theoretic perspective on Frankl's union closed problem

Here is a group theoretic phrasing of a special case of the union closed conjecture: Question: Given a finite group $G$, is there an element of prime power order which is contained in at most half ...
2k views

### $\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$ is a convex function on $[0,+\infty)$?

Let $f(x)=\binom{x}{2}+\binom{x}{4}+\cdots+\binom{x}{2u}$, where $u\in\mathbb{Z}^+$ and $\binom{x}{l}=\frac{x(x-1)\dots(x-l+1)}{l!}$ for all $l\in\mathbb{Z}^+$. Then can we prove $f(x)$ is a convex ...
5k views

### Generalizations of the Birkhoff-von Neumann Theorem

The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices. The question is to point out different ...
1k views

### Combinatorial Databases

At one point, I remember being excited by seeing the website Encyclopedia of Combinatorial Structures as an extension of Sloane's Online Integer Sequence Database site. Unfortunately, the site (ECS) ...
3k views

### Difficult examples for Frankl's union-closed conjecture

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there ...
2k views

### Computer package for representation theory of the symmetric group

Is there a computer algebra package in which I can compute the following for representations of a specific symmetric group (e.g. $S_7$): (1) $V \otimes W$ (2) $S_\lambda V$, where $S_\lambda$ is a ...
16k views

### Is there winning strategy in Tetris ? What if Young diagrams are falling?

Question 1 Is there a winning strategy (algorithm to play infinitely) in Tetris, or is there a sequence of bricks which is impossible to pack without holes? Consider generalized Tetris with Young ...
3k views

### Why do wedges of spheres often appear in combinatorics?

Robin Forman writes in "A User's Guide to Discrete Morse Theory": The reader should not get the impression that the homotopy type of a CW complex is determined by the number of cells of each ...
2k views

### The coupon collector's earworm

[EDITED mostly to report on the answer by Kevin Costello (and to improve the gp code at the end)] I thank Nicolas Dupont for the following question (and for permission to disseminate it further): ...
3k views

### Projective Plane of Order 12

I asked this question on the new Theoretical Computer Science "overflow" site, and commenters suggested I ask it here. That question is here, and it contains additional links, which I doubt I can ...
2k views

### Order of products of elements in symmetric groups

Let $n \in \mathbb{N}$. Is it true that for any $a, b, c \in \mathbb{N}$ satisfying $1 < a, b, c \leq n-2$ the symmetric group ${\rm S}_n$ has elements of order $a$ and $b$ whose product has order ...
2k views

### Why do polytopes pop up in Lagrange inversion?

I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
1k views

### Reference on Persistent Homology

I will be teaching a course on algebraic topology for MSc students and this semester, unlike previous ones where I used to begin with the fundamental group, I would like to start with ideas of ...
1k views

### Combinatorial spin structures

I would like to know how to define spin structures combinatorially, for an oriented smooth manifold equipped with a triangulation. In the case of a 2d manifold, spin structures correspond to ...
2k views

### Is there a topological description of combinatorial Euler characteristic?

There are a collection of definitions of "combinatorial Euler characteristic", which is different from the "homotopy Euler characteristic". I will describe a few of them and give some references, and ...
2k views

### Trigonometry related to Rogers--Ramanujan identities

For integers $n\ge2$ and $k\ge2$, fix the notation $$[m]=\sin\frac{\pi m}{nk+1} \quad\text{and}\quad [m]!=[1][2]\dots[m], \qquad m\in\mathbb Z_{>0}.$$ Consider the following trigonometric numbers:...
4k views

### the following inequality is true，but I can't prove it

The inequality is \begin{equation*} \sum_{k=1}^{2d}\left(1-\frac{1}{2d+2-k}\right)\frac{d^k}{k!}>e^d\left(1-\frac{1}{d}\right) \end{equation*} for all integer $d\geq 1$. I use computer to verify ...
2k views

2k views

### An unfair marriage lemma

I am looking for a citeable reference to the following generalization of Hall's Marriage Theorem: Given a bipartite graph of boys and girls. In addition to gender difference, they are divided into ...