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
111 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 ...
Oliver Roche-Newton's user avatar
101 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 ...
Sam Hopkins's user avatar
  • 22.7k
70 votes
7 answers
13k 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 ...
Qiaochu Yuan's user avatar
67 votes
6 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 ...
Morteza Azad's user avatar
64 votes
1 answer
4k 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 ...
darij grinberg's user avatar
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 ...
Greg Kuperberg's user avatar
56 votes
4 answers
14k 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 ...
Matthew Kahle's user avatar
55 votes
1 answer
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 ...
Sebastien Palcoux's user avatar
55 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, ...
50 votes
4 answers
5k views

Difficult examples for Frankl's union-closed conjecture

Frankl's well-known union-closed conjecture states that if F is a finite family of sets that is closed under taking unions (that is, if A and B belong to the family then so does $A\cup B$), then there ...
gowers's user avatar
  • 28.7k
48 votes
6 answers
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
7 answers
5k views

Is it easy to produce hard-to-color graphs?

This question arises from my recent visit to my daughter's second-grade class, where I led some discussion and activities on graph coloring (see Math for seven-year-olds). In one such activity, each ...
Joel David Hamkins's user avatar
44 votes
3 answers
3k 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 ...
Oksana Gimmel's user avatar
42 votes
4 answers
8k views

Verifying the correctness of a Sudoku solution

A Sudoku is solved correctly, if all columns, all rows and all 9 subsquares are filled with the numbers 1 to 9 without repetition. Hence, in order to verify if a (correct) solution is correct, one has ...
Ralph's user avatar
  • 16.1k
41 votes
3 answers
2k views

What is the minimal size of a partial order that is universal for all partial orders of size n?

A partial order $\mathbb{B}$ is universal for a class $\cal{P}$ of partial orders if every order in $\cal{P}$ embeds order-preservingly into $\mathbb{B}$. For example, every partial order $\langle\...
Joel David Hamkins's user avatar
41 votes
6 answers
7k views

Number of valid topologies on a finite set of n elements

I've heard that the problem of counting topologies is hard, but I couldn't really find anything about it on the rest of the internet. Has this problem been solved? If not, is there some feature that ...
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 ...
Jair Taylor's user avatar
39 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} $ ...
Gjergji Zaimi's user avatar
38 votes
2 answers
3k views

Is there a finite family of functions such that the max of any two functions can be dominated by a third?

Is it true that for every $t$ there is an $n$ and there exists a finite function family, $\cal F$, whose members are from $[n] \to \mathbb N$ (taking all different values) and for any $f_1, \ldots, ...
domotorp's user avatar
  • 18.3k
36 votes
5 answers
6k views

