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

Author(s): Schrijver; Seymour

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

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

Keywords: matroid; sumset; zero sum

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

Author(s): Erdos; Turan

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.

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

Author(s): Erdos; Hajnal

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

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

Keywords: acyclic; digraph; planar

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

Keywords: antichain; cycle; poset

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

Keywords: f-vector; polytope

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

Keywords: digraph; packing

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

Author(s): Erdos; Hajnal

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

Problem   Does every connected vertex-transitive graph have a Hamiltonian path?

Keywords: cycle; hamiltonian; path; vertex-transitive

## 57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

Question   Does there exist a 57-regular graph with diameter 2 and girth 5?

Keywords: cage; Moore graph