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.
1,469
questions
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 ...
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 ...
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 ...
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 ...
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 ...
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
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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\...
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 ...
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} $ ...
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, ...
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}{...
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; ...
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 ...
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 ...
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$ ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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^{...
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....
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 ...
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) ...
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 ...
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 ...
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 ...