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

**39**

votes

**1**answer

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

**49**

votes

**1**answer

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!]
...

**35**

votes

**5**answers

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

**30**

votes

**2**answers

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

**34**

votes

**4**answers

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

**28**

votes

**5**answers

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

**23**

votes

**5**answers

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

**36**

votes

**2**answers

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

**25**

votes

**4**answers

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

**23**

votes

**13**answers

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

**18**

votes

**10**answers

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

**44**

votes

**4**answers

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

**24**

votes

**7**answers

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

**50**

votes

**2**answers

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

**35**

votes

**5**answers

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

**34**

votes

**2**answers

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):
...

**33**

votes

**2**answers

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

**24**

votes

**2**answers

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

**23**

votes

**0**answers

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

**23**

votes

**5**answers

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

**22**

votes

**1**answer

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

**22**

votes

**6**answers

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

**20**

votes

**0**answers

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

**36**

votes

**3**answers

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

**31**

votes

**1**answer

2k views

### tiling a rectangle with the smallest number of squares

This is based on another thread. For $m,n\in \mathbb N$, let $f(m,n)$ be the minimum number of squares with integer sides needed to tile a $m\times n$ rectangle. Recently, a table of values for $n\le ...

**24**

votes

**3**answers

1k views

### Some models for random graphs that I am curious about

G(n,p)
We are familiar with the standard notion of random graphs where you fixed the number n of vertices and choose every edge to belong to the graph with probability 1/2 (or p) independently. This ...

**22**

votes

**8**answers

2k views

### Higher-dimensional Catalan numbers?

One could imagine defining various notions of higher-dimensional Catalan numbers,
by generalizing objects they count.
For example, because the Catalan numbers count the triangulations of convex ...

**22**

votes

**1**answer

1k views

### A Question on 1, 2 ,3 Conjecture

The 1, 2, 3 conjecture is well-known:
If $G$ is a simple graph which is not $K_2$ then one can assign a number among $1, 2, 3$ to every edge such that if we label each vertex with the sum of the ...

**18**

votes

**1**answer

1k views

### Number of distinct values taken by x^x^…^x with parentheses inserted in all possible ways

For what positive x's the number of distinct values taken by x^x^...^x with parentheses inserted in all possible ways is not represented by the sequence A000081? Is it exactly the set of positive ...

**14**

votes

**2**answers

2k views

### What are some open problems in toric varieties?

In light of the nice responses to this question, I wonder what are some open problems in
the area of toric geometry? In particular,
What are some open problems relating to the algebraic ...

**68**

votes

**10**answers

15k views

### Does War have infinite expected length?

My question concerns the (completely deterministic) card game known as War, played by seven-year-olds everywhere, such as my son Horatio, and sometimes also by others, such as their fathers.
The ...

**33**

votes

**1**answer

2k views

### “The Two Sheriffs” puzzle

This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler.
Two sheriffs in neighboring towns are on the track of a killer, in a
case involving eight ...

**15**

votes

**2**answers

2k views

### roots of permutations

Consider equation $x^2=x_0$ in symmetric group $S_n$, where $x_0\in S_n$ is fixed. Is it true that for each integer $n\geq 1$, the maximal number of solutions (square roots) has identity permutation? ...

**15**

votes

**11**answers

3k views

### Applications of Measure, Integration and Banach Spaces to Combinatorics

