# Recent Activity

## Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An *alternating* walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is *universal* if for every pair of edges , there is an alternating walk containing both and

**Question**Does there exist a locally finite highly arc transitive digraph which is universal?

Keywords: arc transitive; digraph

## P vs. NP ★★★★

**Problem**Is P = NP?

Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm

## F_d versus F_{d+1} ★★★

Author(s): Krajicek

**Problem**Find a constant such that for any there is a sequence of tautologies of depth that have polynomial (or quasi-polynomial) size proofs in depth Frege system but requires exponential size proofs.

Keywords: Frege system; short proof

## Even vs. odd latin squares ★★★

A latin square is *even* if the product of the signs of all of the row and column permutations is 1 and is *odd* otherwise.

**Conjecture**For every positive even integer , the number of even latin squares of order and the number of odd latin squares of order are different.

Keywords: latin square

## Universal Steiner triple systems ★★

Author(s): Grannell; Griggs; Knor; Skoviera

**Problem**Which Steiner triple systems are universal?

Keywords: cubic graph; Steiner triple system

## Monotone 4-term Arithmetic Progressions ★★

Author(s): Davis; Entringer; Graham; Simmons

**Question**Is it true that every permutation of positive integers must contain monotone 4-term arithmetic progressions?

Keywords: monotone arithmetic progression; permutation

## The Bermond-Thomassen Conjecture ★★

**Conjecture**For every positive integer , every digraph with minimum out-degree at least contains disjoint cycles.

Keywords: cycles

## Continous analogue of Hirsch conjecture ★★

Author(s): Deza; Terlaky; Zinchenko

**Conjecture**The order of the largest total curvature of the primal central path over all polytopes defined by inequalities in dimension is .

## Average diameter of a bounded cell of a simple arrangement ★★

Author(s): Deza; Terlaky; Zinchenko

**Conjecture**The average diameter of a bounded cell of a simple arrangement defined by hyperplanes in dimension is not greater than .

Keywords: arrangement; diameter; polytope

## Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

**Conjecture**Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?

Keywords: crossing number; surface

## Matchings extend to Hamiltonian cycles in hypercubes ★★

Keywords: Hamiltonian cycle; hypercube; matching

## Linear Hypergraphs with Dimension 3 ★★

Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl

**Conjecture**Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.

Keywords: Hypergraphs

## Reed's omega, delta, and chi conjecture ★★★

Author(s): Reed

For a graph , we define to be the maximum degree, to be the size of the largest clique subgraph, and to be the chromatic number of .

**Conjecture**for every graph .

Keywords: coloring

## Pebbling a cartesian product ★★★

Author(s): Graham

We let denote the pebbling number of a graph .

**Conjecture**.

## Rendezvous on a line ★★★

Author(s): Alpern

**Problem**Two players start at a distance of 2 on an (undirected) line (so, neither player knows the direction of the other) and both move at a maximum speed of 1. What is the infimum expected meeting time (first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy?

Keywords: game theory; optimization; rendezvous

## Linial-Berge path partition duality ★★★

**Conjecture**The minimum -norm of a path partition on a directed graph is no more than the maximal size of an induced -colorable subgraph.

Keywords: coloring; directed path; partition

## What is the smallest number of disjoint spanning trees made a graph Hamiltonian ★★

Author(s): Goldengorin

We are given a complete simple undirected weighted graph and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.

**Question 1**. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.

**Question 2**. What is the smallest number of disjoint spanning trees creates a graph containing a shortest Hamiltonian path?

**Questions 3 and 4**. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?

Keywords: 1-trees; cycle; Hamitonian path; spanning trees

## Davenport's constant ★★★

Author(s):

For a finite (additive) abelian group , the *Davenport constant* of , denoted , is the smallest integer so that every sequence of elements of with length has a nontrivial subsequence which sums to zero.

**Conjecture**

Keywords: Davenport constant; subsequence sum; zero sum

## Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

**Conjecture**For every positive integer , every (loopless) graph with immerses .

Keywords: coloring; complete graph; immersion

## Rainbow AP(4) in an almost equinumerous coloring ★★

Author(s): Conlon

**Problem**Do 4-colorings of , for a large prime, always contain a rainbow if each of the color classes is of size of either or ?

Keywords: arithmetic progression; rainbow