# Recent Activity

## Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

**Conjecture**Let be a simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.

Keywords: list assignment; list coloring

## Combinatorial covering designs ★

Author(s): Gordon; Mills; Rödl; Schönheim

A *covering design*, or *covering*, is a family of -subsets, called *blocks*, chosen from a -set, such that each -subset is contained in at least one of the blocks. The number of blocks is the covering’s *size*, and the minimum size of such a covering is denoted by .

**Problem**Find a closed form, recurrence, or better bounds for . Find a procedure for constructing minimal coverings.

Keywords: recreational mathematics

## Burnside problem ★★★★

Author(s): Burnside

**Conjecture**If a group has generators and exponent , is it necessarily finite?

Keywords:

## Laplacian Degrees of a Graph ★★

Author(s): Guo

**Conjecture**If is a connected graph on vertices, then for .

Keywords: degree sequence; Laplacian matrix

## Random stable roommates ★★

Author(s): Mertens

**Conjecture**The probability that a random instance of the stable roommates problem on people admits a solution is .

Keywords: stable marriage; stable roommates

## Chowla's cosine problem ★★★

Author(s): Chowla

**Problem**Let be a set of positive integers and set What is ?

Keywords: circle; cosine polynomial

## End-Devouring Rays ★

Author(s): Georgakopoulos

**Problem**Let be a graph, a countable end of , and an infinite set of pairwise disjoint -rays in . Prove that there is a set of pairwise disjoint -rays that devours such that the set of starting vertices of rays in equals the set of starting vertices of rays in .

## Seagull problem ★★★

Author(s): Seymour

**Conjecture**Every vertex graph with no independent set of size has a complete graph on vertices as a minor.

Keywords: coloring; complete graph; minor

## $C^r$ Stability Conjecture ★★★★

**Conjecture**Any structurally stable diffeomorphism is hyperbolic.

Keywords: diffeomorphisms,; dynamical systems

## Convex 'Fair' Partitions Of Convex Polygons ★★

Author(s): Nandakumar; Ramana

**Basic Question:** Given any positive integer *n*, can any convex polygon be partitioned into *n* convex pieces so that all pieces have the same area and same perimeter?

**Definitions:** Define a *Fair Partition* of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. Further, if all the resulting pieces are convex, call it a *Convex Fair Partition*.

**Questions:** 1. (Rephrasing the above 'basic' question) Given any positive integer *n*, can any convex polygon be convex fair partitioned into n pieces?

2. If the answer to the above is *"Not always''*, how does one decide the possibility of such a partition for a given convex polygon and a given *n*? And if fair convex partition is allowed by a specific convex polygon for a give *n*, how does one find the *optimal* convex fair partition that *minimizes* the total length of the cut segments?

3. Finally, what could one say about *higher dimensional analogs* of this question?

**Conjecture:** The authors tend to believe that the answer to the above 'basic' question is "yes". In other words they guess: *Every* convex polygon allows a convex fair partition into *n* pieces for any *n*

Keywords: Convex Polygons; Partitioning

## Growth of finitely presented groups ★★★

Author(s): Adyan

**Problem**Does there exist a finitely presented group of intermediate growth?

Keywords: finitely presented; growth

## Chords of longest cycles ★★★

Author(s): Thomassen

**Conjecture**If is a 3-connected graph, every longest cycle in has a chord.

Keywords: chord; connectivity; cycle

## Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

**Conjecture**Let be an integer and let be a minor minimal clutter with . Then either has a minor for some or has Lehman's property.

Keywords: clutter; covering; MFMC property; packing

## Equality in a matroidal circumference bound ★★

**Question**Is the binary affine cube the only 3-connected matroid for which equality holds in the bound where is the circumference (i.e. largest circuit size) of ?

Keywords: circumference

## Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

**Conjecture**If is a highly arc transitive digraph with two ends, then every tile of is a disjoint union of complete bipartite graphs.

Keywords: arc transitive; digraph; infinite graph

## Strong matchings and covers ★★★

Author(s): Aharoni

Let be a hypergraph. A *strongly maximal* matching is a matching so that for every matching . A *strongly minimal* cover is a (vertex) cover so that for every cover .

**Conjecture**If is a (possibly infinite) hypergraph in which all edges have size for some integer , then has a strongly maximal matching and a strongly minimal cover.

Keywords: cover; infinite graph; matching

## Unfriendly partitions ★★★

If is a graph, we say that a partition of is *unfriendly* if every vertex has at least as many neighbors in the other classes as in its own.

**Problem**Does every countably infinite graph have an unfriendly partition into two sets?

Keywords: coloring; infinite graph; partition

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