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

Enumerative combinatorics, graph theory, order theory, posets, matroids, designs and other discrete structures. It also includes algebraic, analytic and probabilistic combinatorics.

9,553
questions

184
votes

3
answers

94k
views

QUICK FINAL UPDATE: Just wanted to thank you MO users for all your support. Special thanks for the fast answers, I've accepted first one, appreciated the clarity it gave me. I've updated my torus ...

139
votes

65
answers

34k
views

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

138
votes

32
answers

11k
views

Teaching group theory this semester, I found myself laboring through a proof that the sign of a permutation is a well-defined homomorphism $\operatorname{sgn} : \Sigma_n \to \Sigma_2$. An insightful ...

117
votes

4
answers

7k
views

The Barratt-Priddy-Quillen(-Segal) theorem says that the following spaces are homotopy equivalent in an (essentially) canonical way:
$\Omega^\infty S^\infty:=\varinjlim~ \Omega^nS^n$
$\mathbb{Z}\...

111
votes

7
answers

7k
views

Let $A$ be a finite set of real numbers. Is it always the case that $|AA+A| \geq |A+A|$?
My first instinct is that this is obviously true, and there is a one-line proof which I am foolishly ...

110
votes

15
answers

88k
views

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

104
votes

5
answers

9k
views

I find the following averaged-integral amusing and intriguing, to say the least. Is there any proof?
For any pair of integers $n\geq k\geq0$, we have
$$\frac1{\pi}\int_0^{\pi}\frac{\sin^n(x)}{\...

97
votes

11
answers

15k
views

I have seen Bernoulli numbers many times, and sometimes very surprisingly. They appear in my textbook on complex analysis, in algebraic topology, and of course, number theory. Things like the criteria ...

97
votes

3
answers

5k
views

This question is inspired by a talk of June Huh from the recent "Current Developments in Mathematics" conference.
Here are two examples of the kind of combinatorial abstractions of geometric ...

96
votes

17
answers

116k
views

Hi all!
Google published recently questions that are asked to candidates on interviews. One of them caused very very hot debates in our company and we're unsure where the truth is. The question is:
...

90
votes

5
answers

4k
views

Can rotations and translations of this shape
perfectly tile some equilateral triangle?
I originally asked this on math.stackexchange where it was well received and we made some good progress. Here's ...

81
votes

4
answers

7k
views

Sorry for a possibly off-topic question -- there are four StackExchange subs each of which could be construed as the proper place for this question, and I've just picked the one I'm most familiar with....

79
votes

9
answers

7k
views

This is a question I've asked myself a couple of times before, but its appearance on MO is somewhat motivated by this thread, and sigfpe's comment to Pete Clark's answer.
I've often heard it claimed ...

79
votes

6
answers

4k
views

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

79
votes

10
answers

8k
views

Some time ago I heard this question and tried playing around with it. I've never succeeded to making actual progress. Here it goes:
Given a finite (nonempty) set of real numbers, $S=\{a_1,a_2,\dots, ...

74
votes

4
answers

6k
views

The paper ”Scattering Amplitudes and the Positive Grassmannian” by Nima Arkani-Hamed, Jacob L. Bourjaily, Freddy Cachazo, Alexander B. Goncharov, Alexander Postnikov, and Jaroslav Trnka, introduces ...

73
votes

11
answers

24k
views

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

71
votes

8
answers

14k
views

I am planning an introductory combinatorics course (mixed grad-undergrad) and am trying to decide whether it is worth budgeting a day for Lagrange inversion. The reason I hesitate is that I know of ...

67
votes

7
answers

13k
views

The standard version of this puzzle is as follows: you have $1000$ bottles of wine, one of which is poisoned. You also have a supply of rats (say). You want to determine which bottle is the poisoned ...

67
votes

6
answers

7k
views

A couple of days ago I was at a nice seminar given by Christian Reiher, during which he told us about a short proof of the following special case of a theorem of Olson.
Theorem. Let $(a_1,b_1),\dots,(...

66
votes

5
answers

16k
views

Historically, the current "standard" set of chess pieces wasn't the only existing alternative or even the standard one. For instance, the famous Al-Suli's Diamond Problem (which remained ...

66
votes

1
answer

4k
views

Given $A,B\in {\Bbb Z}^2$, write $A \leftrightarrows B$ if the
interior of the line segment $AB$ misses
${\Bbb Z}^2$.
For $r>0$, define
$S_r:=\{ \{A, B\} \mid A,B\in {\Bbb Z}^2,\|A\|<r,\|B\|<...

65
votes

2
answers

3k
views

For any $n\geq 2$ consider the recursion
\begin{align*}
a(0,n)&=n;\\
a(m,n)&=a(m-1,n)+\operatorname{gcd}(a(m-1,n),n-m),\qquad m\geq 1.
\end{align*}
I conjecture that $a(n-1,n)$ is always ...

63
votes

1
answer

4k
views

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

61
votes

19
answers

11k
views

The four color theorem asserts that every planar graph can be properly colored by four colors.
The purpose of this question is to collect generalizations, variations, and strengthenings of the four ...

60
votes

7
answers

6k
views

Let $Df$ denote the derivative of a function $f(x)$ and $\bigtriangledown f=f(x)-f(x-1)$ be the discrete derivative. Using the Taylor series expansion for $f(x-1)$, we easily get $\bigtriangledown = ...

60
votes

4
answers

2k
views

A coin is flipped $n$ times and you win if it comes up heads at least $k$ times. The coin is unusual in that you're allowed to pick the probability $p_i$ that it comes up heads on the $i$th flip, ...

59
votes

1
answer

2k
views

I just finished teaching a class in combinatorics in which I included a fairly easy upper bound on the number of domino tilings of a region in the plane as a function of its area. So this led to ...

56
votes

7
answers

24k
views

Wikipedia defines the Jaccard distance between sets A and B as $$J_\delta(A,B)=1-\frac{|A\cap B|}{|A\cup B|}.$$ There's also a book claiming that this is a metric. However, I couldn't find any ...

55
votes

1
answer

3k
views

Let $\cal T_n$ be the family of all triangulations on an $n$-gon using $(n-3)$ non-intersecting diagonals. The number of triangulations in $\cal T_n$ is $C_{n-2}$ the $(n-2)$th Catalan number. Let $\...

54
votes

3
answers

7k
views

The following identity is a bit isolated in the arithmetic of natural integers
$$3^3+4^3+5^3=6^3.$$
Let $K_6$ be a cube whose side has length $6$. We view it as the union of $216$ elementary unit ...

54
votes

4
answers

12k
views

It is well-known that if $\omega=\omega(n)$ is any function such that $\omega \to \infty$ as $n \to \infty$, and if $p \ge (\log{n}+\omega) / n$ then the Erdős–Rényi random graph $G(n,p)$ is ...

53
votes

4
answers

4k
views

Let $G$ be a finite group. Let $r_2\colon G \to \mathbb{N}$ be the square-root counting function, assigning to each $g\in G$ the number of $x\in G$ with $x^2=g$. Perhaps surprisingly, $r_2$ does not ...

53
votes

3
answers

5k
views

Let $A_n=\{a\cdot b : a,b \in \mathbb{N}, a,b\leq n\}$. Are there any estimates for $|A_n|$? Will it be $o(n^2)$?

53
votes

10
answers

8k
views

Consider the $d$-dimensional integer lattice, $Z^d$. Call two points in $Z^d$ "neighbors" if their Euclidean distance is 1 (i.e., if they differ by 1 on exactly one coordinate).
Let $C$ be a two-...

52
votes

2
answers

17k
views

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

52
votes

2
answers

8k
views

This question is related to this previous question where I asked about ordinary Fourier coefficients.
##Special case: is Möbius nearly orthogonal to Morse
!
Harold Calvin Marston Morse (24 March 1892 ...

52
votes

1
answer

5k
views

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

51
votes

8
answers

5k
views

As a relatively new abstraction, matroids clearly enjoy a rich theory unto themselves and also offer a viewpoint that suggests interesting analogies and clarifies aspects of the foundations of ...

51
votes

2
answers

5k
views

The number $f(n)$ of graphs on the vertex set $\{1,\dots,n\}$,
allowing loops but not multiple edges, is $2^{{n+1\choose
2}}$, with exponential generating function $F(x)=\sum_{n\geq 0}
2^{{n+1\choose ...

50
votes

37
answers

6k
views

Sometimes (often?) a structure depending on several parameters turns out to be symmetric w.r.t. interchanging two of the parameters, even though the definition gives a priori no clue of that symmetry. ...

50
votes

19
answers

13k
views

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

50
votes

8
answers

3k
views

Consider all $2^n$ different binary vectors of length $n$ and assume $n$ is an integer multiple of $3$. You are allowed to delete exactly $n/3$ bits from each of the binary vectors, leaving vectors ...

50
votes

4
answers

10k
views

By "chess" here I mean chess played on an $n\times n$ board with an unbounded number of (non-king) pieces. Some care is needed if you want to generalize some of the subtler rules of chess to an $n\...

50
votes

2
answers

3k
views

I believe the solution posted to the arXiv on June 17 by Marcus, Spielman, and Srivastava is correct.
This problem may be hard, so I don't expect an off-the-cuff solution. But can anyone suggest ...

50
votes

0
answers

2k
views

In this Numberphile video (from 3:36 to 7:41), Neil Sloane explains an amazing sequence:
It is the lexicographically first among the sequences of positive integers without triple in arithmetic ...

49
votes

15
answers

10k
views

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

48
votes

12
answers

7k
views

Stanley likes to keep a list of combinatorial results for which there is no known combinatorial proof. For example, until recently I believe the explicit enumeration of the de Brujin sequences fell ...

48
votes

6
answers

6k
views

Not sure if this is a "good" question for this forum or if it'll get panned, but here goes anyway...
Consider this problem. I've been trying to find a formula to expand the "regular iteration" of "...

48
votes

0
answers

2k
views

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