Recent Activity

Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

Conjecture   Let $ G $ be a simple graph with $ n $ vertices and list chromatic number $ \chi_\ell(G) $. Suppose that $ 0\leq t\leq \chi_\ell $ and each vertex of $ G $ is assigned a list of $ t $ colors. Then at least $ \frac{tn}{\chi_\ell(G)} $ vertices of $ G $ can be colored from these lists.

Keywords: list assignment; list coloring

Combinatorial covering designs

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

A $ (v, k, t) $ covering design, or covering, is a family of $ k $-subsets, called blocks, chosen from a $ v $-set, such that each $ t $-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 $ C(v, k, t) $.

Problem   Find a closed form, recurrence, or better bounds for $ C(v,k,t) $. Find a procedure for constructing minimal coverings.

Keywords: recreational mathematics

Burnside problem ★★★★

Author(s): Burnside

Conjecture   If a group has $ r $ generators and exponent $ n $, is it necessarily finite?


Laplacian Degrees of a Graph ★★

Author(s): Guo

Conjecture   If $ G $ is a connected graph on $ n $ vertices, then $ c_k(G) \ge d_k(G) $ for $ k = 1, 2, \dots, n-1 $.

Keywords: degree sequence; Laplacian matrix

Random stable roommates ★★

Author(s): Mertens

Conjecture   The probability that a random instance of the stable roommates problem on $ n \in 2{\mathbb N} $ people admits a solution is $ \Theta( n ^{-1/4} ) $.

Keywords: stable marriage; stable roommates

Chowla's cosine problem ★★★

Author(s): Chowla

Problem   Let $ A \subseteq {\mathbb N} $ be a set of $ n $ positive integers and set \[m(A) = - \min_x \sum_{a \in A} \cos(ax).\] What is $ m(n) = \min_A m(A) $?

Keywords: circle; cosine polynomial

End-Devouring Rays

Author(s): Georgakopoulos

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

Keywords: end; ray

Seagull problem ★★★

Author(s): Seymour

Conjecture   Every $ n $ vertex graph with no independent set of size $ 3 $ has a complete graph on $ \ge \frac{n}{2} $ vertices as a minor.

Keywords: coloring; complete graph; minor

$C^r$ Stability Conjecture ★★★★

Author(s): Palis; Smale

Conjecture   Any $ C^r $ 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 $ G $ is a 3-connected graph, every longest cycle in $ G $ has a chord.

Keywords: chord; connectivity; cycle

Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

Conjecture   Let $ r \ge 2 $ be an integer and let $ H $ be a minor minimal clutter with $ \frac{1}{r}\tau_r(H) < \tau(H) $. Then either $ H $ has a $ J_k $ minor for some $ k \ge 2 $ or $ H $ 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 $ AG(3,2) $ the only 3-connected matroid for which equality holds in the bound $$E(M) \leq c(M) c(M^*) / 2$$ where $ c(M) $ is the circumference (i.e. largest circuit size) of $ M $?

Keywords: circumference

Highly arc transitive two ended digraphs ★★

Author(s): Cameron; Praeger; Wormald

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

Keywords: arc transitive; digraph; infinite graph

Strong matchings and covers ★★★

Author(s): Aharoni

Let $ H $ be a hypergraph. A strongly maximal matching is a matching $ F \subseteq E(H) $ so that $ |F' \setminus F| \le |F \setminus F'| $ for every matching $ F' $. A strongly minimal cover is a (vertex) cover $ X \subseteq V(H) $ so that $ |X' \setminus X| \ge |X \setminus X'| $ for every cover $ X' $.

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

Keywords: cover; infinite graph; matching

Unfriendly partitions ★★★

Author(s): Cowan; Emerson

If $ G $ is a graph, we say that a partition of $ V(G) $ 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 $ v_0,e_1,v_1,\ldots,v_m $ so that the vertex $ v_i $ is either the head of both $ e_i $ and $ e_{i+1} $ or the tail of both $ e_i $ and $ e_{i+1} $ for every $ 1 \le i \le m-1 $. A digraph is universal if for every pair of edges $ e,f $, there is an alternating walk containing both $ e $ and $ f $

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?

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

F_d versus F_{d+1} ★★★

Author(s): Krajicek

Problem   Find a constant $ k $ such that for any $ d $ there is a sequence of tautologies of depth $ k $ that have polynomial (or quasi-polynomial) size proofs in depth $ d+1 $ Frege system $ F_{d+1} $ but requires exponential size $ F_d $ proofs.

Keywords: Frege system; short proof