Random

Signing a graph to have small magnitude eigenvalues ★★

Author(s): Bilu; Linial

Conjecture   If $ A $ is the adjacency matrix of a $ d $-regular graph, then there is a symmetric signing of $ A $ (i.e. replace some $ +1 $ entries by $ -1 $) so that the resulting matrix has all eigenvalues of magnitude at most $ 2 \sqrt{d-1} $.

Keywords: eigenvalue; expander; Ramanujan graph; signed graph; signing

Coloring the union of degenerate graphs ★★

Author(s): Tarsi

Conjecture   The union of a $ 1 $-degenerate graph (a forest) and a $ 2 $-degenerate graph is $ 5 $-colourable.

Keywords:

Concavity of van der Waerden numbers ★★

Author(s): Landman

For $ k $ and $ \ell $ positive integers, the (mixed) van der Waerden number $ w(k,\ell) $ is the least positive integer $ n $ such that every (red-blue)-coloring of $ [1,n] $ admits either a $ k $-term red arithmetic progression or an $ \ell $-term blue arithmetic progression.

Conjecture   For all $ k $ and $ \ell $ with $ k \geq \ell $, $ w(k,\ell) \geq w(k+1,\ell-1) $.

Keywords: arithmetic progression; van der Waerden

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

Subset-sums equality (pigeonhole version) ★★★

Author(s):

Problem   Let $ a_1,a_2,\ldots,a_n $ be natural numbers with $ \sum_{i=1}^n a_i < 2^n - 1 $. It follows from the pigeon-hole principle that there exist distinct subsets $ I,J \subseteq \{1,\ldots,n\} $ with $ \sum_{i \in I} a_i = \sum_{j \in J} a_j $. Is it possible to find such a pair $ I,J $ in polynomial time?

Keywords: polynomial algorithm; search problem

Magic square of squares ★★

Author(s): LaBar

Question   Does there exist a $ 3\times 3 $ magic square composed of distinct perfect squares?

Keywords:

Characterizing (aleph_0,aleph_1)-graphs ★★★

Author(s): Diestel; Leader

Call a graph an $ (\aleph_0,\aleph_1) $-graph if it has a bipartition $ (A,B) $ so that every vertex in $ A $ has degree $ \aleph_0 $ and every vertex in $ B $ has degree $ \aleph_1 $.

Problem   Characterize the $ (\aleph_0,\aleph_1) $-graphs.

Keywords: binary tree; infinite graph; normal spanning tree; set theory

Are all Fermat Numbers square-free? ★★★

Author(s):

Conjecture   Are all Fermat Numbers \[ F_n  = 2^{2^{n } }  + 1 \] Square-Free?

Keywords:

2-accessibility of primes ★★

Author(s): Landman; Robertson

Question   Is the set of prime numbers 2-accessible?

Keywords: monochromatic diffsequences; primes

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

Circular choosability of planar graphs

Author(s): Mohar

Let $ G = (V, E) $ be a graph. If $ p $ and $ q $ are two integers, a $ (p,q) $-colouring of $ G $ is a function $ c $ from $ V $ to $ \{0,\dots,p-1\} $ such that $ q \le |c(u)-c(v)| \le p-q $ for each edge $ uv\in E $. Given a list assignment $ L $ of $ G $, i.e.~a mapping that assigns to every vertex $ v $ a set of non-negative integers, an $ L $-colouring of $ G $ is a mapping $ c : V \to N $ such that $ c(v)\in L(v) $ for every $ v\in V $. A list assignment $ L $ is a $ t $-$ (p,q) $-list-assignment if $ L(v) \subseteq \{0,\dots,p-1\} $ and $ |L(v)| \ge tq $ for each vertex $ v \in V $ . Given such a list assignment $ L $, the graph G is $ (p,q) $-$ L $-colourable if there exists a $ (p,q) $-$ L $-colouring $ c $, i.e. $ c $ is both a $ (p,q) $-colouring and an $ L $-colouring. For any real number $ t \ge 1 $, the graph $ G $ is $ t $-$ (p,q) $-choosable if it is $ (p,q) $-$ L $-colourable for every $ t $-$ (p,q) $-list-assignment $ L $. Last, $ G $ is circularly $ t $-choosable if it is $ t $-$ (p,q) $-choosable for any $ p $, $ q $. The circular choosability (or circular list chromatic number or circular choice number) of G is $$cch(G) := \inf\{t \ge 1 : G \text{ is circularly $t$-choosable}\}.$$

Problem   What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs

Earth-Moon Problem ★★

Author(s): Ringel

Problem   What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?

Keywords:

The large sets conjecture ★★★

Author(s): Brown; Graham; Landman

Conjecture   If $ A $ is 2-large, then $ A $ is large.

Keywords: 2-large sets; large sets

Covering systems with big moduli ★★

Author(s): Erdos; Selfridge

