Home

Recent Activity

Number Theory » Analytic N.T.

Lindelöf hypothesis ★★

Author(s): Lindelöf

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).$$

Keywords: Riemann Hypothesis; zeta

Posted by porton
updated September 20th, 2010
add new comment
Logic

Termination of the sixth Goodstein Sequence ★

Author(s): Graham

Question   How many steps does it take the sixth Goodstein sequence to terminate?

Keywords: Goodstein Sequence

Posted by mdevos
updated September 17th, 2010
5 comments
Graph Theory » Topological G.T. » Genus

Consecutive non-orientable embedding obstructions ★★★

Author(s):

Conjecture   Is there a graph $ G $ that is a minor-minimal obstruction for two non-orientable surfaces?

Keywords: minor; surface

Posted by Bruce Richter
updated September 15th, 2010
2 comments
Combinatorics » Ramsey Theory

Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let $ R(k,k) $ denote the $ k^{th} $ diagonal Ramsey number.

Conjecture   $ \lim_{k \rightarrow \infty} R(k,k) ^{\frac{1}{k}} $ exists.
Problem   Determine the limit in the above conjecture (assuming it exists).

Keywords: Ramsey number

Posted by mdevos
updated September 13th, 2010
2 comments
Topology

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

Author(s): David Eppstein

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.

Keywords: knot theory, links, chessboard complex

Posted by rybu
updated September 4th, 2010
add new comment
Algebra

Elementary symmetric of a sum of matrices ★★★

Author(s):

Problem  

Given a Matrix $ A $, the $ k $-th 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.

Keywords:

Posted by rscosa
updated August 27th, 2010
1 comment
Geometry

Monochromatic empty triangles ★★★

Author(s):

If $ X \subseteq {\mathbb R}^2 $ is a finite set of points which is 2-colored, an 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 monochromatic if all points in $ T $ are the same color.

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.

Keywords: empty triangle; general position; ramsey theory

Posted by mdevos
updated August 27th, 2010
4 comments
Combinatorics » 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 edge-antipodal if $ \phi(e) \neq \phi(e') $ whenever $ e,e' $ are antipodal edges.

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.

Keywords: antipodal; cube; edge-coloring

Posted by mdevos
updated August 20th, 2010
5 comments
Theoretical Comp. Sci. » Algorithms

Exponential Algorithms for Knapsack ★★

Author(s): Lipton

Conjecture  

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

Posted by dick lipton
updated August 6th, 2010
7 comments
Topology

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

Author(s): Gordon

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?

Keywords: 2-knot; Computational Complexity; knot theory

Posted by rybu
updated July 23rd, 2010
add new comment
Graph Theory » Coloring » Homomorphisms

Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

Question  

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 $?

Keywords: algorithm; Exponential-time algorithm; homomorphism

Posted by jfoniok
updated July 8th, 2010
add new comment
Graph Theory

Exact colorings of graphs ★★

Author(s): Erickson

Conjecture   For $ c \geq m \geq 1 $, let $ P(c,m) $ be the statement that given any exact $ c $-coloring of the edges of a complete countably infinite graph (that is, a coloring with $ c $ colors all of which must be used at least once), there exists an exactly $ m $-colored countably infinite complete subgraph. Then $ P(c,m) $ is true if and only if $ m=1 $, $ m=2 $, or $ c=m $.

Keywords: graph coloring; ramsey theory

Posted by Martin Erickson
updated June 29th, 2010
add new comment
Combinatorics

Dividing up the unrestricted partitions ★★

Author(s): David S.; Newman

Begin with the generating function for unrestricted partitions:

(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...

Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.

Keywords: congruence properties; partition

Posted by DavidSNewman
updated May 18th, 2010
2 comments
Graph Theory » Graph Algorithms

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

Problem   Does there exist a polynomial time algorithm which takes as input a graph $ G $ and for every vertex $ v \in V(G) $ a subset $ \ell(v) $ of $ \{1,2,3,4\} $, and decides if there exists a partition of $ V(G) $ into $ \{A_1,A_2,A_3,A_4\} $ so that $ v \in A_i $ only if $ i \in \ell(v) $ and so that $ A_1,A_2 $ are independent, $ A_4 $ is a clique, and there are no edges between $ A_1 $ and $ A_3 $?

Keywords: list partition; polynomial algorithm

Posted by mdevos
updated May 18th, 2010
1 comment
Combinatorics

Long rainbow arithmetic progressions ★★

Author(s): Fox; Jungic; Mahdian; Nesetril; Radoicic

For $ k\in \mathbb{N} $ let $ T_k $ denote the minimal number $ t\in \mathbb{N} $ such that there is a rainbow $ AP(k) $ in every equinumerous $ t $-coloring of $ \{ 1,2,\ldots ,tn\} $ for every $ n\in \mathbb{N} $

Conjecture   For all $ k\geq 3 $, $ T_k=\Theta (k^2) $.

Keywords: arithmetic progression; rainbow

Posted by vjungic
updated May 12th, 2010
1 comment
Graph Theory

Reconstruction conjecture ★★★★

Author(s): Kelly; Ulam

The deck of a graph $ G $ is the multiset consisting of all unlabelled subgraphs obtained from $ G $ by deleting a vertex in all possible ways (counted according to multiplicity).

Conjecture   If two graphs on $ \ge 3 $ vertices have the same deck, then they are isomorphic.

Keywords: reconstruction

Posted by zitterbewegung
updated May 4th, 2010
3 comments
Graph Theory

Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

Conjecture   It has been shown that a $ k $-outerplanar embedding for which $ k $ is minimal can be found in polynomial time. Does a similar result hold for $ k $-edge-outerplanar graphs?

Keywords: planar graph; polynomial algorithm

Posted by jcmeyer
updated April 18th, 2010
add new comment
Graph Theory

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

Posted by jcmeyer
updated April 18th, 2010
add new comment
Graph Theory

Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

Conjecture   Can the approximation ratio $ O(\sqrt{n}) $ be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than $ \mathcal{APX} $-hardness?

Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm

Posted by jcmeyer
updated April 18th, 2010
add new comment
Graph Theory

Beneš Conjecture (graph-theoretic form) ★★★

Author(s): Beneš

Problem  ($ \dag $)   Find a sufficient condition for a straight $ \ell $-stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture  ($ \diamond $)   Let $ L $ be a simple regular ordered $ 2 $-stage graph. Suppose that the graph $ L^m $ is externally connected, for some $ m\ge1 $. Then the graph $ L^{2m} $ is rearrangeable.

Keywords:

Posted by Vadim Lioubimov
updated April 17th, 2010
add new comment | 3 attachments