# Recent Activity

## Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph is -*degenerate* if every subgraph of has a vertex of degree .

**Conjecture**Every simple planar graph has a 5-coloring so that for , the union of any color classes induces a -degenerate graph.

Keywords: coloring; degenerate; planar

## Partial List Coloring ★★★

Author(s): Iradmusa

Let be a simple graph, and for every list assignment let be the maximum number of vertices of which are colorable with respect to . Define , where the minimum is taken over all list assignments with for all .

**Conjecture**[2] Let be a graph with list chromatic number and . Then

Keywords: list assignment; list coloring

## Cube-Simplex conjecture ★★★

Author(s): Kalai

**Conjecture**For every positive integer , there exists an integer so that every polytope of dimension has a -dimensional face which is either a simplex or is combinatorially isomorphic to a -dimensional cube.

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

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