# Recent Activity

## Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

**Conjecture**A triangle-free graph with maximum degree has chromatic number at most .

Keywords: chromatic number; girth; maximum degree; triangle free

## Erdös-Szekeres conjecture ★★★

**Conjecture**Every set of points in the plane in general position contains a subset of points which form a convex -gon.

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

## Inequality of the means ★★★

Author(s):

**Question**Is is possible to pack rectangular -dimensional boxes each of which has side lengths inside an -dimensional cube with side length ?

Keywords: arithmetic mean; geometric mean; Inequality; packing

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

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