Recent Activity

2-accessibility of primes ★★

Author(s): Landman; Robertson

Question   Is the set of prime numbers 2-accessible?

Keywords: monochromatic diffsequences; primes

Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph $ G $, we let $ \gamma(G) $ be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and $ \beta(G) $ be the size of the smallest feedback edge set.

Conjecture  If $ G $ is a simple digraph without directed cycles of length $ \le 3 $, then $ \beta(G) \le \frac{1}{2} \gamma(G) $.

Keywords: acyclic; digraph; feedback edge set; triangle free

Tarski's exponential function problem ★★

Author(s): Tarski

Conjecture   Is the theory of the real numbers with the exponential function decidable?

Keywords: Decidability

Jacobian Conjecture ★★★

Author(s): Keller

Conjecture   Let $ k $ be a field of characteristic zero. A collection $ f_1,\ldots,f_n $ of polynomials in variables $ x_1,\ldots,x_n $ defines an automorphism of $ k^n $ if and only if the Jacobian matrix is a nonzero constant.

Keywords: Affine Geometry; Automorphisms; Polynomials

Counting 3-colorings of the hex lattice ★★

Author(s): Thomassen

Problem   Find $ \lim_{n \rightarrow \infty} (\chi( H_n , 3)) ^{ 1 / |V(H_n)| } $.

Keywords: coloring; Lieb's Ice Constant; tiling; torus

Dense rational distance sets in the plane ★★★

Author(s): Ulam

Problem   Does there exist a dense set $ S \subseteq {\mathbb R}^2 $ so that all pairwise distances between points in $ S $ are rational?

Keywords: integral distance; rational distance

Negative association in uniform forests ★★

Author(s): Pemantle

Conjecture   Let $ G $ be a finite graph, let $ e,f \in E(G) $, and let $ F $ be the edge set of a forest chosen uniformly at random from all forests of $ G $. Then \[ {\mathbb P}(e \in F \mid f \in F}) \le {\mathbb P}(e \in F) \]

Keywords: forest; negative association

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem   Let $ G $ be a perfect graph on $ n $ vertices. Is it true that either $ G $ or $ \bar{G} $ contains a complete bipartite subgraph with bipartition $ (A,B) $ so that $ |A|, |B| \ge n^{1 - o(1)} $?

Keywords: perfect graph

Wall-Sun-Sun primes and Fibonacci divisibility ★★

Author(s):

Conjecture   For any prime $ p $, there exists a Fibonacci number divisible by $ p $ exactly once.

Equivalently:

Conjecture   For any prime $ p>5 $, $ p^2 $ does not divide $ F_{p-\left(\frac p5\right)} $ where $ \left(\frac mn\right) $ is the Legendre symbol.

Keywords: Fibonacci; prime

A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture   Let $ a > b > 0 $ be integers. Set $ b_1 = b $ and $ b_{i+1} = {a \bmod {b_i}} $ for $ i \geq 0 $. Eventually we have $ b_{n+1} = 0 $; put $ P(a,b) = n $.

Example: $ P(35, 22) = 7 $, since $ b_1 = 22 $, $ b_2 = 13 $, $ b_3 = 9 $, $ b_4 = 8 $, $ b_5 = 3 $, $ b_6 = 2 $, $ b_7 = 1 $, $ b_8 = 0 $.

Prove or disprove: $ P(a,b) = O((\log a)^2) $.

Keywords: Pierce expansions

Total Colouring Conjecture ★★★

Author(s): Behzad

Conjecture   A total coloring of a graph $ G = (V,E) $ is an assignment of colors to the vertices and the edges of $ G $ such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph $ G $, $ \chi''(G) $, equals the minimum number of colors needed in a total coloring of $ G $. It is an old conjecture of Behzad that for every graph $ G $, the total chromatic number equals the maximum degree of a vertex in $ G $, $ \Delta(G) $ plus one or two. In other words, \[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\]

Keywords: Total coloring

Edge Reconstruction Conjecture ★★★

Author(s): Harary

Conjecture  

Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs

Keywords: reconstruction

Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

Conjecture   For every $ \epsilon > 0 $ and every positive integer $ k $, there exists $ r_0 = r_0(\epsilon,k) $ so that every simple $ r $-regular graph $ G $ with $ r \ge r_0 $ has a $ k $-regular subgraph $ H $ with $ |V(H)| \ge (1- \epsilon) |V(G)| $.

Keywords: regular; subgraph

Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph $ G $ is $ k $-degenerate if every subgraph of $ G $ has a vertex of degree $ \le k $.

Conjecture   Every simple planar graph has a 5-coloring so that for $ 1 \le k \le 4 $, the union of any $ k $ color classes induces a $ (k-1) $-degenerate graph.

Keywords: coloring; degenerate; planar

Partial List Coloring ★★★

Author(s): Iradmusa

Let $ G $ be a simple graph, and for every list assignment $ \mathcal{L} $ let $ \lambda_{\mathcal{L}} $ be the maximum number of vertices of $ G $ which are colorable with respect to $ \mathcal{L} $. Define $ \lambda_t = \min{ \lambda_{\mathcal{L}} } $, where the minimum is taken over all list assignments $ \mathcal{L} $ with $ |\mathcal{L}| = t $ for all $ v \in V(G) $.

Conjecture   [2] Let $ G $ be a graph with list chromatic number $ \chi_\ell $ and $ 1\leq r\leq s\leq \chi_\ell $. Then \[\frac{\lambda_r}{r}\geq\frac{\lambda_s}{s}.\]

Keywords: list assignment; list coloring

Cube-Simplex conjecture ★★★

Author(s): Kalai

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

Keywords: cube; facet; polytope; simplex

S(S(f)) = S(f) for reloids ★★

Author(s): Porton

Question   $ S(S(f)) = S(f) $ for every endo-reloid $ f $?

Keywords: reloid

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?

Keywords: