Unanswered Questions
3,137 questions with no upvoted or accepted answers
55
votes
0
answers
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 ...
- 2,598
51
votes
0
answers
2k
views
Does every triangle-free graph with maximum degree at most 6 have a 5-colouring?
A very specific case of Reed's Conjecture
Reed's $\omega$,$\Delta$, $\chi$ conjecture proposes that every graph has $\chi \leq \lceil \tfrac 12(\Delta+1+\omega)\rceil$. Here $\chi$ is the chromatic ...
CommunityBot
- 1
45
votes
0
answers
3k
views
A = B (but not quite); 3-d arrays with multiple recurrences
Many years ago, I discovered the remarkable array (apparently originally discovered by Ramanujan)
1
1 3
2 10 15
6 40 105 105
24 196 700 1260 945
...
- 33.5k
41
votes
0
answers
1k
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 ...
- 62.6k
36
votes
0
answers
2k
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 = (\alpha,...
- 16.8k
35
votes
0
answers
949
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 $...
- 5,981
32
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,341
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.
...
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,429
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$,
...
CommunityBot
- 1
29
votes
0
answers
1k
views
Linking formulas by Euler, Pólya, Nekrasov-Okounkov
Consider the formal product
$$F(t,x,z):=\prod_{j=0}^{\infty}(1-tx^j)^{z-1}.$$
(a) If $z=2$ then on the one hand we get Euler's
$$F(t,x,2)=\sum_{n\geq0}\frac{(-1)^nx^{\binom{n}2}}{(x;x)_n}t^n,$$
on the ...
CommunityBot
- 1
29
votes
0
answers
3k
views
Why do polytopes pop up in Lagrange inversion?
I'd be interested in hearing people's viewpoints on this. Looking for an intuitive perspective. See Wikipedia for descriptions of polytopes and the Lagrange inversion theorem/formula (LIF) for ...
- 10.2k
27
votes
0
answers
619
views
A conjecture about inclusion–exclusion
$\newcommand\calF{\mathcal{F}}
\def\cupdot {\stackrel{\bullet}{\cup}}
\def\minusdot {\stackrel{\bullet}{\setminus}}$This post presents a conjecture that we have with some colleagues. It is about ...
- 23.1k
27
votes
0
answers
890
views
A question on simultaneous conjugation of permutations
Given $a,b\in S_n$ such that their commutator has at least $n-4$ fixed points, is there an element $z\in S_n$ such that $a^z=a^{-1}$, and $b^z=b^{-1}$? Here $a^z:=z^{-1}az$.
Magma says that the ...
- 33.5k
26
votes
0
answers
904
views
Which sets of roots of unity give a polynomial with nonnegative coefficients?
The question in brief: When does a subset $S$ of the complex $n$th roots of unity have the property that
$$\prod_{\alpha\, \in \,S} (z-\alpha)$$
gives a polynomial in $\mathbb R[z]$ with ...
- 13.3k
24
votes
0
answers
752
views
How much of the plane is 4-colorable?
In 1981, Falconer proved that the measurable chromatic number of the plane is at least 5. That is, there are no measurable sets $A_1,A_2,A_3,A_4\subseteq\mathbb{R}^2$, each avoiding unit distances, ...
- 7,593
24
votes
0
answers
486
views
Is the Poset of Graphs Automorphism-free?
For $n\geq 5$, let $\mathcal {P}_n$ be the set of all isomorphism classes of graphs with n vertices. Give this set the poset structure given by $G \le H$ if and only if $G$ is a subgraph of $H$.
Is ...
23
votes
0
answers
1k
views
Do all possible trees arise as orbit trees of some permutation groups?
I.Motivation from descriptive set theory
(Contains some quotes from Maciej Malicki's paper.)
The classical theorem of Birkhoff-Kakutani implies that every metrizable topological group G admits a ...
CommunityBot
- 1
22
votes
0
answers
544
views
Zero curves of Tutte Polynomials?
There is an extensive theory of the real and complex roots of the chromatic polynomial of a graph, a substantial fraction of this being due to the connections between the chromatic polynomial and a ...
- 12.3k
22
votes
0
answers
805
views
Combinatorics of Quantum Schubert Polynomials
Let $S_n$ be the symmetric group. Let $s_i$ denote the adjacent transposition $(i \ i+1)$. For any permutation $w\in S_n$, an expression $w=s_{i_1}s_{i_2}\cdots s_{i_p}$ of minimal possible length is ...
- 13.3k
22
votes
0
answers
3k
views
Origins of the Nerve Theorem
Recently, I've read two papers which have cited the Nerve Theorem, one crediting Borsuk with the result and another Leray. Here is the question:
Who was the first to prove the Nerve Theorem?
- 24.4k
21
votes
0
answers
430
views
Straight-line drawing of regular polyhedra
Find the minimum number of straight lines needed to cover a crossing-free straight-line drawing of the icosahedron $(13\dots 15)$ and of the dodecahedron $(9\dots 10)$ (in the plane).
For example, ...
- 4,282
21
votes
0
answers
597
views
Coloring a Ferrers diagram
I've shopped the problem below around a bit and it seems like it might be known, or not that hard to resolve, but so far I've come up empty-handed.
Say that a coloring of the dots of a Ferrers ...
- 80.3k
21
votes
0
answers
2k
views
The Fourier Transform of taking Eigenvalues
The purpose of this question is to ask about the Fourier transform of the map which associate to an $n$ by $n$ matrix its $n$ eigenvalues, or some function of the $n$ eigenvalues. The main motivation ...
- 51.9k
21
votes
0
answers
902
views
Cauchy matrices with elementary symmetric polynomials
$\newcommand{\vx}{\mathbf{x}}$
Let $e_k(\vx)$ denote the elementary symmetric polynomial, defined for $k=0,1,\ldots,n$ over a vector $\vx=(x_1,\ldots,x_n)$ by
\begin{equation*}
e_k(\vx) := \sum_{1 \...
- 28.5k
21
votes
1
answer
1k
views
Tiling rectangle with trominoes — an invariant
There are two types of trominoes, straight shapes and L-shaped. Suppose a rectangle $R$ admits at least one tiling using trominoes, with an even number of L-trominoes.
EDIT: we do not admit ALL ...
CommunityBot
- 1
20
votes
0
answers
559
views
Hall's Marriage Theorem and intervals
In Hall's Marriage Theorem, we have a set $B$ of brides and $G$ of
grooms, where each bride $b$ has an acceptable set $A_b \subseteq G$
of grooms. A matching $m:B\to G$ is an injection such that $m(b)
...
- 27.7k
19
votes
0
answers
595
views
Large values of characters of the symmetric group
For $g$ an element of a group and $\chi$ an irreducible character, there are two easy bounds for the character value $\chi(g)$: First, the bound $|\chi(g)|\leq \chi(1)$ by the dimension of the ...
- 1
19
votes
0
answers
420
views
Row of the character table of symmetric group with most negative entries
The row of the character table of $S_n$ corresponding to the trivial representation has all entries positive, and by orthogonality clearly it is the only one like this.
Is it true that for $n\gg 0$, ...
- 23.1k
19
votes
0
answers
611
views
Simpler proofs of certain Ramsey numbers
The reason for the gorgeous simplicity of the classic proofs of $R(3,3)$, $R(4,4)$, $R(3,4)$ and $R(3,5)$ is that essentially all you need is the trivial bound and a picture.
But for bigger Ramsey ...
- 17.5k