# Recent Activity

## Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

Conjecture   For every rational and every rational , there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula on variables, for some , and clauses drawn uniformly at random from the set of formulas on variables. Return with probability at least 0.5 (over the instances) that is typical without returning typical for any instance with at least simultaneously satisfiable clauses.

Keywords: NP; randomness in TCS; satisfiability

## Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

Problem   Do there exist non-isomorphic trees which have the same chromatic symmetric function?

Keywords: chromatic polynomial; symmetric function; tree

## Shannon capacity of the seven-cycle ★★★

Author(s):

Problem   What is the Shannon capacity of ?

Keywords:

## Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let be a finite undirected simple graph.

A -page book embedding of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The book thickness of , denoted by bt is the minimum integer for which there is a -page book embedding of .

Let be the graph obtained by subdividing each edge of exactly once.

Conjecture   There is a function such that for every graph , Keywords: book embedding; book thickness

## Frobenius number of four or more integers ★★

Author(s):

Problem   Find an explicit formula for Frobenius number of co-prime positive integers for .

Keywords:

## Magic square of squares ★★

Author(s): LaBar

Question   Does there exist a magic square composed of distinct perfect squares?

Keywords:

## Diophantine quintuple conjecture ★★

Author(s):

Definition   A set of m positive integers is called a Diophantine -tuple if is a perfect square for all .
Conjecture  (1)   Diophantine quintuple does not exist.

It would follow from the following stronger conjecture [Da]:

Conjecture  (2)   If is a Diophantine quadruple and , then Keywords:

## Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture   Every finite group is the Galois group of some finite algebraic extension of .

Keywords:

## Seymour's r-graph conjecture ★★★

Author(s): Seymour

An -graph is an -regular graph with the property that for every with odd size.

Conjecture for every -graph .

Keywords: edge-coloring; r-graph

## Edge list coloring conjecture ★★★

Author(s):

Conjecture   Let be a loopless multigraph. Then the edge chromatic number of equals the list edge chromatic number of .

Keywords:

## Kneser–Poulsen conjecture ★★★

Author(s): Kneser; Poulsen

Conjecture   If a finite set of unit balls in is rearranged so that the distance between each pair of centers does not decrease, then the volume of the union of the balls does not decrease.

Keywords: pushing disks

## Wide partition conjecture ★★

Author(s): Chow; Taylor

Conjecture   An integer partition is wide if and only if it is Latin.

Keywords:

## 3-accessibility of Fibonacci numbers ★★

Author(s): Landman; Robertson

Question   Is the set of Fibonacci numbers 3-accessible?

## Simplexity of the n-cube ★★★

Author(s):

Question   What is the minimum cardinality of a decomposition of the -cube into -simplices?

Keywords: cube; decomposition; simplex

## Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture   Let be a sequence of nonnegative integers which strictly decreases until .

Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus with crossings, but not with less crossings.

Keywords: crossing number; crossing sequence

## The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number of is the minimum number of crossings in all drawings of in the plane.

Conjecture Keywords: complete graph; crossing number

## The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number of is the minimum number of crossings in all drawings of in the plane.

The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.

Conjecture Keywords: crossing number; hypercube

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