# Recent Activity

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

## The intersection of two perfect matchings ★★

**Conjecture**Every bridgeless cubic graph has two perfect matchings , so that does not contain an odd edge-cut.

Keywords: cubic; nowhere-zero flow; perfect matching

## Counterexamples to the Baillie-PSW primality test ★★

Author(s):

**Problem (1)**Find a counterexample to Baillie-PSW primality test or prove that there is no one.

**Problem (2)**Find a composite or which divides both (see Fermat pseudoprime) and the Fibonacci number (see Lucas pseudoprime), or prove that there is no such .

Keywords:

## A sextic counterexample to Euler's sum of powers conjecture ★★

Author(s): Euler

**Problem**Find six positive integers such that or prove that such integers do not exist.

Keywords:

## Geodesic cycles and Tutte's Theorem ★★

Author(s): Georgakopoulos; Sprüssel

**Problem**If is a -connected finite graph, is there an assignment of lengths to the edges of , such that every -geodesic cycle is peripheral?

Keywords: cycle space; geodesic cycles; peripheral cycles