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.

Filter by
Sorted by
Tagged with
180
votes
3answers
92k 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 ...
131
votes
63answers
30k 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 ...
112
votes
4answers
6k 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}\...
108
votes
7answers
7k 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 ...
104
votes
5answers
8k 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)}{\...
96
votes
11answers
14k 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 ...
94
votes
17answers
109k 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: ...
94
votes
13answers
75k 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 ...
93
votes
3answers
4k 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: http://www.math.harvard.edu/cdm/. Here are two examples of the kind of ...
89
votes
5answers
3k 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 ...
79
votes
10answers
8k 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, ...
77
votes
9answers
7k 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 ...
77
votes
4answers
6k 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....
74
votes
6answers
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 ...
74
votes
4answers
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 ...
70
votes
8answers
13k 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
11answers
22k 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 ...
67
votes
6answers
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,(...
66
votes
7answers
12k 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 ...
65
votes
5answers
15k 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 ...
59
votes
19answers
10k 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 ...
59
votes
7answers
6k 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 = ...
59
votes
4answers
2k 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, ...
59
votes
1answer
1k 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 ...
57
votes
1answer
3k 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 ...
55
votes
0answers
3k 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\} | A,B\in {\Bbb Z}^2,||A||<r,||B||<r, |...
54
votes
3answers
6k 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 ...
54
votes
1answer
2k 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 $\...
53
votes
10answers
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-...
53
votes
4answers
10k 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 ...
52
votes
2answers
7k 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 ! Harold Calvin Marston Morse (24 March ...
52
votes
1answer
5k 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!] ...
51
votes
7answers
22k 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 ...
51
votes
2answers
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
votes
37answers
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
8answers
3k views

Puzzle on deleting k bits from binary vectors of length 3k

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
2answers
17k 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 ...
50
votes
4answers
9k 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\...
50
votes
0answers
2k 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 ...
49
votes
3answers
4k 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)$?
49
votes
2answers
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 ...
48
votes
15answers
9k 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 ...
48
votes
8answers
5k 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 ...
48
votes
6answers
4k views

Non-enumerative proof that there are many derangements?

Recall that a derangement is a permutation $\pi: \{1,\ldots,n\} \to \{1,\ldots,n\}$ with no fixed points: $\pi(j) \neq j$ for all $j$. A classical application of the inclusion-exclusion principle ...
47
votes
7answers
8k views

Conway's game of life for random initial position

What is the behavior of Conway's game of life when the initial position is random? -- We can ask this question on an infinite grid or on an $n$ by $n$ table (planar or on a torus). Specifically ...
47
votes
5answers
5k 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 because ...
47
votes
6answers
6k views

Is there an "elegant" non-recursive formula for these coefficients? Also, how can one get proofs of these patterns?

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 "...
47
votes
1answer
3k views

Why is the Frankl conjecture hard?

This is a naive question that could justifiably be quickly closed. Nevertheless: Q. Why is Péter Frankl's conjecture so difficult? If any two sets in some family of sets have a union that also ...
46
votes
18answers
12k 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, ...
46
votes
3answers
4k views

Does knight behave like a king in his infinite odyssey?

The Knight's Tour is a well-known mathematical chess problem. There is an extensive amount of research concerning this question in two/higher dimensional finite boards. Here, I would like to tackle ...

1
2 3 4 5
174