Random

Perfect cuboid ★★

Author(s):

Conjecture   Does a perfect cuboid exist?

Keywords:

Counterexamples to the Baillie-PSW primality test ★★

Author(s):

Problem  (1)   Find a counterexample to Baillie-PSW primality test or prove that there is no one.
Problem  (2)   Find a composite $ n\equiv 3 $ or $ 7\pmod{10} $ which divides both $ 2^{n-1} - 1 $ (see Fermat pseudoprime) and the Fibonacci number $ F_{n+1} $ (see Lucas pseudoprime), or prove that there is no such $ n $.

Keywords:

Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group $ G $, let $ s(G) $ ($ s'(G) $) denote the smallest integer $ m $ so that every sequence of $ m $ elements of $ G $ has a subsequence of length $ >0 $ (length $ |G| $) which has product equal to 1 in some order.

Conjecture   $ s'(G) = s(G) + |G| - 1 $ for every finite group $ G $.

Keywords: subsequence sum; zero sum

Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family $ {\mathcal F} $ of graphs is $ \chi $-bounded if there exists a function $ f: {\mathbb N} \rightarrow {\mathbb N} $ so that every $ G \in {\mathcal F} $ satisfies $ \chi(G) \le f (\omega(G)) $.

Conjecture   For every fixed tree $ T $, the family of graphs with no induced subgraph isomorphic to $ T $ is $ \chi $-bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

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

Author(s): Charles Pugh

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 $

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

The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

Conjecture   $ \displaystyle   cr(K_{m,n}) = \floor{\frac m2} \floor{\frac {m-1}2}                      \floor{\frac n2} \floor{\frac {n-1}2}  $

Keywords: complete bipartite graph; crossing number

Roller Coaster permutations ★★★

Author(s): Ahmed; Snevily

Let $ S_n $ denote the set of all permutations of $ [n]=\set{1,2,\ldots,n} $. Let $ i(\pi) $ and $ d(\pi) $ denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in $ \pi $. Let $ X(\pi) $ denote the set of subsequences of $ \pi $ with length at least three. Let $ t(\pi) $ denote $ \sum_{\tau\in X(\pi)}(i(\tau)+d(\tau)) $.

A permutation $ \pi\in S_n $ is called a Roller Coaster permutation if $ t(\pi)=\max_{\tau\in S_n}t(\tau) $. Let $ RC(n) $ be the set of all Roller Coaster permutations in $ S_n $.

Conjecture   For $ n\geq 3 $,
    \item If $ n=2k $, then $ |RC(n)|=4 $. \item If $ n=2k+1 $, then $ |RC(n)|=2^j $ with $ j\leq k+1 $.
Conjecture  (Odd Sum conjecture)   Given $ \pi\in RC(n) $,
    \item If $ n=2k+1 $, then $ \pi_j+\pi_{n-j+1} $ is odd for $ 1\leq j\leq k $. \item If $ n=2k $, then $ \pi_j + \pi_{n-j+1} = 2k+1 $ for all $ 1\leq j\leq k $.

Keywords:

A conjecture about direct product of funcoids ★★

Author(s): Porton

Conjecture   Let $ f_1 $ and $ f_2 $ are monovalued, entirely defined funcoids with $ \operatorname{Src}f_1=\operatorname{Src}f_2=A $. Then there exists a pointfree funcoid $ f_1 \times^{\left( D \right)} f_2 $ such that (for every filter $ x $ on $ A $) $$\left\langle f_1 \times^{\left( D \right)} f_2 \right\rangle x = \bigcup \left\{ \langle f_1\rangle X \times^{\mathsf{FCD}} \langle f_2\rangle X \hspace{1em} | \hspace{1em} X \in \mathrm{atoms}^{\mathfrak{A}} x \right\}.$$ (The join operation is taken on the lattice of filters with reversed order.)

A positive solution of this problem may open a way to prove that some funcoids-related categories are cartesian closed.

Keywords: category theory; general topology

Asymptotic Distribution of Form of Polyhedra ★★

Author(s): Rüdinger

Problem   Consider the set of all topologically inequivalent polyhedra with $ k $ edges. Define a form parameter for a polyhedron as $ \beta:= v/(k+2) $ where $ v $ is the number of vertices. What is the distribution of $ \beta $ for $ k \to \infty $?

Keywords: polyhedral graphs, distribution

Covering powers of cycles with equivalence subgraphs

Author(s):

Conjecture   Given $ k $ and $ n $, the graph $ C_{n}^k $ has equivalence covering number $ \Omega(k) $.

Keywords:

Obstacle number of planar graphs

Author(s): Alpert; Koch; Laison

Does there exist a planar graph with obstacle number greater than 1? Is there some $ k $ such that every planar graph has obstacle number at most $ k $?

Keywords: graph drawing; obstacle number; planar graph; visibility graph

Rota's basis conjecture ★★★

Author(s): Rota

Conjecture   Let $ V $ be a vector space of dimension $ n $ and let $ B_1,\ldots,B_n \subseteq V $ be bases. Then there exist $ n $ disjoint transversals of $ B_1,\ldots,B_n $ each of which is a base.

Keywords: base; latin square; linear algebra; matroid; transversal

Reed's omega, delta, and chi conjecture ★★★

Author(s): Reed

For a graph $ G $, we define $ \Delta(G) $ to be the maximum degree, $ \omega(G) $ to be the size of the largest clique subgraph, and $ \chi(G) $ to be the chromatic number of $ G $.

Conjecture   $ \chi(G) \le \ceil{\frac{1}{2}(\Delta(G)+1) + \frac{1}{2}\omega(G)} $ for every graph $ G $.

Keywords: coloring

Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph $ G $ is $ k $-degenerate if every subgraph of $ G $ has a vertex of degree $ \le k $.

Conjecture   Every simple planar graph has a 5-coloring so that for $ 1 \le k \le 4 $, the union of any $ k $ color classes induces a $ (k-1) $-degenerate graph.

Keywords: coloring; degenerate; planar

Infinite distributivity of meet over join for a principal funcoid ★★

Author(s): Porton

Conjecture   $ f \sqcap \bigsqcup S = \bigsqcup \langle f \sqcap \rangle^{\ast} S $ for principal funcoid $ f $ and a set $ S $ of funcoids of appropriate sources and destinations.

Keywords: distributivity; principal funcoid

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.

Question   Is it true that for every (sub)cubic graph $ G $, we have $ \chi_s'(G) \le 6 $?

Keywords: edge coloring; star coloring

A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture   Let $ a > b > 0 $ be integers. Set $ b_1 = b $ and $ b_{i+1} = {a \bmod {b_i}} $ for $ i \geq 0 $. Eventually we have $ b_{n+1} = 0 $; put $ P(a,b) = n $.

Example: $ P(35, 22) = 7 $, since $ b_1 = 22 $, $ b_2 = 13 $, $ b_3 = 9 $, $ b_4 = 8 $, $ b_5 = 3 $, $ b_6 = 2 $, $ b_7 = 1 $, $ b_8 = 0 $.

Prove or disprove: $ P(a,b) = O((\log a)^2) $.

Keywords: Pierce expansions

Erdős–Straus conjecture ★★

Author(s): Erdos; Straus

Conjecture  

For all $ n > 2 $, there exist positive integers $ x $, $ y $, $ z $ such that $$1/x + 1/y + 1/z = 4/n$$.

Keywords: Egyptian fraction

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

Conjecture   Let $ H $ be a simple $ d $-uniform hypergraph, and assume that every set of $ d-1 $ points is contained in at most $ r $ edges. Then there exists an $ r+d-1 $-edge-coloring so that any two edges which share $ d-1 $ vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing

The Bermond-Thomassen Conjecture ★★

Author(s): Bermond; Thomassen

Conjecture   For every positive integer $ k $, every digraph with minimum out-degree at least $ 2k-1 $ contains $ k $ disjoint cycles.

Keywords: cycles

Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

Melnikov's valency-variety problem

Author(s): Melnikov

Problem   The valency-variety $ w(G) $ of a graph $ G $ is the number of different degrees in $ G $. Is the chromatic number of any graph $ G $ with at least two vertices greater than $$\ceil{ \frac{\floor{w(G)/2}}{|V(G)| - w(G)} } ~ ?$$

Keywords:

Distribution and upper bound of mimic numbers ★★

Author(s): Bhattacharyya

Problem  

Let the notation $ a|b $ denote ''$ a $ divides $ b $''. The mimic function in number theory is defined as follows [1].

Definition   For any positive integer $ \mathcal{N} = \sum_{i=0}^{n}\mathcal{X}_{i}\mathcal{M}^{i} $ divisible by $ \mathcal{D} $, the mimic function, $ f(\mathcal{D} | \mathcal{N}) $, is given by,

$$ f(\mathcal{D} | \mathcal{N}) = \sum_{i=0}^{n}\mathcal{X}_{i}(\mathcal{M}-\mathcal{D})^{i} $$

By using this definition of mimic function, the mimic number of any non-prime integer is defined as follows [1].

Definition   The number $ m $ is defined to be the mimic number of any positive integer $ \mathcal{N} = \sum_{i=0}^{n}\mathcal{X}_{i}\mathcal{M}^{i} $, with respect to $ \mathcal{D} $, for the minimum value of which $ f^{m}(\mathcal{D} | \mathcal{N}) = \mathcal{D} $.

Given these two definitions and a positive integer $ \mathcal{D} $, find the distribution of mimic numbers of those numbers divisible by $ \mathcal{D} $.

Again, find whether there is an upper bound of mimic numbers for a set of numbers divisible by any fixed positive integer $ \mathcal{D} $.

Keywords: Divisibility; mimic function; mimic number

Goldbach conjecture ★★★★

Author(s): Goldbach

Conjecture   Every even integer greater than 2 is the sum of two primes.

Keywords: additive basis; prime

Approximation ratio for k-outerplanar graphs ★★

Author(s): Bentz

Conjecture   Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a constant in $ k $-outerplanar graphs or tree-width graphs?

Keywords: approximation algorithms; planar graph; polynomial algorithm

The 3n+1 conjecture ★★★

Author(s): Collatz

Conjecture   Let $ f(n) = 3n+1 $ if $ n $ is odd and $ \frac{n}{2} $ if $ n $ is even. Let $ f(1) = 1 $. Assume we start with some number $ n $ and repeatedly take the $ f $ of the current number. Prove that no matter what the initial number is we eventually reach $ 1 $.

Keywords: integer sequence

Are there an infinite number of lucky primes?

Author(s): Lazarus: Gardiner: Metropolis; Ulam

Conjecture   If every second positive integer except 2 is remaining, then every third remaining integer except 3, then every fourth remaining integer etc. , an infinite number of the remaining integers are prime.

Keywords: lucky; prime; seive

The Two Color Conjecture ★★

Author(s): Neumann-Lara

Conjecture   If $ G $ is an orientation of a simple planar graph, then there is a partition of $ V(G) $ into $ \{X_1,X_2\} $ so that the graph induced by $ X_i $ is acyclic for $ i=1,2 $.

Keywords: acyclic; digraph; planar

Oriented chromatic number of planar graphs ★★

Author(s):

An oriented colouring of an oriented graph is assignment $ c $ of colours to the vertices such that no two arcs receive ordered pairs of colours $ (c_1,c_2) $ and $ (c_2,c_1) $. It is equivalent to a homomorphism of the digraph onto some tournament of order $ k $.

Problem   What is the maximal possible oriented chromatic number of an oriented planar graph?

Keywords: oriented coloring; oriented graph; planar graph

Which outer reloids are equal to inner ones ★★

Author(s): Porton

Warning: This formulation is vague (not exact).

Question   Characterize the set $ \{f\in\mathsf{FCD} \mid (\mathsf{RLD})_{\mathrm{in}} f=(\mathsf{RLD})_{\mathrm{out}} f\} $. In other words, simplify this formula.

The problem seems rather difficult.

Keywords:

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

Conjecture   There is a constant $ c $ such that the list chromatic number of any bipartite graph $ G $ of maximum degree $ \Delta $ is at most $ c \log \Delta $.

Keywords:

The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

Conjecture   Every bridgeless cubic graph has two perfect matchings $ M_1 $, $ M_2 $ so that $ M_1 \cap M_2 $ does not contain an odd edge-cut.

Keywords: cubic; nowhere-zero flow; perfect matching

Good Edge Labelings ★★

Author(s): Araújo; Cohen; Giroire; Havet

Question   What is the maximum edge density of a graph which has a good edge labeling?

We say that a graph is good-edge-labeling critical, if it has no good edge labeling, but every proper subgraph has a good edge labeling.

Conjecture   For every $ c<4 $, there is only a finite number of good-edge-labeling critical graphs with average degree less than $ c $.

Keywords: good edge labeling, edge labeling

trace inequality ★★

Author(s):

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?

Keywords:

Inequality for square summable complex series ★★

Author(s): Retkes

Conjecture   For all $ \alpha=(\alpha_1,\alpha_2,\ldots)\in l_2(\cal{C}) $ the following inequality holds $$\sum_{n\geq 1}|\alpha_n|^2\geq \frac{6}{\pi^2}\sum_{k\geq0}\bigg| \sum_{l\geq0}\frac{1}{l+1}\alpha_{2^k(2l+1)}\bigg|^2 $$

Keywords: Inequality

Random stable roommates ★★

Author(s): Mertens

Conjecture   The probability that a random instance of the stable roommates problem on $ n \in 2{\mathbb N} $ people admits a solution is $ \Theta( n ^{-1/4} ) $.

Keywords: stable marriage; stable roommates

Decomposing a connected graph into paths. ★★★

Author(s): Gallai

Conjecture   Every simple connected graph on $ n $ vertices can be decomposed into at most $ \frac{1}{2}(n+1) $ paths.

Keywords:

Which lattices occur as intervals in subgroup lattices of finite groups? ★★★★

Author(s):

Conjecture  

There exists a finite lattice that is not an interval in the subgroup lattice of a finite group.

Keywords: congruence lattice; finite groups

Circular coloring triangle-free subcubic planar graphs ★★

Author(s): Ghebleh; Zhu

Problem   Does every triangle-free planar graph of maximum degree three have circular chromatic number at most $ \frac{20}{7} $?

Keywords: circular coloring; planar graph; triangle free

Graceful Tree Conjecture ★★★

Author(s):

Conjecture   All trees are graceful

Keywords: combinatorics; graceful labeling

Combinatorial covering designs

Author(s): Gordon; Mills; Rödl; Schönheim

A $ (v, k, t) $ covering design, or covering, is a family of $ k $-subsets, called blocks, chosen from a $ v $-set, such that each $ t $-subset is contained in at least one of the blocks. The number of blocks is the covering’s size, and the minimum size of such a covering is denoted by $ C(v, k, t) $.

Problem   Find a closed form, recurrence, or better bounds for $ C(v,k,t) $. Find a procedure for constructing minimal coverings.

Keywords: recreational mathematics

Forcing a $K_6$-minor ★★

Author(s): Barát ; Joret; Wood

Conjecture   Every graph with minimum degree at least 7 contains a $ K_6 $-minor.
Conjecture   Every 7-connected graph contains a $ K_6 $-minor.

Keywords: connectivity; graph minors

Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set $ S \subseteq {\mathbb Z} $ has distinct subset sums if distinct subsets of $ S $ have distinct sums.

Conjecture   There exists a fixed constant $ c $ so that $ |S| \le \log_2(n) + c $ whenever $ S \subseteq \{1,2,\ldots,n\} $ has distinct subset sums.

Keywords: subset sum

Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

Problem   Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree $ r > 2 $?

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

Are all Mersenne Numbers with prime exponent square-free? ★★★

Author(s):

Conjecture   Are all Mersenne Numbers with prime exponent $ {2^p-1} $ Square free?

Keywords: Mersenne number

Decomposition of completions of reloids ★★

Author(s): Porton

Conjecture   For composable reloids $ f $ and $ g $ it holds
    \item $ \operatorname{Compl} ( g \circ f) = ( \operatorname{Compl} g) \circ f $ if $ f $ is a co-complete reloid; \item $ \operatorname{CoCompl} ( f \circ g) = f \circ \operatorname{CoCompl} g $ if $ f $ is a complete reloid; \item $ \operatorname{CoCompl} ( ( \operatorname{Compl} g) \circ f) = \operatorname{Compl} ( g \circ   ( \operatorname{CoCompl} f)) = ( \operatorname{Compl} g) \circ ( \operatorname{CoCompl} f) $; \item $ \operatorname{Compl} ( g \circ ( \operatorname{Compl} f)) = \operatorname{Compl} ( g \circ   f) $; \item $ \operatorname{CoCompl} ( ( \operatorname{CoCompl} g) \circ f) = \operatorname{CoCompl} ( g   \circ f) $.

Keywords: co-completion; completion; reloid

Birch & Swinnerton-Dyer conjecture ★★★★

Author(s):

Conjecture   Let $ E/K $ be an elliptic curve over a number field $ K $. Then the order of the zeros of its $ L $-function, $ L(E, s) $, at $ s = 1 $ is the Mordell-Weil rank of $ E(K) $.

Keywords:

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture   Every set of $ 2^{n-2} + 1 $ points in the plane in general position contains a subset of $ n $ points which form a convex $ n $-gon.

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

Strong 5-cycle double cover conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Let $ C $ be a circuit in a bridgeless cubic graph $ G $. Then there is a five cycle double cover of $ G $ such that $ C $ is a subgraph of one of these five cycles.

Keywords: cycle cover

Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

Conjecture   Every prism over a $ 3 $-connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords: