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

Keywords: choosability; complete multipartite graph; list coloring

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

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.

Keywords: Discrete Geometry; Geometric Ramsey Theory

## Mixing Circular Colourings ★

**Question**Is always rational?

Keywords: discrete homotopy; graph colourings; mixing

## The Borodin-Kostochka Conjecture ★★

**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 ★★★

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