All Questions
Tagged with combinatorics or co.combinatorics
11,024 questions
35
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 side length, then the tiled rectangle $R$ has at least one integer side length.
There ...
- 4,952
35
votes
2
answers
2k
views
What is the oriented Fano plane?
One way to remember the multiplication table of the octonions is to use the following diagram (which I got from John Baez's online paper): if $(e_i,e_j,e_k)$ is one of the lines listed according to ...
- 47.3k
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 ...
- 2,993
35
votes
0
answers
1k
views
Orthogonal vectors with entries from $\{-1,0,1\}$
Let $\mathbf{1}$ be the all-ones vector, and suppose $\mathbf{1}, \mathbf{v_1}, \mathbf{v_2}, \ldots, \mathbf{v_{n-1}} \in \{-1,0,1\}^n$ are mutually orthogonal non-zero vectors. Does it follow that $...
- 6,351
34
votes
18
answers
20k
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 ...
- 349
34
votes
16
answers
7k
views
Generalizations of the Birkhoff-von Neumann Theorem
The famous Birkhoff-von Neumann theorem asserts that every doubly stochastic matrix can be written as a convex combination of permutation matrices.
The question is to point out different ...
- 24.7k
34
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 ...
- 19.7k
34
votes
1
answer
2k
views
Two-colouring the two-sphere
Suppose that $S^2$ is the unit sphere in $\mathbb{R}^3$.
Is there a function $f \colon S^2 \to \{0,1\}$ so that, for any orthonormal basis $(u,v,z)$, exactly one of the values $f(u)$, $f(v)$, and $f(...
- 679
34
votes
4
answers
3k
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 ...
- 32.1k
34
votes
2
answers
3k
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 ...
34
votes
1
answer
789
views
Which graphs on $n$ vertices have the largest determinant?
This is a question that seems like it should have been studied before, but for some reason I cannot find much at all about it, and so I am asking for any pointers / references etc.
The determinant of ...
- 12.7k
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 ...
- 3,463
33
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 ...
33
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 ...
33
votes
1
answer
2k
views
Is there a configuration of 5 points on the plane where any two can be covered by an axis aligned rectangle?
I'm trying to figure out the question in the title for a project that I'm working on.
My goal is to find a configuration of five integer points on the plane, where we can overlap any pair of them ...
- 473
33
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$ ...
- 156k
33
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?
- 528
33
votes
5
answers
3k
views
What's the motivation of entropy as a combinatorical tool? What problems is it able to solve?
I am interested in using Shannon's entropy in combinatorics. It is often presented with a motivation of how much information can be passed, but assume I am not interested in that, I want to understand ...
- 515
33
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 ...
- 156k
33
votes
1
answer
7k
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 ...
- 13.4k
33
votes
1
answer
3k
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 $...
- 42.8k
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 ...
- 457
33
votes
1
answer
1k
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 ...
- 22.8k
33
votes
0
answers
2k
views
The easily bored sequence
If we want to compare the repetitiveness of two finite words, it looks reasonable, first of all, to consider more repetitive the word repeating more times one of its factors, and secondarily to ...
- 4,459
32
votes
3
answers
3k
views
A conjectural trigonometric identity
Recently, I formulated the following conjecture which seems novel.
Conjecture. For any positive odd integer $n$, we have the identity
$$\sum_{j,k=0}^{n-1}\frac1{\cos 2\pi j/n+\cos 2\pi k/n}=\frac{n^2}...
- 15.6k
32
votes
7
answers
71k
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 ...
- 439
32
votes
3
answers
2k
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; ...
- 321
32
votes
2
answers
1k
views
Do graphs with an odd number of walks of length $\ell$ between any two vertices exist?
Given $\ell\ge 1$, we say a graph $G$ is $\ell$-good if for each $u,v\in G$ (not necessarily distinct), the number of walks of length $\ell$ from $u$ to $v$ is odd. We say a graph $G$ is good if it is ...
- 3,499
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 ...
- 384
32
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 ...
- 25.1k
32
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 ...
- 22.1k
32
votes
5
answers
9k
views
How many binary operations are associative?
Let $X$ be a finite set of $n$ elements, and consider a binary operation $\odot: X \times X \rightarrow X$. There are $n^{n^2}$ such binary operations, as the $n \times n$ table entries can each
be ...
- 151k
32
votes
3
answers
3k
views
Order of products of elements in symmetric groups
Let $n \in \mathbb{N}$. Is it true that for any $a, b, c \in \mathbb{N}$ satisfying
$1 < a, b, c \leq n-2$ the symmetric group ${\rm S}_n$ has elements of order $a$ and $b$
whose product has order $...
- 19.6k
32
votes
3
answers
2k
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'...
- 33.8k
32
votes
1
answer
2k
views
Is this formal noncommutative power series identity known?
I recently discovered the following cute formal noncommutative power series identity: if $(x_i)_{i \in I}$ is some finite collection of noncommuting variables, then the formal power series
$$ 1 + \...
- 114k
32
votes
0
answers
3k
views
Vertex coloring inherited from perfect matchings (motivated by quantum physics)
Added (19.01.2021): Dustin Mixon wrote a blog post about the question where he reformulated and generalized the question.
Added (25.12.2020): I made a youtube video to explain the question in detail.
...
- 155
32
votes
0
answers
1k
views
Minimal number of intersections in a convex $n$-gon?
For a convex polygon $P$, draw all the diagonals of $P$ and consider the intersection points made by those diagonals. Let $f(n)$ be the minimal number of such intersections where $P$ ranges over all ...
- 1,474
32
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$,
...
- 24.7k
31
votes
7
answers
3k
views
Why are we interested in permutahedra, associahedra, cyclohedra, ...?
The following families of polytopes have received a lot of attention:
permutahedra,
associahedra,
cyclohedra,
...
My question is simple: Why?
As I understand, at least the latter two were ...
- 13.6k
31
votes
11
answers
2k
views
Combinatorial databases
At one point, I remember being excited by seeing the website Encyclopedia of Combinatorial Structures as an extension of Sloane's Online Integer Sequence Database site. Unfortunately, the site (ECS) ...
31
votes
3
answers
10k
views
Cutting a rectangle into an odd number of congruent non-rectangular pieces
We are interested in tiling a rectangle with copies of a single tile (rotations and reflections are allowed). This is very easy to do, by cutting the rectangle into smaller rectangles.
What happens ...
- 1,110
31
votes
2
answers
1k
views
Does the symmetric group $S_{10}$ factor as a knit product of symmetric subgroups $S_6$ and $S_7$?
By knit product (alias: Zappa-Szép product), I mean a product $AB$ of subgroups for which $A\cap B=1$. In particular, note that neither subgroup is required to be normal, thus making this a ...
- 1,068
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 ...
- 156k
31
votes
2
answers
3k
views
Is there a "finitary" solution to the Basel problem?
Gabor Toth's Glimpses of Algebra and Geometry contains the following beautiful proof (perhaps I should say "interpretation") of the formula $\displaystyle \frac{\pi}{4} = 1 - \frac{1}{3} + \frac{1}{5} ...
- 118k
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, ...
- 37.7k
31
votes
4
answers
3k
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-...
user40023
31
votes
2
answers
1k
views
Slick proof related to choosing points from an interval in order
Choose a point anywhere in the unit interval $[0, 1]$. Now choose a second point from the same interval so that there is one point in each half, $[0, \frac12]$ and $[\frac12, 1]$. Now choose a third ...
- 4,994
31
votes
1
answer
1k
views
Vanishing line on Conway's game of life
If the initial state of Conway's game of life is a line of $n \in [0,100]$ alive cells, then it vanishes completely after some steps iff $n \in \{0,1,2,6,14,15,18,19,23,24 \}$. See below for $n=24$.
...
31
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 ...
- 18.8k