Problem   Does for every integer $ N $ exist a covering system with all moduli distinct and at least equal to~$ N $?

Keywords: covering system

57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

Question   Does there exist a 57-regular graph with diameter 2 and girth 5?

Keywords: cage; Moore graph

Switching reconstruction of digraphs ★★

Author(s): Bondy; Mercier

Question   Are there any switching-nonreconstructible digraphs on twelve or more vertices?

Keywords:

A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

Conjecture   Let $ H $ be a simple $ d $-uniform hypergraph, and assume that every set of $ d-1 $ points is contained in at most $ r $ edges. Then there exists an $ r+d-1 $-edge-coloring so that any two edges which share $ d-1 $ vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing

Diophantine quintuple conjecture ★★

Author(s):

Definition   A set of m positive integers $ \{a_1, a_2, \dots, a_m\} $ is called a Diophantine $ m $-tuple if $ a_i\cdot a_j + 1 $ is a perfect square for all $ 1 \leq i < j \leq m $.
Conjecture  (1)   Diophantine quintuple does not exist.

It would follow from the following stronger conjecture [Da]:

Conjecture  (2)   If $ \{a, b, c, d\} $ is a Diophantine quadruple and $ d > \max \{a, b, c\} $, then $ d = a + b + c + 2bc + 2\sqrt{(ab+1)(ac+1)(bc+1)}. $

Keywords:

Perfect cuboid ★★

Author(s):

Conjecture   Does a perfect cuboid exist?

Keywords:

Arc-disjoint strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

Conjecture   There exists an ineteger $ k $ so that every $ k $-arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs?

Keywords:

Even vs. odd latin squares ★★★

Author(s): Alon; Tarsi

A latin square is even if the product of the signs of all of the row and column permutations is 1 and is odd otherwise.

Conjecture   For every positive even integer $ n $, the number of even latin squares of order $ n $ and the number of odd latin squares of order $ n $ are different.

Keywords: latin square

Transversal achievement game on a square grid ★★

Author(s): Erickson

Problem   Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $ n \times  n $ grid. The first player (if any) to occupy a set of $ n $ cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?

Keywords: game

Are there an infinite number of lucky primes?

Author(s): Lazarus: Gardiner: Metropolis; Ulam

Conjecture   If every second positive integer except 2 is remaining, then every third remaining integer except 3, then every fourth remaining integer etc. , an infinite number of the remaining integers are prime.

Keywords: lucky; prime; seive

Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

Conjecture   For every positive integer $ t $, every (loopless) graph $ G $ with $ \chi(G) \ge t $ immerses $ K_t $.

Keywords: coloring; complete graph; immersion

Beneš Conjecture (graph-theoretic form) ★★★

Author(s): Beneš

Problem  ($ \dag $)   Find a sufficient condition for a straight $ \ell $-stage graph to be rearrangeable. In particular, what about a straight uniform graph?
Conjecture  ($ \diamond $)   Let $ L $ be a simple regular ordered $ 2 $-stage graph. Suppose that the graph $ L^m $ is externally connected, for some $ m\ge1 $. Then the graph $ L^{2m} $ is rearrangeable.

Keywords:

Twin prime conjecture ★★★★

Author(s):

Conjecture   There exist infinitely many positive integers $ n $ so that both $ n $ and $ n+2 $ are prime.

Keywords: prime; twin prime

Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture   Every finite group is the Galois group of some finite algebraic extension of $ \mathbb Q $.

Keywords:

A conjecture on iterated circumcentres ★★

Author(s): Goddyn

Conjecture   Let $ p_1,p_2,p_3,\ldots $ be a sequence of points in $ {\mathbb R}^d $ with the property that for every $ i \ge d+2 $, the points $ p_{i-1}, p_{i-2}, \ldots p_{i-d-1} $ are distinct, lie on a unique sphere, and further, $ p_i $ is the center of this sphere. If this sequence is periodic, must its period be $ 2d+4 $?

Keywords: periodic; plane geometry; sequence

The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed graph $ H $, there exists a constant $ \delta(H) $, so that every graph $ G $ without an induced subgraph isomorphic to $ H $ contains either a clique or an independent set of size $ |V(G)|^{\delta(H)} $.

Keywords: induced subgraph

A nowhere-zero point in a linear mapping ★★★

Author(s): Jaeger

Conjecture   If $ {\mathbb F} $ is a finite field with at least 4 elements and $ A $ is an invertible $ n \times n $ matrix with entries in $ {\mathbb F} $, then there are column vectors $ x,y \in {\mathbb F}^n $ which have no coordinates equal to zero such that $ Ax=y $.

Keywords: invertible; nowhere-zero flow

The circular embedding conjecture ★★★

Author(s): Haggard

Conjecture   Every 2-connected graph may be embedded in a surface so that the boundary of each face is a cycle.

