# Recent Activity

## P vs. PSPACE ★★★

Author(s): Folklore

**Problem**Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?

Keywords: P; PSPACE; separation; unconditional

## Sums of independent random variables with unbounded variance ★★

Author(s): Feige

**Conjecture**If are independent random variables with , then

Keywords: Inequality; Probability Theory; randomness in TCS

## Grunbaum's Conjecture ★★★

Author(s): Grunbaum

**Conjecture**If is a simple loopless triangulation of an orientable surface, then the dual of is 3-edge-colorable.

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

## 3-Colourability of Arrangements of Great Circles ★★

Author(s): Felsner; Hurtado; Noy; Streinu

Consider a set of great circles on a sphere with no three circles meeting at a point. The arrangement graph of has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.

**Conjecture**Every arrangement graph of a set of great circles is -colourable.

Keywords: arrangement graph; graph coloring

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

## Middle levels problem ★★

Author(s): Erdos

**Conjecture**Let be the bipartite graph whose vertices are the -subsets and the -subsets of a -element set, and with inclusion as the adjacency relationship. Then is Hamiltonian.

Keywords:

## Kneser–Poulsen conjecture ★★★

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

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

Keywords:

## 3-accessibility of Fibonacci numbers ★★

**Question**Is the set of Fibonacci numbers 3-accessible?

Keywords: Fibonacci numbers; monochromatic diffsequences

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

## Compatible Matching Conjecture ★★

Author(s): Wood

For an even set of points in the plane, a *perfect matching of * is a collection of nonintersecting segments such that every point of is an end of exactly one of the segments.

**Conjecture**Let be a set of points in the plane in general position such that is divisible by 4. Then for every perfect matching of there is another perfect matching, , of such that no segment of crosses a segment of .

Keywords: geometric graphs; matchings