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

**42**

votes

**15**answers

8k views

### Strong induction without a base case

Strong induction proves a sequence of statements $P(0)$, $P(1)$, $\ldots$ by proving the implication
"If $P(m)$ is true for all nonnegative integers $m$ less than $n$, then $P(n)$ is true."
for ...

**42**

votes

**4**answers

2k views

### A curious process with positive integers

Let $k > 1$ be an integer, and $A$ be a multiset initially containing all positive integers. We perform the following operation repeatedly: extract the $k$ smallest elements of $A$ and add their ...

**42**

votes

**6**answers

3k views

### Can we color Z^+ with n colors such that a, 2a, …, na all have different colors for all a?

For example for n=2 coloring odd numbers red, numbers of the form 4k+2 blue and so on works.
This problem was posed in the KoMaL for n+1 prime, by Peter Pach Pal. I verified it for all n<30, I ...

**42**

votes

**0**answers

1k views

### Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?

A very specific case of Reed's Conjecture
Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...

**41**

votes

**4**answers

4k views

### A game of stones

How I arrived at this question is a rather long story having to do with the honors calculus class I am teaching. At this point it's sheer curiosity on my part. Here is the game.
$\newcommand{\bZ}{\...

**41**

votes

**4**answers

4k views

### Integer-valued factorial ratios

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

**41**

votes

**2**answers

2k views

### Numbers that are generic w.r.t. exponentiation

This is a follow-up to my old question Number of distinct values taken by $x\hat{\phantom{\hat{}}}x\hat{\phantom{\hat{}}}\dots\hat{\phantom{\hat{}}}x$ with parentheses inserted in all possible ways.
...

**40**

votes

**15**answers

6k views

### What does the generating function $x/(1 - e^{-x})$ count?

Let $x$ be a formal (or small, since the function is analytic) variable, and consider the power series
$$ A(x) = \frac{x}{1 - e^{-x}} = \sum_{m=0}^\infty \left( -\sum_{n=1}^\infty \frac{(-x)^n}{(n+1)!}...

**40**

votes

**8**answers

4k views

### 1 rectangle <= 4 squares

Almost 25 years ago a professor at Indiana U showed me the following problem:
given a map $\mathbb{Z}^2\rightarrow\mathbb{R}$ such that the sum inside every square (parallel to the axes) is $\leq1$ ...

**40**

votes

**1**answer

3k views

### Mathematicians wearing hats on arbitrary total orders

I've been pondering the following generalisation of a famous problem (the special case where $T = \mathbb{N})$:
Question: We have some totally-ordered set $T$ of mathematicians, each wearing a hat ...

**40**

votes

**3**answers

1k views

### Characterizing positivity of formal group laws

The formal group law associated with a generating function $f(x) = x + \sum_{n=2}^\infty a_n \frac{x^n}{n!}$ is $$f(f^{-1}(x) + f^{-1}(y)).$$ In my thesis, I found a large number of examples of ...

**39**

votes

**15**answers

7k views

### Strengthening the Induction Hypothesis

Suppose you are trying to prove result $X$ by induction and are getting nowhere fast. One nice trick is to try to prove a stronger result $X'$ (that you don't really care about) by induction. This ...

**39**

votes

**4**answers

1k views

### Sets of unit fractions with sum $\leq 1$

Consider a set of fractions $\left\{1, \frac{1}{2}, \frac{1}{3}, \ldots, \frac{1}{n}\right\}$. How many subsets of this set have sum at most 1? I'm interested in the asymptotics of this number.
...

**39**

votes

**5**answers

2k views

### How many rearrangements must fail to alter the value of a sum before you conclude that none do?

This will not be altogether unrelated to this earlier question.
For which classes $C$ of bijections from $\{1,2,3,\ldots\}$ to itself is it the case that for all sequences $\{a_i\}_{i=1}^\infty$ of ...

**39**

votes

**3**answers

2k views

### Does an existence of large cardinals have implications in number theory or combinatorics?

Does an existence of large cardinals have implications in more down-to-earth fields like number theory, finite combinatorics, graph theory, Ramsey theory or computability theory? Are there any ...

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

**39**

votes

**1**answer

1k views

### Do runs of every length occur in this sequence?

This is a repost from user r.e.s's unsolved Math Stack Exchange question: Do runs of every length occur in this string? That question was derived from my original question on the subject: Does this ...

**38**

votes

**17**answers

10k views

### Linear Algebra Proofs in Combinatorics?

Simple linear algebra methods are a surprisingly powerful tool to prove combinatorial results. Some examples of combinatorial theorems with linear algebra proofs are the (weak) perfect graph theorem, ...

**38**

votes

**1**answer

794 views

### How to be rigorous about combinatorial algorithms?

1. The question
This may be the worst question I've ever posed on MathOverflow: broad,
open-ended and likely to produce heat. Yet, I think any progress that will be
made here will be extremely useful ...

**38**

votes

**2**answers

1k views

### Implications of non-negativity of coefficients of arbitrary Kazhdan-Lusztig polynomials?

In their seminal 1979 paper here,
Kazhdan and Lusztig studied an arbitrary Coxeter group $(W,S)$ and the corresponding Iwahori-Hecke algebra. In particular they showed how to pass from a standard ...

**37**

votes

**5**answers

4k views

### Algebraic Proof of 4-Colour Theorem?

4-Colour Theorem. Every planar graph is 4-colourable.
This theorem of course has a well-known history. It was first proven by Appel and Haken in 1976, but their proof was met with skepticism ...

**37**

votes

**9**answers

3k views

### The shortest path in first passage percolation

Update (January 17): The problem has now been solved by Daniel Ahlberg and Christopher Hoffman. (Thanks to Matt Kahle for informing us.)
Consider a square planar grid. (The vertices are pair of ...

**37**

votes

**4**answers

2k views

### A family of words counted by the Catalan numbers

In recent work with Michael Albert and Nik Ruškuc, a family of words has arisen which is counted by the Catalan numbers. I've looked at Richard Stanley's Catalan exercises in EC2 and his Catalan ...

**37**

votes

**2**answers

1k views

### How close can one get to the missing finite projective planes?

This question can be interpreted as an instance of the Zarankiewicz problem. Suppose we have an $n\times n$ matrix with entries in $\{0,1\}$ with no $\begin{pmatrix}1 & 1\\ 1& 1\end{pmatrix} $ ...

**36**

votes

**6**answers

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

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

**36**

votes

**2**answers

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

**36**

votes

**4**answers

2k views

### Does there exist a comprehensive compilation of Erdos's open problems?

Fan Chung and Ron Graham's book Erdos on Graphs: His Legacy of Unsolved Problems (A. K. Peters, 1998) collects together all of Erdos's open problems in graph theory that they could find into a single ...

**36**

votes

**9**answers

5k views

### What proportion of chess positions that one can set up on the board, using a legal collection of pieces, can actually arise in a legal chess game?

Many chess positions that one may easily set up on a chess board
are impossible to achieve in a game of legal moves. For example,
among the impossible situations would be:
A position in which both ...

**36**

votes

**2**answers

2k views

### Rooks in three dimensions

Given is an infinite 3-dim chess board and a black king. What is the minimum number of white rooks necessary that can guarantee a checkmate in a finite number of moves?
(In 3-dimensional chess rooks ...

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

**36**

votes

**4**answers

9k views

### Do actual Sudoku puzzles have a unique rational solution?

Here is a question in the intersection of mathematics and sociology. There is a standard way to encode a Sudoku puzzle as an integer programming problem. The problem has a 0-1-valued variable $a_{i,...

**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 $\...

**36**

votes

**2**answers

1k views

### Is there an analog of Sperner's lemma for the Hopf invariant?

Recall that Sperner's lemma is essentially a combinatorial version of the topological statement "A map from $S^n$ to $S^n$ with degree one cannot be nullhomotopic."
My question is, does there exist ...

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

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

**35**

votes

**6**answers

10k views

### Submitting to arXiv when unaffiliated

I am writing a short paper in the area of combinatorics.
When the paper is complete, I would like to be able to submit it to arXiv.
The reasons that I would like to submit to arXiv are:
To obtain a ...

**35**

votes

**6**answers

3k views

### Why do Littlewood-Richardson coefficients describe the cohomology of the Grassmannian?

I'm looking for a "conceptual" explanation to the question in the title. The standard proofs that I've seen go as follows: use the Schubert cell decomposition to get a basis for cohomology and show ...

**35**

votes

**5**answers

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

**35**

votes

**2**answers

2k views

### Random sequence of integers in $\{1, 2, \dots, n \}$ which is “everywhere probably increasing” - how long can it be?

Let $D=(d_1,d_2,\dots,d_k)$ be a sequence of correlated random variables. $D$ is "everywhere $r$-probably increasing" if the event $d_j > d_i$ has probability $\geq r$ for all $j > i$.
Fix $r \...

**35**

votes

**6**answers

2k views

### Placing numbers $1,2,\ldots,n^3$ in a cube so that numbers of any two adjacent unit subcube are coprime

This is a question first I asked in SE but since there was no suggestion or solution, I decide to put it here.
Consider an $n\times n \times n$ Cube containing $n^3$ unit cubes. Is it possible to ...

**35**

votes

**2**answers

1k views

### What is the oriented Fano plane?

One way to remember the multiplication table of the octonions is to use the following diagram (which I got from John Baez's online paper): if $(e_i,e_j,e_k)$ is one of the lines listed according to ...

**35**

votes

**2**answers

1k views

### Is there a combinatorial reason that the (-1)st Catalan number is -1/2?

The $n$th Catalan number can be written in terms of factorials as
$$ C_n = {(2n)! \over (n+1)! n!}. $$
We can rewrite this in terms of gamma functions to define the Catalan numbers for complex $z$:
$$...

**35**

votes

**3**answers

3k views

### finding the parity of a permutation in little space

Suppose we have a permutation $\pi$ on $1,2,\ldots,n$ and want to determine the parity (odd or even) of $\pi$.
The standard method is find the cycles of $\pi$ and recall that the parity of $\pi$ ...

**34**

votes

**21**answers

4k views

### Generalizations of Planar Graphs

This is a follow up to Harrison's question: why planar graphs are so exceptional. I would like to ask about (and collect answers to) various notions, in graph theory and beyond graph theory (topology; ...

**34**

votes

**14**answers

18k views

### What are the Applications of Hypergraphs

Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a ...

**34**

votes

**7**answers

4k views

### Help with a double sum, please

Here is a double series I have been having trouble evaluating:
$$S=\sum_{k=0}^{m}\sum_{j=0}^{k+m-1}(-1)^{k}{m \choose k}\frac{[2(k+m)]!}{(k+m)!^{2}}\frac{(k-j+m)!^{2}}{(k-j+m)[2(k-j+m)]!}\frac{1}{2^{k+...

**34**

votes

**2**answers

3k views

### How to find Erdős' treasure trove?

The renowned mathematician, Paul Erdős, has published more than 1500 papers in various branches of mathematics including discrete mathematics, graph theory, number theory, mathematical analysis, ...

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

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