Recent Activity

Are all Fermat Numbers square-free? ★★★


\begin{conjecture} Are all Fermat Numbers \[ F_n = 2^{2^{n } } + 1 \] Square-Free?



Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

\begin{conjecture} If $G,H$ are simple finite graphs, then $\chi(G \times H) = \min \{ \chi(G), \chi(H) \}$. \end{conjecture}

Here $G \times H$ is the \Def[tensor product]{tensor product of graphs} (also called the direct or categorical product) of $G$ and $H$.

Keywords: categorical product; coloring; homomorphism; tensor product

Choosability of Graph Powers ★★

Author(s): Noel

\begin{question}[Noel, 2013] Does there exist a function $f(k)=o(k^2)$ such that for every graph $G$, \[\text{ch}\left(G^2\right)\leq f\left(\chi\left(G^2\right)\right)?\] \end{question}

Keywords: choosability; chromatic number; list coloring; square of a graph

Large acyclic induced subdigraph in a planar oriented graph. ★★

Author(s): Harutyunyan

\begin{conjecture} Every planar oriented graph $D$ has an acyclic induced subdigraph of order at least $\frac{3}{5} |V(D)|$. \end{conjecture}


Polignac's Conjecture ★★★

Author(s): de Polignac

\begin{conjecture} Polignac's Conjecture: For any positive even number n, there are infinitely many prime gaps of size n. In other words: There are infinitely many cases of two consecutive prime numbers with difference n. \end{conjecture}

In particular, this implies:

\begin{conjecture} Twin Prime Conjecture: There are an infinite number of twin primes. \end{conjecture}

Keywords: prime; prime gap

Alexa's Conjecture on Primality ★★

Author(s): Alexa

\begin{definition} Let $r_i$ be the unique integer (with respect to a fixed $p\in\mathbb{N}$) such that

$$(2i+1)^{p-1} \equiv r_i \pmod p ~~\text{ and } ~ 0 \le r_i < p. $$ \end{definition} \begin{conjecture} A natural number $p \ge 8$ is a prime iff $$ \displaystyle \sum_{i=1}^{\left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor} r_i = \left \lfloor \frac{\sqrt[3]p}{2} \right \rfloor $$ \end{conjecture}

Keywords: primality

P vs. BPP ★★★

Author(s): Folklore

\begin{conjecture} Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP? \end{conjecture}

Keywords: BPP; circuit complexity; pseudorandom generators

Goldbach conjecture ★★★★

Author(s): Goldbach

\begin{conjecture} Every even integer greater than 2 is the sum of two primes. \end{conjecture}

Keywords: additive basis; prime

Goldberg's conjecture ★★★

Author(s): Goldberg

The \emph{overfull parameter} is defined as follows: \[ w(G) = \max_{H \subseteq G} \left\lceil \frac{ |E(H)| }{ \lfloor \tfrac{1}{2} |V(H)| \rfloor} \right\rceil. \]

\begin{conjecture} Every graph $G$ satisfies $\chi'(G) \le \max\{ \Delta(G) + 1, w(G) \}$. \end{conjecture}

Keywords: edge-coloring; multigraph

Cyclic spanning subdigraph with small cyclomatic number ★★

Author(s): Bondy

\begin{conjecture} Let $D$ be a digraph all of whose strong components are nontrivial. Then $D$ contains a cyclic spanning subdigraph with cyclomatic number at most $\alpha(D)$. \end{conjecture}


inverse of an integer matrix ★★

Author(s): Gregory

\begin{question} I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all $\ge 2$. Suppose X is an m-by-n integer matrix $(m \le n)$. Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.


Keywords: invertable matrices, integer matrices

Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament ★★

Author(s): Yuster

\begin{conjecture} If $T$ is a tournament of order $n$, then it contains $\left \lceil n(n-1)/6 - n/3\right\rceil$ arc-disjoint transitive subtournaments of order 3. \end{conjecture}


Arc-disjoint directed cycles in regular directed graphs ★★

Author(s): Alon; McDiarmid; Molloy

\begin{conjecture} If $G$ is a $k$-regular directed graph with no parallel arcs, then $G$ contains a collection of ${k+1 \choose 2}$ arc-disjoint directed cycles. \end{conjecture}


Jacob Palis Conjecture(Finitude of Attractors)(Dynamical Systems) ★★★★


\begin{conjecture} Let $Diff^{r}(M) $ be the space of $C^{r}$ Diffeomorphisms on the connected , compact and boundaryles manifold M and $\chi^{r}(M)$ the space of $C^{r}$ vector fields. There is a dense set $D\subset Diff^{r}(M)$ ($D\subset \chi^{r}(M)$ ) such that $\forall f\in D$ exhibit a finite number of attractor whose basins cover Lebesgue almost all ambient space $M$ \end{conjecture} This is a very Deep and Hard problem in Dynamical Systems . It present the dream of the dynamicist mathematicians .

Keywords: Attractors , basins, Finite

Closing Lemma for Diffeomorphism (Dynamical Systems) ★★★★

Author(s): Charles Pugh

\begin{conjecture} Let $f\in Diff^{r}(M)$ and $p\in\omega_{f} $. Then for any neighborhood $V_{f}\subset Diff^{r}(M) $ there is $g\in V_{f}$ such that $p$ is periodic point of $g$ \end{conjecture} There is an analogous conjecture for flows ( $C^{r}$ vector fields . In the case of diffeos this was proved by Charles Pugh for $r = 1$. In the case of Flows this has been solved by Sushei Hayahshy for $r = 1$ . But in the two cases the problem is wide open for $r > 1$

Keywords: Dynamics , Pertubation

Sub-atomic product of funcoids is a categorical product ★★


\begin{conjecture} In the category of continuous funcoids (defined similarly to the category of topological spaces) the following is a direct categorical product: \begin{itemize} \item Product morphism is defined similarly to the category of topological spaces. \item Product object is the sub-atomic product. \item Projections are sub-atomic projections. \end{itemize} \end{conjecture}

See details, exact definitions, and attempted proofs \href[here]{}.


Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

\begin{question} Are there graphs for which $\text{ch}^{\text{OL}}-\text{ch}$ is arbitrarily large? \end{question}

Keywords: choosability; list coloring; on-line choosability

Are almost all graphs determined by their spectrum? ★★★


\begin{problem} Are almost all graphs uniquely determined by the spectrum of their adjacency matrix? \end{problem}

Keywords: cospectral; graph invariant; spectrum

Signing a graph to have small magnitude eigenvalues ★★

Author(s): Bilu; Linial

\begin{conjecture} If $A$ is the adjacency matrix of a $d$-regular graph, then there is a symmetric signing of $A$ (i.e. replace some $+1$ entries by $-1$) so that the resulting matrix has all eigenvalues of magnitude at most $2 \sqrt{d-1}$. \end{conjecture}

Keywords: eigenvalue; expander; Ramanujan graph; signed graph; signing

The Bollobás-Eldridge-Catlin Conjecture on graph packing ★★★


\begin{conjecture}[BEC-conjecture] If $G_1$ and $G_2$ are $n$-vertex graphs and $(\Delta(G_1) + 1) (\Delta(G_2) + 1) < n + 1$, then $G_1$ and $G_2$ pack. \end{conjecture}

Keywords: graph packing