# Recent Activity

## Discrete Logarithm Problem ★★★

Author(s):

If is prime and , we write if satisfies . The problem of finding such an integer for a given (with ) is the Discrete Log Problem.

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

Keywords: discrete log; NP

## 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 , there is only a finite number of good-edge-labeling critical graphs with average degree less than .

Keywords: good edge labeling, edge labeling

## Special Primes ★

Author(s): George BALAN

Conjecture   Let be a prime natural number. Find all primes , such that .

Keywords:

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

Author(s): Payan

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

Keywords:

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

Author(s): Noel

Conjecture   If is a -chromatic graph on at most vertices, then .

## 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

## Euler-Mascheroni constant ★★★

Author(s):

Question   Is Euler-Mascheroni constant an transcendental number?

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

## Graham's conjecture on tree reconstruction ★★

Author(s): Graham

Problem   for every graph , we let denote the line graph of . Given that is a tree, can we determine it from the integer sequence ?

Keywords: reconstruction; tree

## Vertex Cover Integrality Gap ★★

Author(s): Atserias

Conjecture   For every there is such that, for every large , there are -vertex graphs and such that and .

Keywords: counting quantifiers; FMT12-LesHouches

## Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

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

Conjecture   For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.

## Mixing Circular Colourings ★

Author(s): Brewster; Noel

Question   Is always rational?

Keywords: discrete homotopy; graph colourings; mixing

## The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

Conjecture   Every graph with maximum degree has chromatic number at most .

Keywords:

## Chromatic number of random lifts of complete graphs ★★

Author(s): Amit

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

Keywords: random lifts, coloring

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

Author(s):

Conjecture   is a primitive root modulo for all primes , where is prime.

Keywords:

## Circular choosability of planar graphs ★

Author(s): Mohar

Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is

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

Keywords: choosability; circular colouring; planar graphs

## A conjecture about direct product of funcoids ★★

Author(s): Porton

Conjecture   Let and are monovalued, entirely defined funcoids with . Then there exists a pointfree funcoid such that (for every filter on ) (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

## 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

## Criterion for boundedness of power series ★

Author(s): Rüdinger

Question   Give a necessary and sufficient criterion for the sequence so that the power series is bounded for all .

Keywords: boundedness; power series; real analysis

## Length of surreal product ★

Author(s): Gonshor

Conjecture   Every surreal number has a unique sign expansion, i.e. function , where is some ordinal. This is the length of given sign expansion and also the birthday of the corresponding surreal number. Let us denote this length of as .

It is easy to prove that

What about

?

Keywords: surreal numbers

## Durer's Conjecture ★★★

Author(s): Durer; Shephard

Conjecture   Every convex polytope has a non-overlapping edge unfolding.

Keywords: folding; polytope