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

6,440 questions
15answers
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 ...
4answers
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 ...
6answers
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 ...
0answers
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 ...
4answers
4k views

5answers
3k views

6answers
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 ...
2answers
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 ...
2answers
1k views

2answers
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, ...
4answers
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 ...
2answers
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): ...