# Recent Activity

## Monochromatic reachability or rainbow triangles ★★★

Author(s): Sands; Sauer; Woodrow

In an edge-colored digraph, we say that a subgraph is *rainbow* if all its edges have distinct colors, and *monochromatic* if all its edges have the same color.

**Problem**Let be a tournament with edges colored from a set of three colors. Is it true that must have either a rainbow directed cycle of length three or a vertex so that every other vertex can be reached from by a monochromatic (directed) path?

Keywords: digraph; edge-coloring; tournament

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

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

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

Author(s): Behzad

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

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

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

Author(s): Iradmusa

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.