Recent Activity

Hilbert-Smith conjecture ★★

Author(s): David Hilbert; Paul A. Smith

\begin{conjecture} Let $G$ be a locally compact topological group. If $G$ has a continuous faithful group action on an $n$-manifold, then $G$ is a \Def{Lie group}. \end{conjecture}


trace inequality ★★


Let $A,B$ be positive semidefinite, by Jensen's inequality, it is easy to see $[tr(A^s+B^s)]^{\frac{1}{s}}\leq [tr(A^r+B^r)]^{\frac{1}{r}}$, whenever $s>r>0$.

What about the $tr(A^s+B^s)^{\frac{1}{s}}\leq tr(A^r+B^r)^{\frac{1}{r}}$, is it still valid?


Real roots of the flow polynomial ★★

Author(s): Welsh

\begin{conjecture} All real roots of nonzero flow polynomials are at most 4. \end{conjecture}

Keywords: flow polynomial; nowhere-zero flow

Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

\begin{question} Is every \Def{Cayley graph} Hamiltonian? \end{question}


Finite Lattice Representation Problem ★★★★


\begin{conjecture} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. There exists a finite lattice which is not the congruence lattice of a finite algebra. \end{conjecture}

Keywords: congruence lattice; finite algebra

Outer reloid of restricted funcoid ★★

Author(s): Porton

\begin{question} $( \mathsf{RLD})_{\mathrm{out}} (f \cap^{\mathsf{FCD}} ( \mathcal{A} \times^{\mathsf{FCD}} \mathcal{B})) = (( \mathsf{RLD})_{\mathrm{out}} f) \cap^{\mathsf{RLD}} ( \mathcal{A} \times^{\mathsf{RLD}} \mathcal{B})$ for every filter objects $\mathcal{A}$ and $\mathcal{B}$ and a funcoid $f\in\mathsf{FCD}(\mathrm{Src}\,f; \mathrm{Dst}\,f)$? \end{question}

Keywords: direct product of filters; outer reloid

Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

\begin{conjecture} Is it possible to color edges of the complete graph $K_n$ using $O(n)$ colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?

Equivalently: is the star chromatic index of $K_n$ linear in $n$? \end{conjecture}

Keywords: complete graph; edge coloring; star coloring

Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index $\chi_s'(G)$ of a graph $G$ is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.

\begin{question} Is it true that for every (sub)cubic graph $G$, we have $\chi_s'(G) \le 6$? \end{question}

Keywords: edge coloring; star coloring

Inscribed Square Problem ★★

Author(s): Toeplitz

\begin{conjecture} Does every \Def{Jordan curve} have 4 points on it which form the vertices of a square? \end{conjecture}

Keywords: simple closed curve; square

Lindelöf hypothesis ★★

Author(s): Lindelöf

\begin{conjecture} For any $\epsilon>0$ $$\zeta\left(\frac12 + it\right) \mbox{ is }\mathcal{O}(t^\epsilon).$$

Since $\epsilon$ can be replaced by a smaller value, we can also write the conjecture as, for any positive $\epsilon$, $$\zeta\left(\frac12 + it\right) \mbox{ is }o(t^\varepsilon).$$ \end{conjecture}

Keywords: Riemann Hypothesis; zeta

Termination of the sixth Goodstein Sequence

Author(s): Graham

\begin{question} How many steps does it take the sixth Goodstein sequence to terminate? \end{question}

Keywords: Goodstein Sequence

Consecutive non-orientable embedding obstructions ★★★


\begin{conjecture} Is there a graph $G$ that is a minor-minimal obstruction for two non-orientable surfaces? \end{conjecture}

Keywords: minor; surface

Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let $R(k,k)$ denote the $k^{th}$ diagonal \Def[Ramsey number]{ramsey number}.

\begin{conjecture} $\lim_{k \rightarrow \infty} R(k,k) ^{\frac{1}{k}}$ exists. \end{conjecture}

\begin{problem} Determine the limit in the above conjecture (assuming it exists). \end{problem}

Keywords: Ramsey number

The 4x5 chessboard complex is the complement of a link, which link? ★★

Author(s): David Eppstein

\begin{problem} Ian Agol and Matthias Goerner observed that the 4x5 chessboard complex is the complement of many distinct links in the 3-sphere. Their observation is non-constructive, as it uses the resolution of the Poincare Conjecture. Find specific links that have the 4x5 chessboard complex as their complement. \end{problem}

Keywords: knot theory, links, chessboard complex

Elementary symmetric of a sum of matrices ★★★


\begin{problem} % Enter your conjecture in LaTeX Given a Matrix $A$, the $k$-th \Def{elementary symmetric function} of $A$, namely $S_k(A)$, is defined as the sum of all $k$-by-$k$ principal minors.

Find a closed expression for the $k$-th elementary symmetric function of a sum of N $n$-by-$n$ matrices, with $0\le N\le k\le n$ by using partitions.



Monochromatic empty triangles ★★★


If $X \subseteq {\mathbb R}^2$ is a finite set of points which is 2-colored, an \emph{empty triangle} is a set $T \subseteq X$ with $|T|=3$ so that the convex hull of $T$ is disjoint from $X \setminus T$. We say that $T$ is \emph{monochromatic} if all points in $T$ are the same color.

\begin{conjecture} There exists a fixed constant $c$ with the following property. If $X \subseteq {\mathbb R}^2$ is a set of $n$ points in general position which is 2-colored, then it has $\ge cn^2$ monochromatic empty triangles. \end{conjecture}

Keywords: empty triangle; general position; ramsey theory

Edge-antipodal colorings of cubes ★★

Author(s): Norine

We let $Q_d$ denote the $d$-dimensional cube graph. A map $\phi : E(Q_d) \rightarrow \{0,1\}$ is called \emph{edge-antipodal} if $\phi(e) \neq \phi(e')$ whenever $e,e'$ are antipodal edges.

\begin{conjecture} If $d \ge 2$ and $\phi : E(Q_d) \rightarrow \{0,1\}$ is edge-antipodal, then there exist a pair of antipodal vertices $v,v' \in V(Q_d)$ which are joined by a monochromatic path. \end{conjecture}

Keywords: antipodal; cube; edge-coloring

Exponential Algorithms for Knapsack ★★

Author(s): Lipton

\begin{conjecture} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. The famous 0-1 Knapsack problem is: Given $a_{1},a_{2},\dots,a_{n}$ and $b$ integers, determine whether or not there are $0-1$ values $x_{1},x_{2},\dots,x_{n}$ so that $$ \sum_{i=1}^{n} a_{i}x_{i} = b.$$ The best known worst-case algorithm runs in time $2^{n/2}$ times a polynomial in $n$. Is there an algorithm that runs in time $2^{n/3}$?


Keywords: Algorithm construction; Exponential-time algorithm; Knapsack

Unsolvability of word problem for 2-knot complements ★★★

Author(s): Gordon

\begin{problem} Does there exist a smooth/PL embedding of $S^2$ in $S^4$ such that the fundamental group of the complement has an unsolvable word problem? \end{problem}

Keywords: 2-knot; Computational Complexity; knot theory

Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

\begin{question} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. Is there an algorithm that decides, for input graphs $G$ and $H$, whether there exists a homomorphism from $G$ to $H$ in time $O(c^{|V(G)|+|V(H)|})$ for some constant $c$? \end{question}

Keywords: algorithm; Exponential-time algorithm; homomorphism