# Recent Activity

## Ramsey properties of Cayley graphs ★★★

Author(s): Alon

**Conjecture**There exists a fixed constant so that every abelian group has a subset with so that the Cayley graph has no clique or independent set of size .

Keywords: Cayley graph; Ramsey number

## Bases of many weights ★★★

Let be an (additive) abelian group, and for every let .

**Conjecture**Let be a matroid on , let be a map, put and . Then

## The Erdos-Turan conjecture on additive bases ★★★★

Let . The *representation function* for is given by the rule . We call an *additive basis* if is never .

**Conjecture**If is an additive basis, then is unbounded.

Keywords: additive basis; representation function

## Rota's unimodal conjecture ★★★

Author(s): Rota

Let be a matroid of rank , and for let be the number of closed sets of rank .

**Conjecture**is unimodal.

**Conjecture**is log-concave.

Keywords: flat; log-concave; matroid

## A conjecture on iterated circumcentres ★★

Author(s): Goddyn

**Conjecture**Let be a sequence of points in with the property that for every , the points are distinct, lie on a unique sphere, and further, is the center of this sphere. If this sequence is periodic, must its period be ?

Keywords: periodic; plane geometry; sequence

## Unions of triangle free graphs ★★★

**Problem**Does there exist a graph with no subgraph isomorphic to which cannot be expressed as a union of triangle free graphs?

Keywords: forbidden subgraph; infinite graph; triangle free

## The Two Color Conjecture ★★

Author(s): Neumann-Lara

**Conjecture**If is an orientation of a simple planar graph, then there is a partition of into so that the graph induced by is acyclic for .

## Half-integral flow polynomial values ★★

Author(s): Mohar

Let be the flow polynomial of a graph . So for every positive integer , the value equals the number of nowhere-zero -flows in .

**Conjecture**for every 2-edge-connected graph .

Keywords: nowhere-zero flow

## Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group , let () denote the smallest integer so that every sequence of elements of has a subsequence of length (length ) which has product equal to 1 in some order.

**Conjecture**for every finite group .

Keywords: subsequence sum; zero sum

## Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set is -*universal* if every vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in , and all edges are (non-intersecting) straight line segments.

**Question**Does there exist an -universal set of size ?

Keywords: geometric graph; planar graph; universal set

## Antichains in the cycle continuous order ★★

Author(s): DeVos

If , are graphs, a function is called *cycle-continuous* if the pre-image of every element of the (binary) cycle space of is a member of the cycle space of .

**Problem**Does there exist an infinite set of graphs so that there is no cycle continuous mapping between and whenever ?

## Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The *fatness* of a 4-polytope is defined to be where is the number of faces of of dimension .

**Question**Does there exist a fixed constant so that every convex 4-polytope has fatness at most ?

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

Author(s): Turan

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

**Conjecture**

Keywords: complete bipartite graph; crossing number

## Woodall's Conjecture ★★★

Author(s): Woodall

**Conjecture**If is a directed graph with smallest directed cut of size , then has disjoint dijoins.

## Pentagon problem ★★★

Author(s): Nesetril

**Question**Let be a 3-regular graph that contains no cycle of length shorter than . Is it true that for large enough~ there is a homomorphism ?

Keywords: cubic; homomorphism

## Ryser's conjecture ★★★

Author(s): Ryser

**Conjecture**Let be an -uniform -partite hypergraph. If is the maximum number of pairwise disjoint edges in , and is the size of the smallest set of vertices which meets every edge, then .

Keywords: hypergraph; matching; packing

## The Erdös-Hajnal Conjecture ★★★

**Conjecture**For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .

Keywords: induced subgraph

## Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

Keywords: cycle; hamiltonian; path; vertex-transitive

## 57-regular Moore graph? ★★★

Keywords: cage; Moore graph

## Few subsequence sums in Z_n x Z_n ★★

**Conjecture**For every , the sequence in consisting of copes of and copies of has the fewest number of distinct subsequence sums over all zero-free sequences from of length .

Keywords: subsequence sum; zero sum