Keywords: cover; cycle

Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The Odd Distance Graph, denoted $ {\mathcal O} $, is the graph with vertex set $ {\mathbb R}^2 $ and two points adjacent if the distance between them is an odd integer.

Question   Is $ \chi({\mathcal O}) = \infty $?

Keywords: coloring; geometric graph; odd distance

3-accessibility of Fibonacci numbers ★★

Author(s): Landman; Robertson

Question   Is the set of Fibonacci numbers 3-accessible?

Keywords: Fibonacci numbers; monochromatic diffsequences

Primitive pythagorean n-tuple tree ★★

Author(s):

Conjecture   Find linear transformation construction of primitive pythagorean n-tuple tree!

Keywords:

Mixing Circular Colourings

Author(s): Brewster; Noel

Question   Is $ \mathfrak{M}_c(G) $ always rational?

Keywords: discrete homotopy; graph colourings; mixing

What is the smallest number of disjoint spanning trees made a graph Hamiltonian ★★

Author(s): Goldengorin

We are given a complete simple undirected weighted graph $ G_1=(V,E) $ and its first arbitrary shortest spanning tree $ T_1=(V,E_1) $. We define the next graph $ G_2=(V,E\setminus E_1) $ and find on $ G_2 $ the second arbitrary shortest spanning tree $ T_2=(V,E_2) $. We continue similarly by finding $ T_3=(V,E_3) $ on $ G_3=(V,E\setminus \cup_{i=1}^{2}E_i) $, etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let $ T^{k}=(V,\cup_{i=1}^{k}E_i) $ be the graph obtained as union of all $ k $ disjoint trees.

Question 1. What is the smallest number of disjoint spanning trees creates a graph $ T^{k} $ containing a Hamiltonian path.

Question 2. What is the smallest number of disjoint spanning trees creates a graph $ T^{k} $ containing a shortest Hamiltonian path?

Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?

Keywords: 1-trees; cycle; Hamitonian path; spanning trees

Three-chromatic (0,2)-graphs ★★

Author(s): Payan

Question   Are there any (0,2)-graphs with chromatic number exactly three?

Keywords:

Rank vs. Genus ★★★

Author(s): Johnson

Question   Is there a hyperbolic 3-manifold whose fundamental group rank is strictly less than its Heegaard genus? How much can the two differ by?

Keywords:

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

Author(s): Porton

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

Keywords: reloid

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

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

Closing Lemma for Diffeomorphism (Dynamical Systems) ★★★★

Author(s): Charles Pugh

Conjecture   Let $ f\in Diff^{r}(M) $ and $ p\in\omega_{f}  $. Then for any neighborhood $ V_{f}\subset Diff^{r}(M)  $ there is $ g\in V_{f} $ such that $ p $ is periodic point of $ g $

There is an analogous conjecture for flows ( $ C^{r} $ vector fields . In the case of diffeos this was proved by Charles Pugh for $ r = 1 $. In the case of Flows this has been solved by Sushei Hayahshy for $ r = 1 $ . But in the two cases the problem is wide open for $ r > 1 $

Keywords: Dynamics , Pertubation

Packing T-joins ★★

Author(s): DeVos

Conjecture   There exists a fixed constant $ c $ (probably $ c=1 $ suffices) so that every graft with minimum $ T $-cut size at least $ k $ contains a $ T $-join packing of size at least $ (2/3)k-c $.

Keywords: packing; T-join

Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture   Let $ G $ be the disjoint union of the graphs $ G_1 $ and $ G_2 $ and let $ \Sigma $ be a surface. Is it true that every optimal drawing of $ G $ on $ \Sigma $ has the property that $ G_1 $ and $ G_2 $ are disjoint?

Keywords: crossing number; surface

Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture   Every set of $ 2^{n-2} + 1 $ points in the plane in general position contains a subset of $ n $ points which form a convex $ n $-gon.

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

The Two Color Conjecture ★★

Author(s): Neumann-Lara

Conjecture   If $ G $ is an orientation of a simple planar graph, then there is a partition of $ V(G) $ into $ \{X_1,X_2\} $ so that the graph induced by $ X_i $ is acyclic for $ i=1,2 $.

Keywords: acyclic; digraph; planar

Seymour's Second Neighbourhood Conjecture ★★★

Author(s): Seymour

Conjecture   Any oriented graph has a vertex whose outdegree is at most its second outdegree.

Keywords: Caccetta-Häggkvist; neighbourhood; second; Seymour

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

Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

Conjecture   There is an absolute constant $ c $ such that for every hexagonal graph $ G $ and vertex weighting $ p:V(G)\rightarrow \mathbb{N} $, $$\chi(G,p) \leq \frac{9}{8}\omega(G,p) + c $$

Keywords:

List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given $ a,b\geq2 $, what is the smallest integer $ t\geq0 $ such that $ \chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t) $?

Keywords: complete bipartite graph; complete multipartite graph; list coloring