Recent Activity

Discrete Logarithm Problem ★★★

Author(s):

If $p$ is prime and $g,h \in {\mathbb Z}_p^*$ , we write $\log_g(h) = n$ if $n \in {\mathbb Z}$ satisfies $g^n = h$ . The problem of finding such an integer $n$ for a given $g,h \in {\mathbb Z}^*_p$ (with $g \neq 1$ ) is the Discrete Log Problem.

Conjecture There does not exist a polynomial time algorithm to solve the Discrete Log Problem.

Keywords: discrete log; NP

Posted by cplxphil
updated February 25th, 2013

3 comments

Graph Theory » Coloring » Labeling

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

Posted by DOT
updated February 16th, 2013

1 comment

Number Theory

Special Primes ★

Author(s): George BALAN

Conjecture Let $p$ be a prime natural number. Find all primes $q\equiv1\left(\mathrm{mod}\: p\right)$ , such that $2^{\frac{\left(q-1\right)}{p}}\equiv1\left(\mathrm{mod}\: q\right)$ .

Keywords:

Posted by maththebalans
updated February 7th, 2013

2 comments

Graph Theory » Coloring

Three-chromatic (0,2)-graphs ★★

Author(s): Payan

Question Are there any (0,2)-graphs with chromatic number exactly three?

Keywords:

Posted by Gordon Royle
updated February 6th, 2013

1 comment

Graph Theory » Coloring » Vertex coloring

Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

Conjecture If $G$ is a $k$ -chromatic graph on at most $mk$ vertices, then $\text{ch}(G)\leq \text{ch}(K_{m*k})$ .

Keywords: choosability; complete multipartite graph; list coloring

Posted by Jon Noel
updated February 2nd, 2013

add new comment

Number Theory » Analytic N.T.

The Riemann Hypothesis ★★★★

Author(s): Riemann

The zeroes of the Riemann zeta function that are inside the Critical Strip (i.e. the vertical strip of the complex plane where the real part of the complex variable is in ]0;1[), are actually located on the Critical line ( the vertical line of the complex plane with real part equal to 1/2)

Keywords: Millenium Problems; zeta

Posted by eric
updated January 27th, 2013

4 comments

Number Theory » Analytic N.T.

Euler-Mascheroni constant ★★★

Author(s):

Question Is Euler-Mascheroni constant an transcendental number?

Keywords: constant; Euler; irrational; Mascheroni; rational; transcendental

Posted by Juggernaut
updated January 21st, 2013

1 comment

Graph Theory » Basic G.T.

Graham's conjecture on tree reconstruction ★★

Author(s): Graham

Problem for every graph $G$ , we let $L(G)$ denote the line graph of $G$ . Given that $G$ is a tree, can we determine it from the integer sequence $|V(G)|, |V(L(G))|, |V(L(L(G)))|, \ldots$ ?

Keywords: reconstruction; tree

Posted by mdevos
updated January 16th, 2013

5 comments

Logic » Finite Model Theory

Vertex Cover Integrality Gap ★★

Author(s): Atserias

Conjecture For every $\varepsilon > 0$ there is $\delta > 0$ such that, for every large $n$ , there are $n$ -vertex graphs $G$ and $H$ such that $G \equiv_{\delta n}^{\mathrm{C}} H$ and $\mathrm{vc}(G) \ge (2 - \varepsilon) \cdot \mathrm{vc}(H)$ .

Keywords: counting quantifiers; FMT12-LesHouches

Posted by dberwanger
updated October 2nd, 2012

add new comment

Geometry

Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let $S$ be a set of points in the plane. Two points $v$ and $w$ in $S$ are visible with respect to $S$ if the line segment between $v$ and $w$ contains no other point in $S$ .

Conjecture For all integers $k,\ell\geq2$ there is an integer $n$ such that every set of at least $n$ points in the plane contains at least $\ell$ collinear points or $k$ pairwise visible points.

Keywords: Discrete Geometry; Geometric Ramsey Theory

Posted by David Wood
updated September 25th, 2012

1 comment

