# Recent Activity

## Rank vs. Genus ★★★

Author(s): Johnson

Question   Is there a hyperbolic 3-manifold whose fundamental group rank is strictly less than its Heegaard genus? How much can the two differ by?

Keywords:

## The Hodge Conjecture ★★★★

Author(s): Hodge

Conjecture   Let be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of .

Keywords: Hodge Theory; Millenium Problems

## 2-accessibility of primes ★★

Author(s): Landman; Robertson

Question   Is the set of prime numbers 2-accessible?

Keywords: monochromatic diffsequences; primes

## Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph , we let be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and be the size of the smallest feedback edge set.

Conjecture  If is a simple digraph without directed cycles of length , then .

Keywords: acyclic; digraph; feedback edge set; triangle free

## Tarski's exponential function problem ★★

Author(s): Tarski

Conjecture   Is the theory of the real numbers with the exponential function decidable?

Keywords: Decidability

## Jacobian Conjecture ★★★

Author(s): Keller

Conjecture   Let be a field of characteristic zero. A collection of polynomials in variables defines an automorphism of if and only if the Jacobian matrix is a nonzero constant.

Keywords: Affine Geometry; Automorphisms; Polynomials

## Counting 3-colorings of the hex lattice ★★

Author(s): Thomassen

Problem   Find .

Keywords: coloring; Lieb's Ice Constant; tiling; torus

## Dense rational distance sets in the plane ★★★

Author(s): Ulam

Problem   Does there exist a dense set so that all pairwise distances between points in are rational?

Keywords: integral distance; rational distance

## Negative association in uniform forests ★★

Author(s): Pemantle

Conjecture   Let be a finite graph, let , and let be the edge set of a forest chosen uniformly at random from all forests of . Then

Keywords: forest; negative association

## Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem   Let be a perfect graph on vertices. Is it true that either or contains a complete bipartite subgraph with bipartition so that ?

Keywords: perfect graph

## Wall-Sun-Sun primes and Fibonacci divisibility ★★

Author(s):

Conjecture   For any prime , there exists a Fibonacci number divisible by exactly once.

Equivalently:

Conjecture   For any prime , does not divide where is the Legendre symbol.

Keywords: Fibonacci; prime

## A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture   Let be integers. Set and for . Eventually we have ; put .

Example: , since , , , , , , , .

Prove or disprove: .

Keywords: Pierce expansions

## Total Colouring Conjecture ★★★

Conjecture   A total coloring of a graph is an assignment of colors to the vertices and the edges of such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph , , equals the minimum number of colors needed in a total coloring of . It is an old conjecture of Behzad that for every graph , the total chromatic number equals the maximum degree of a vertex in , plus one or two. In other words,

Keywords: Total coloring

## Edge Reconstruction Conjecture ★★★

Author(s): Harary

Conjecture

Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs

Keywords: reconstruction

## Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

Conjecture   For every and every positive integer , there exists so that every simple -regular graph with has a -regular subgraph with .

Keywords: regular; subgraph

## Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph is -degenerate if every subgraph of has a vertex of degree .

Conjecture   Every simple planar graph has a 5-coloring so that for , the union of any color classes induces a -degenerate graph.

Keywords: coloring; degenerate; planar

## Partial List Coloring ★★★

Let be a simple graph, and for every list assignment let be the maximum number of vertices of which are colorable with respect to . Define , where the minimum is taken over all list assignments with for all .

Conjecture   [2] Let be a graph with list chromatic number and . Then

Keywords: list assignment; list coloring

## Cube-Simplex conjecture ★★★

Author(s): Kalai

Conjecture   For every positive integer , there exists an integer so that every polytope of dimension has a -dimensional face which is either a simplex or is combinatorially isomorphic to a -dimensional cube.

Keywords: cube; facet; polytope; simplex

## S(S(f)) = S(f) for reloids ★★

Author(s): Porton

Question   for every endo-reloid ?

Keywords: reloid

## Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

Conjecture   Let be a simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.

Keywords: list assignment; list coloring