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

6,446 questions

**34**

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

**34**

votes

**0**answers

2k views

### Curious $q$-analogues

Consider the Fibonacci polynomials
$$F_n (x) = \sum_{j = 0}^{\left\lfloor {n/2} \right\rfloor }\binom{n-j}{j} x^{n - 2j} $$
and the Lucas polynomials
$$L_n (x) = \sum_{j = 0}^{\left\lfloor {n/2} \...

**33**

votes

**3**answers

2k views

### Fibonacci series captures Euler $e=2.718\dots$

The Fibonacci recurrence $F_n=F_{n-1}+F_{n-2}$ allows values for all indices $n\in\mathbb{Z}$. There is an almost endless list of properties of these numbers in all sorts of ways. The below question ...

**33**

votes

**2**answers

3k views

### Projective Plane of Order 12

I asked this question on the new Theoretical Computer Science "overflow" site, and commenters suggested I ask it here. That question is here, and it contains additional links, which I doubt I can ...

**33**

votes

**4**answers

1k views

### Graph containing all trees?

Consider graphs on $n$ nodes. I am trying to find a graph $G$ that contains all $n$-node trees as sub-graphs but contains as few edges as possible. The complete graph $K_n$ suffices, but can we get ...

**33**

votes

**5**answers

44k views

### How large is TREE(3)?

Friedman, in http://www.math.osu.edu/~friedman.8/pdf/EnormousInt112201.pdf, shows that TREE(3) is much larger than n(4), itself bounded below by $A^{A(187195)}(3)$ (where $A$ is the Ackerman ...

**33**

votes

**1**answer

2k views

### “The Two Sheriffs” puzzle

This puzzle is taken from the book Mathematical puzzles: a connoisseur's collection by P. Winkler.
Two sheriffs in neighboring towns are on the track of a killer, in a
case involving eight ...

**33**

votes

**4**answers

3k views

### Cliques, Paley graphs and quadratic residues

A question I've thought about, on and off for a long time, is how to improve the best bounds that (seem to be) known for the clique numbers of Paley graphs.
If p=1 mod 4 is a prime, we can define the ...

**33**

votes

**1**answer

2k views

### orders of products of permutations

Let $p$ be a prime, $n\gg p$ not divisible by $p$ (say, $n>2^{2^p}$). Are there two permutations $a, b$ of the set $\{1,...,n\}$ which together act transitively on $\{1,2,...,n\}$ and such that all ...

**33**

votes

**0**answers

759 views

### Is there anything to the obvious analogy between Joyal's combinatorial species and Goodwillie calculus?

Combinatorial species and calculus of functors both take the viewpoint that many interesting functors can be expanded in a kind of Taylor series. Many operations familiar from actual calculus can be ...

**32**

votes

**18**answers

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

**32**

votes

**8**answers

172k views

### The factorial of -1, -2, -3,

Well, $n!$ is for integer $n < 0$ not defined — as yet.
So the question is:
How could a sensible generalization of the factorial for negative integers look like?
Clearly a good generalization ...

**32**

votes

**2**answers

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

**32**

votes

**5**answers

2k views

### Icon Arrangement on Desktop

Story
I was bored sitting in front of my computer and using a rectangle to select icons on my screen. I could select $1$, $2$, $3$, $4$, but not $5$ icons.
(Black squares are the icons. Note that it ...

**32**

votes

**3**answers

1k views

### chromatic number of the hyperbolic plane

A notorious problem in combinatorics is the following:
If we color $\mathbb{R}^2$ so that no pair of points at unit distance get the same color, what is the fewest number of colors required?
This ...

**32**

votes

**1**answer

2k views

### Fourier transform on the discrete cube

Notation: identify an element of $\{-1,1\}^n$ with the set $S \subseteq \{1, \ldots, n\}$ on which it takes the value $-1$.
The following is an asymptotic question. "Close to one" means "more than $...

**31**

votes

**7**answers

2k views

### List of proofs where existence through probabilistic method has not been constructivised

The probabilistic method as first pioneered by Erdős (although others have used this before) shows the existence of a certain object. What are some of the most important objects for which we can show ...

**31**

votes

**1**answer

4k views

### Are the norms of graphs dense in any interval?

It is known that there is a gap between 2 and the next largest norm of a graph.
Is there an interval of the real line in which norms of graphs are dense?

**31**

votes

**6**answers

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

**31**

votes

**3**answers

3k views

### How much linear algebra can be done with graphs?

Let G be a finite directed acyclic graph, with sources $A=\{a_1,\ldots,a_n\}$ and sinks $B=\{b_1,\ldots,b_n\}$, with edge weights $w_{ij}$. The weight of a directed path P is the product of weights of ...

**31**

votes

**4**answers

2k views

### Probability of zero in a random matrix

Let $M(n,k)$ be the set of $n\times n$ matrices of nonnegative integers such that every row and every column sums to $k$. Let $P(n,k)$ be the fraction of such matrices which have no zero entries, ...

**31**

votes

**4**answers

2k views

### A puzzle with some jumping frogs

(The following puzzle is ispired by this nice video of Gordon Hamilton on Numberphile)
In a pond there are $n$ leaves placed in a circle, for convenience they are numbered clockwise by $0,1,\ldots,n-...

**31**

votes

**1**answer

3k views

### Is the set of primes “translation-finite”?

The definition in the title probably needs explaining. I should say that the question itself was an idea I had for someone else's undergraduate research project, but we decided early on it would be ...

**31**

votes

**1**answer

2k views

### tiling a rectangle with the smallest number of squares

This is based on another thread. For $m,n\in \mathbb N$, let $f(m,n)$ be the minimum number of squares with integer sides needed to tile a $m\times n$ rectangle. Recently, a table of values for $n\le ...

**31**

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

**31**

votes

**0**answers

977 views

### 3-colorings of the unit distance graph of $\Bbb R^3$

Let $\Gamma$ be the unit distance graph of $\Bbb R^3$: points $(x,y)$ form an edge if $|x,y|=1$.
Let $(A,B,C,D)$ be a unit side rhombus in the plane, with a transcendental diagonal, e.g. $A = (\...

**30**

votes

**3**answers

1k views

### Combinatorial identity: $\sum_{i,j \ge 0} \binom{i+j}{i}^2 \binom{(a-i)+(b-j)}{a-i}^2=\frac{1}{2} \binom{(2a+1)+(2b+1)}{2a+1}$

In my research, I found this identity and as I experienced, it's surely right. But I can't give a proof for it.
Could someone help me?
This is the identity:
let $a$ and $b$ be two positive integers; ...

**30**

votes

**3**answers

3k views

### Can assignment solve stable marriage?

This is an excellent question asked by one of my students. I imagine the answer is "no", but it doesn't strike me as easy.
Recall the set up of the stable marriage problem. We have $n$ men and $n$ ...

**30**

votes

**3**answers

3k views

### Is there a reset sequence?

There is a question someone (I'm hazy as to who) told me years ago. I found it fascinating for a time, but then I forgot about it, and I'm out of touch with any subsequent developments. Can anyone ...

**30**

votes

**4**answers

2k views

### Tiling A Rectangle With A Hint of Magic

Here's a a famous problem:
If a rectangle $R$ is tiled by rectangles $T_i$ each of which has at least one integer sidelength, then the tiled rectangle $R$ has at least one integer side length.
$\...

**30**

votes

**2**answers

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

**30**

votes

**3**answers

1k views

### “Nyldon words”: understanding a class of words factorizing the free monoid increasingly

BACKGROUND.
Let me first introduce some classical definitions, which appear, e.g., in §5 of Lothaire's Combinatorics on Words, in §5.1 of Reutenauer's Free Lie algebras, and in §6.1 of Victor Reiner'...

**30**

votes

**2**answers

2k views

### Shimura-Taniyama-Weil VS Grothendieck's dessins

When listening to the beautiful lectures by Gilles Schaeffer at
the SLC68, the following (perhaps crazy) question occurred to me:
did anyone attempt (succeed?) to combinatorially prove modularity of ...

**30**

votes

**1**answer

852 views

### partition of infinite word onto permitted words

Consider words over binary alphabet $\{0,1\}$. Let $M$ be a set of finite words such that $M$ contains at least $c\cdot 2^n$ words of length $n$ for all large enough $n$ (for a constant $c$, $0<c&...

**30**

votes

**1**answer

1k views

### Mysterious symmetry - in search for a bijection

I have a mysterious symmetry that I have not managed to prove.
First some definitions (see picture below)
Fix a partition that fit in a staircase shape with $n$ rows.
There are $Catalan(n)$ such ...

**30**

votes

**5**answers

2k views

### Does every bipartite graph with 512 edges have an induced subgraph with 256 edges?

Suppose we have a (simple) bipartite graph with $2^k$ edges. Is it true that there is a subset of the vertices such that their induced subgraph has exactly $2^{k-1}$ edges?
I know that the answer is ...

**30**

votes

**1**answer

959 views

### Why does McMahon formula look like the inclusion-exclusion principle?

The McMahon formula for the number of tilings of an $a \times b \times c$ hexagon by lozenges:
$$ \Big[H(a)H(b)H(c)\Big] \Big[H(a+b)H(b+c)H(c+a)\Big]^{-1} \Big[H(a+b+c)\Big]$$
looks oddly like the ...

**30**

votes

**1**answer

3k views

### An edge partitioning problem on cubic graphs

Hello everyone,
I already asked this question on the TCS Stack Exchange, but it has not been resolved yet. Maybe readers of this forum will have other ideas or information, although I suspect that ...

**30**

votes

**0**answers

2k views

### A Combinatorial Abstraction for The “Polynomial Hirsch Conjecture”

Consider $t$ disjoint families of subsets of {1,2,…,n}, ${\cal F}_1,{\cal F_2},\dots {\cal F_t}$ .
Suppose that
(*)
For every $i \lt j \lt k$
and every $R \in {\cal F}_i$, and $T \in {\cal F}_k$, ...

**29**

votes

**7**answers

3k views

### Examples of integer sequences coincidences

For the time being, the OEIS website contains almost $300000$ sequences. Each of these sequences is the mark of a specific mathematical concept. Sometimes two (or more) distinct concepts have the ...

**29**

votes

**4**answers

2k views

### Is it possible to define higher cardinal arithmetics

In number theory there are several operators like addition, multiplication and exponentiation defined from $\omega\times\omega$ to $\omega$. Each of them is defined as an ...

**29**

votes

**4**answers

3k views

### How does this relationship between the Catalan numbers and SU(2) generalize?

This is a question, or really more like a cloud of questions, I wanted to ask awhile ago based on this SBS post and this post I wrote inspired by it, except that Math Overflow didn't exist then.
As ...

**29**

votes

**1**answer

701 views

### Number of irreducible representations of a finite group over a field of characteristic 0

Let $G$ be a finite group and $K$ a field with $\mathbb{Q} \subseteq K \subseteq \mathbb{C}$.
For $K=\mathbb{C}$ the number of irreducible representations of $KG$ is equal to the number of conjugacy ...

**29**

votes

**4**answers

1k views

### Stirling number identity via homology?

This is a question about the well-known formula involving both types of Stirling numbers:
$\sum_{k=1}^{\infty}(-1)^{k}S(n,k)c(k,m)=0$,
where $S(n,k)$ is the number of partitions of an $n$-element set ...

**28**

votes

**6**answers

12k views

### How many surjections are there from a set of size n?

It is well-known that the number of surjections from a set of size n to a set of size m is quite a bit harder to calculate than the number of functions or the number of injections. (Of course, for ...

**28**

votes

**10**answers

2k views

### Open questions about posets

Partially ordered sets (posets) are important objects in combinatorics (with basic connections to extremal combinatorics and to algebraic combinatorics) and also in other areas of mathematics. They ...

**28**

votes

**5**answers

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

**28**

votes

**2**answers

2k views

### When does doubling the size of a set multiply the number of subsets by an integer?

For natural numbers $m, r$, consider the ratio of the number of subsets of size $m$ taken from a set of size $2(m+r)$ to the number of subsets of the same size taken from a set of size $m+r$:
$$R(m,r)...

**28**

votes

**2**answers

7k views

### Mean minimum distance for N random points on a one-dimensional line

Let's say that I have a one-dimensional line of finite length 'L' that I populate with a set of 'N' random points. I was wondering if there was a simple/straightforward method (not involving long ...

**28**

votes

**3**answers

4k views

### Is there a good argument for why you can't place 4 queens which cover a chessboard?

It has been known since the 1850's (or even much earlier) that 5 queens could be placed on an 8*8
chessboard so that every square on the board lies in the same row, column, or diagonal as at least ...