Graph Theory » Coloring » Vertex coloring

Mixing Circular Colourings ★

Author(s): Brewster; Noel

Question Is $\mathfrak{M}_c(G)$ always rational?

Keywords: discrete homotopy; graph colourings; mixing

Posted by Jon Noel
updated September 22nd, 2012

add new comment

Graph Theory

The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

Conjecture Every graph with maximum degree $\Delta \geq 9$ has chromatic number at most $\max\{\Delta-1, \omega\}$ .

Keywords:

Posted by Andrew King
updated September 10th, 2012

add new comment

Graph Theory » Probabilistic G.T.

Chromatic number of random lifts of complete graphs ★★

Author(s): Amit

Question Is the chromatic number of a random lift of $K_5$ concentrated on a single value?

Keywords: random lifts, coloring

Posted by DOT
updated September 3rd, 2012

add new comment

Number Theory

3 is a primitive root modulo primes of the form 16 q^4 + 1, where q>3 is prime ★★

Author(s):

Conjecture $3~$ is a primitive root modulo $~p$ for all primes $~p=16\cdot q^4+1$ , where $~q>3$ is prime.

Keywords:

Posted by princeps
updated August 24th, 2012

1 comment

Graph Theory » Coloring » Homomorphisms

Circular choosability of planar graphs ★

Author(s): Mohar

Let $G = (V, E)$ be a graph. If $p$ and $q$ are two integers, a $(p,q)$ -colouring of $G$ is a function $c$ from $V$ to $\{0,\dots,p-1\}$ such that $q \le |c(u)-c(v)| \le p-q$ for each edge $uv\in E$ . Given a list assignment $L$ of $G$ , i.e.~a mapping that assigns to every vertex $v$ a set of non-negative integers, an $L$ -colouring of $G$ is a mapping $c : V \to N$ such that $c(v)\in L(v)$ for every $v\in V$ . A list assignment $L$ is a $t$ - $(p,q)$ -list-assignment if $L(v) \subseteq \{0,\dots,p-1\}$ and $|L(v)| \ge tq$ for each vertex $v \in V$ . Given such a list assignment $L$ , the graph G is $(p,q)$ - $L$ -colourable if there exists a $(p,q)$ - $L$ -colouring $c$ , i.e. $c$ is both a $(p,q)$ -colouring and an $L$ -colouring. For any real number $t \ge 1$ , the graph $G$ is $t$ - $(p,q)$ -choosable if it is $(p,q)$ - $L$ -colourable for every $t$ - $(p,q)$ -list-assignment $L$ . Last, $G$ is circularly $t$ -choosable if it is $t$ - $(p,q)$ -choosable for any $p$ , $q$ . The circular choosability (or circular list chromatic number or circular choice number) of G is $cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$

Problem What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs

Posted by rosskang
updated August 23rd, 2012

add new comment

Topology

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

Posted by porton
updated July 26th, 2012

add new comment

Number Theory

MacEachen Conjecture ★

Author(s): McEachen

Conjecture Every odd prime number must either be adjacent to, or a prime distance away from a primorial or primorial product.

Keywords: primality; prime distribution

Posted by billymac00
updated July 7th, 2012

4 comments | 1 attachment

Analysis

Criterion for boundedness of power series ★

Author(s): Rüdinger

Question Give a necessary and sufficient criterion for the sequence $(a_n)$ so that the power series $\sum_{n=0}^{\infty} a_n x^n$ is bounded for all $x \in \mathbb{R}$ .

Keywords: boundedness; power series; real analysis

Posted by andreasruedinger
updated June 21st, 2012

5 comments

Combinatorics

Length of surreal product ★

Author(s): Gonshor

Conjecture Every surreal number has a unique sign expansion, i.e. function $f: o\rightarrow \{-, +\}$ , where $o$ is some ordinal. This $o$ is the length of given sign expansion and also the birthday of the corresponding surreal number. Let us denote this length of $s$ as $\ell(s)$ .

It is easy to prove that

$\ell(s+t) \leq \ell(s)+\ell(t)$