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

Keywords: end; ray

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

Author(s): Palis; Smale

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

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

Author(s): Oxley; Royle

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

Author(s): Cowan; Emerson

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

Author(s): Cook; Levin

Problem   Is P = NP?

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