I'm going to be teaching a Master's level analysis course(measure theory, Lebesgue integration, Banach and Hilbert spaces, and if there's time, some spectral or PDE stuff) in the fall. My problem is ...

**27**

votes

**8**answers

4k views

### Applications of infinite graph theory

Finite graph theory abounds with applications inside mathematics itself, in computer science, and engineering. Therefore, I find it naturally to do research in graph theory and I also clearly see the ...

**23**

votes

**4**answers

1k views

### How many simplicial complexes on n vertices up to homotopy equivalence?

Fix a number $n$, and define $\gamma(n)$ to be the number of simplicial complexes on $n$ unlabeled vertices up to homotopy equivalence. It is unlikely that an explicit formula exists, but what is ...

**15**

votes

**11**answers

2k views

### Chromatic number of graphs of tangent closed balls

The Koebe–Andreev–Thurston theorem gives a characterization of planar graphs in terms of disjoint circles being tangent. For every planar graph $G$ there is a disk packing whose graph is $G$. What ...

**15**

votes

**5**answers

6k views

### Which graphs have incidence matrices of full rank?

This is a follow-up to a previous question. What graphs have incidence matrices of full rank?
Obvious members of the class: complete graphs.
Obvious counterexamples: Graph with more than two ...

**12**

votes

**3**answers

1k views

### Models for graphs representing real-life networks

I am interested in basic models of graphs (stochastic or deterministic) that are offered for real-life networks (like social networks, the Internet, neuron networks).
I will be thankful for answers ...

**36**

votes

**5**answers

3k views

### Factorials in Pascals Triangle

Hi,
I asked this question of Keith Conrad, and he suggested that I try posting here. One of my students observed that the only instances of factorials in the interior of Pascal's triangle are $\...

**27**

votes

**2**answers

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

**26**

votes

**2**answers

1k views

### Some binomial coefficient determinants

It is well known that for $n>0$
$$d(n)=\det\left(\binom{2i+2j+1}{i+j}\right)_{i,j=0}^{n-1}=1.$$
Computer experiments suggest that more generally
$$d(n,k)=\det\left(\binom{2i+2j+2k+1}{i+j}\right)_{i,...

**25**

votes

**3**answers

709 views

### Ordering subsets of the cyclic group to give distinct partial sums

Suppose that you are given a set $S$ of $k$ nonzero elements from $\mathbb{Z}_n$. Is it always possible to order the elements of $S$, say $a_1,a_2,\dots,a_k$ in such a way that the partial sums $a_1,...

**24**

votes

**4**answers

1k views

### Asymptotic growth of a certain integer sequence

Some time ago, while putting my nose in the Sloane's Online Encyclopedia of Integer Sequences, I came over the sequence A019568 defined as follows:
$a(n):=$ the smallest positive integer $k$ such
...

**13**

votes

**0**answers

411 views

### What is the geometric intuition behind Wilf-Zeilberger theory?

This problem is somehow inspired by a bunch of impressive posts of combinatorial identities by T. Amdeberhan. Earlier this month I learnt from computer scientists that they have a generic algorithmic ...

**11**

votes

**1**answer

674 views

### Fomin-Kirillov algebras and Schubert calculus

In
Fomin, Sergey; Kirillov, Anatol N. Quadratic algebras, Dunkl elements, and
Schubert calculus. Advances in geometry, 147--182, Progr. Math., 172,
Birkhäuser Boston, Boston, MA, 1999. MR1667680 (...

**11**

votes

**2**answers

1k views

### Proving $\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}$

I found the following formula in a book without any proof:
$$\sum_{k=0}^{2m}(-1)^k{\binom{2m}{k}}^3=(-1)^m\binom{2m}{m}\binom{3m}{m}.$$
This does not seem to follow immediately from the basic ...

**24**

votes

**2**answers

2k views

### Is there a name for a family of finite sequences that block all infinite sequences?

Let ${\bf N}^\omega = \bigcup_{m=1}^\infty {\bf N}^m$ denote the space of all finite sequences $(N_1,\ldots,N_m)$ of natural numbers. For want of a better name, let me call a family ${\mathcal T} \...

**21**

votes

**0**answers

398 views

### Coloring a Ferrers diagram

I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed.
Say that a coloring of the dots of a Ferrers ...

**18**

votes

**5**answers

3k views

### Has any attempt been made to classify finite groupoids?

I recently stumbled upon the Mathieu groupoid and I found them fascinating.
It appears as a subset of $S_{13}$ which is not closed under multiplication, but it turns out to be a groupoid with 13 ...