All Questions
Tagged with combinatorics or co.combinatorics
11,024 questions
186
votes
3
answers
96k
views
Issue UPDATE: in graph theory, different definitions of edge crossing numbers - impact on applications?
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 ...
- 343
161
votes
37
answers
17k
views
Conceptual reason why the sign of a permutation is well-defined?
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 ...
- 63.9k
147
votes
66
answers
40k
views
Important formulas in combinatorics
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 ...
125
votes
4
answers
8k
views
What do the stable homotopy groups of spheres say about the combinatorics of finite sets?
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}\...
- 23k
121
votes
15
answers
101k
views
Sum of 'the first k' binomial coefficients for fixed $N$
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 ...
- 1,288
113
votes
7
answers
8k
views
Is the set $ AA+A $ always at least as large as $ A+A $?
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 ...
- 1,498
106
votes
5
answers
10k
views
integral of a "sin-omial" coefficients=binomial
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)}{\...
- 43.2k
103
votes
3
answers
6k
views
Why do combinatorial abstractions of geometric objects behave so well?
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 ...
- 24.2k
101
votes
10
answers
16k
views
Why do Bernoulli numbers arise everywhere?
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 ...
98
votes
17
answers
123k
views
Google question: In a country in which people only want boys [closed]
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:
...
- 1,107
95
votes
5
answers
4k
views
Can a row of five equilateral triangles tile a big equilateral triangle?
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 ...
- 3,137
82
votes
9
answers
8k
views
What are some examples of interesting uses of the theory of combinatorial species?
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 ...
- 1,570
81
votes
10
answers
9k
views
Existence of a zero-sum subset
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, ...
- 85.6k
81
votes
4
answers
8k
views
Wanted: a "Coq for the working mathematician"
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....
- 33.8k
79
votes
6
answers
4k
views
Does every polyomino tile R^n for some n?
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 ...
- 82.7k
75
votes
11
answers
28k
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 ...
- 236k
75
votes
4
answers
6k
views
What is the amplituhedron?
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 ...
- 24.7k
74
votes
9
answers
16k
views
What is Lagrange Inversion good for?
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 ...
70
votes
7
answers
14k
views
Identifying poisoned wines
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 ...
- 118k
69
votes
7
answers
17k
views
What is a chess piece mathematically?
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 ...
69
votes
2
answers
4k
views
Function that produces primes
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 ...
- 4,938
67
votes
6
answers
7k
views
How to recognise that the polynomial method might work
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,(...
- 29k
66
votes
1
answer
4k
views
(Approximately) bijective proof of $\zeta(2)=\pi^2/6$?
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\|<...
- 17.6k
64
votes
1
answer
5k
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 ...
- 33.8k
63
votes
19
answers
12k
views
Generalizations of the four-color theorem
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 ...
62
votes
7
answers
26k
views
Is the Jaccard distance a distance?
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 ...
- 1,355
62
votes
7
answers
7k
views
Euler-Maclaurin formula and Riemann-Roch
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 = ...
- 13.1k
60
votes
4
answers
3k
views
Flipping coins on a budget
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, ...
- 82.7k
59
votes
2
answers
4k
views
For a finite set A of positive reals, prove that the set A + A - A contains at least as many positive as negative elements
I am currently working on a proof that would need to use the following theorem that I cannot prove:
"Let $A$ be a finite set of positive real numbers. Then, the set $A + A - A$ contains at least ...
- 643
59
votes
1
answer
2k
views
Which region in the plane with a given area has the most domino tilings?
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.6k
58
votes
3
answers
6k
views
Number of elements in the set $\{1,\cdots,n\}\cdot\{1,\cdots,n\}$
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)$?
- 897
57
votes
4
answers
15k
views
Connectivity of the Erdős–Rényi random graph
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 ...
- 7,857
57
votes
0
answers
3k
views
On the first sequence without triple in arithmetic progression
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 ...
56
votes
21
answers
14k
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, ...
56
votes
1
answer
3k
views
Intersecting family of triangulations
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 $\...
- 24.7k
54
votes
3
answers
7k
views
cube + cube + cube = cube
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 ...
- 52.3k
54
votes
4
answers
5k
views
How many square roots can a non-identity element in a group have?
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 ...
- 805
54
votes
2
answers
8k
views
Walsh Fourier transform of the Möbius function
This question is related to this previous question where I asked about ordinary Fourier coefficients.
Special case: is Möbius nearly orthogonal to Morse
August Ferdinand Möbius (November 17, 1790 – ...
54
votes
10
answers
8k
views
The "sensitivity" of 2-colorings of the d-dimensional integer lattice
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-...
- 9,823
53
votes
1
answer
6k
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!]
...
- 151k
53
votes
0
answers
2k
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 ...
- 1,834
52
votes
8
answers
6k
views
What are the external triumphs of matroid theory?
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 ...
- 17.6k
52
votes
4
answers
10k
views
Do there exist chess positions that require exponentially many moves to reach?
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\...
- 82.7k
52
votes
2
answers
3k
views
vector balancing problem
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 ...
- 42.8k
51
votes
2
answers
5k
views
The "square root" of a graph?
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.8k
51
votes
2
answers
18k
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 ...
- 24.9k
51
votes
3
answers
4k
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 ...
- 19.2k
50
votes
37
answers
6k
views
Structures that turn out to exhibit a symmetry even though their definition doesn't
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
12
answers
7k
views
Combinatorial results without known combinatorial proofs
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 ...
50
votes
6
answers
11k
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 ...
- 7,609