Factorials in Pascal's triangle

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 $\binom{4}{...
Rob Gross's user avatar
  • 361
36 votes
21 answers
6k 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; ...
Gil Kalai's user avatar
  • 24.2k
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 ...
kian's user avatar
  • 353
35 votes
1 answer
2k views

How hard is reconstructing a permutation from its differences sequence?

My interest in combinatorially motivated computational problems led me to search for simple problems that turn out to be computationally hard. In this pursuit, I came up with a problem which I hope is ...
Mohammad Al-Turkistany's user avatar
35 votes
3 answers
3k views

Does the hypergraph structure of the set of subgroups of a finite group characterize isomorphism type?

Question Suppose there is a bijection between the underlying sets of two finite groups $G, H$, such that every subgroup of $G$ corresponds to a subgroup of $H$, and that every subgroup of $H$ ...
Chris Beck's user avatar
34 votes
18 answers
19k views

Interesting and accessible topics in graph theory

This summer, I will be teaching an introductory course in graph theory to talented high school seniors. The intent of the course is not to establish proficiency in graph theory, per se. Rather, I hope ...
34 votes
9 answers
7k views

Applications of infinite graph theory

Finite graph theory abounds with applications inside mathematics itself, in computer science, and engineering. Therefore, I find it naturally to do research in graph theory and I also clearly see the ...
Richard Dupont's user avatar
33 votes
1 answer
1k views

What does this connection between Chebyshev, Ramanujan, Ihara and Riemann mean?

It all started with Chris' answer saying returning paths on cubic graphs without backtracking can be expressed by the following recursion relation: $$p_{r+1}(a) = ap_r(a)-2p_{r-1}(a)$$ $a$ is an ...
draks ...'s user avatar
  • 457
33 votes
10 answers
6k views

Is the empty graph a tree?

This is a boring, technical question that I stumbled upon while making a contribution to Sage. I would still like to hear a constructive answer so hopefully the question does not get closed. The ...
Jernej's user avatar
  • 3,433
33 votes
4 answers
3k views

In what rigorous sense are Sperner's Lemma and the Brouwer Fixed Point Theorem equivalent?

I understand that one can give a proof of each of these propositions assuming the truth of the other. But this seems a bit squishy to me, since there is a trivial sense in which any two true theorems ...
James Propp's user avatar
  • 19.4k
32 votes
3 answers
2k views

A double grading of catalan numbers

This is something I found in trying to work on Vince Vatter's excellent question. I have no solution, but a much more precise conjecture. Recall that a rooted planar tree is a rooted tree where, for ...
David E Speyer's user avatar
31 votes
6 answers
5k views

What is known about this plethysm?

Let $S^{\lambda}$ be a Schur functor. Is there a known positive rule to compute the decomposition of $S^{\lambda}(\bigwedge^2 \mathbb{C}^n)$ into $GL_n(\mathbb{C})$ irreps? In response to Vladimir's ...
David E Speyer's user avatar
30 votes
7 answers
67k views

Notation for the all-ones vector [closed]

What's the most common way of writing the all-ones vector, that is, the vector, when projected onto each standard basis vector of a given vector space, having length one? The zero vector is frequently ...
Bkkbrad's user avatar
  • 419
30 votes
4 answers
1k views

Resolution of multiple edges

Given $k$ girls, they are given $kn$ balls so that each girl has $n$ balls. Balls are coloured with $n$ colours so that there are $k$ balls of each colour. Two girls may exchange the balls (1 ball for ...
Fedor Petrov's user avatar
30 votes
8 answers
2k views

Cryptomorphisms

I am curious to collect examples of equivalent axiomatizations of mathematical structures. The two examples that I have in mind are Topological Spaces. These can be defined in terms of open sets, ...
29 votes
2 answers
1k views

Determining if a rational function has a subtraction-free expression

This question was first asked by Mehtaab Sawhney in Alex Postnikov's combinatorics class. Given a rational function $F=P(x_1,...,x_n)/Q(x_1,...,x_n)$ with (say) integer coefficients, it is often of ...
Christian Gaetz's user avatar
28 votes
5 answers
2k views

Visibility of vertices in polyhedra

Suppose $P$ is a closed polyhedron in space (i.e. a union of polygons which is homeomorphic to $S^2$) and $X$ is an interior point of $P$. Is it true that $X$ can see at least one vertex of $P$? More ...
Mostafa's user avatar
  • 4,454
28 votes
7 answers
8k views

Solving NP problems in (usually) Polynomial time?

Just because a problem is NP-complete doesn't mean it can't be usually solved quickly. The best example of this is probably the traveling salesman problem, for which extraordinarily large instances ...
DoubleJay's user avatar
  • 2,353
28 votes
2 answers
3k views

Erdős-Szekeres for first differences

The classical Erdős-Szekeres theorem says that any sequence of $n^2+1$ real numbers contains a monotonic $(n+1)$-term subsequence. Suppose, however, that we want to find a subsequence which is not ...
Seva's user avatar
  • 22.8k
26 votes
5 answers
1k views

Is the matrix $\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}$ nonsingular?

Suppose we have a $(2m-1) \times (2m-1)$ matrix defined as follows: $$\left({2m\choose 2j-i}\right)_{i,j=1}^{2m-1}.$$ For example, if $m=3$, the matrix is $$\begin{pmatrix}6 & 20 & 6& 0 ...
user42804's user avatar
  • 1,091
26 votes
2 answers
1k views

Partitions to different parts not exceeding $n$

Consider the polynomial $(1+x)(1+x^2)\dots (1+x^n)=1+x+\dots+x^{n(n+1)/2}$, which enumerates subj. How to prove that it's coefficients increase up to $x^{n(n+1)/4}$ (and hence decrease after this)? Or ...
Fedor Petrov's user avatar
25 votes
5 answers
5k views

Complete graph invariants?

Obviously, graph invariants are wonderful things, but the usual ones (the Tutte polynomial, the spectrum, whatever) can't always distinguish between nonisomorphic graphs. Actually, I think that even a ...
Harrison Brown's user avatar
24 votes
5 answers
3k views

What is the minimum N for which there exist N points in the plane that cannot be covered by any number of non-overlapping closed unit discs?

This problem was posed in March 2010 at G4G9 in a talk by the Japanese mathematician Hirokazu "Iwahiro" Iwasawa. He claims there is a simple proof that N > 10, though he did not share it with the ...
jordancurve's user avatar
23 votes
8 answers
2k views

Can we disallow finite choice?

When people work with infinite sets, there are some who (with good reason) don't like to use the Axiom of Choice. This is defensible, since the axiom is independent of the other axioms of ZF set ...
Harrison Brown's user avatar
23 votes
3 answers
3k views

How many different numbers can be obtained as product of first $n$ natural numbers?

Let m and n be natural numbers, and consider the set of all possible products of m (not necessarily distinct) elements from the set $\{1,2,\ldots,n\}$, that is consider the set $\{1^{a_1} \cdot 2^{...
Hujdurovic's user avatar
23 votes
2 answers
3k views

Calculating Mayer-Vietoris efficiently

This is a question whose motivation and framing seem to involve a lot of topology, but which I suspect comes down to some simple and standard combinatorics that's probably recorded in a book somewhere....
David E Speyer's user avatar
22 votes
6 answers
5k views

The matrix tree theorem for weighted graphs

I am interested in the general form of the Kirchoff Matrix Tree Theorem for weighted graphs, and in particular what interesting weightings one can choose. Let $G = (V,E, \omega)$ be a weighted graph ...
bc919's user avatar
  • 323
21 votes
3 answers
2k views

Sampling from the Birkhoff polytope

The set of $n\times n$ real, nonnegative matrices whose rows and columns sum to one forms the well-known Birkhoff polytope Recently someone asked me if I knew How to sample (in polynomial time) ...
Suvrit's user avatar
  • 28.4k
21 votes
6 answers
2k views

Sperner's lemma and paths from one side to the opposite one in a grid

I recently found this nice puzzle: Given an $n \times n$ grid where we draw at random one diagonal in each of the $1 \times 1$ squares, then we can always find a path using these small diagonals that ...
Cosmin Pohoata's user avatar
21 votes
1 answer
623 views

Counting categories with at most $n$ morphisms

There are a number of results which count the number of possible algebraic structures on a set of $n$ elements. Notable previous MO questions are for example here and here. The analogous question for ...
Espen Nielsen's user avatar
21 votes
2 answers
1k views

3D generalizations of permutations, RSK correspondence, contingency tables, etc.

I want to gather facts and questions related to 3D generalizations of permutations, RSK correspondence, contingency tables, etc. One reason I am interested in this is because it is potentially related ...
Jonah Blasiak's user avatar

1 2 3
4
5
30