# Random

## Signing a graph to have small magnitude eigenvalues ★★

**Conjecture**If is the adjacency matrix of a -regular graph, then there is a symmetric signing of (i.e. replace some entries by ) so that the resulting matrix has all eigenvalues of magnitude at most .

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

## Coloring the union of degenerate graphs ★★

Author(s): Tarsi

**Conjecture**The union of a -degenerate graph (a forest) and a -degenerate graph is -colourable.

Keywords:

## Concavity of van der Waerden numbers ★★

Author(s): Landman

For and positive integers, the (mixed) van der Waerden number is the least positive integer such that every (red-blue)-coloring of admits either a -term red arithmetic progression or an -term blue arithmetic progression.

**Conjecture**For all and with , .

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 be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?

Keywords: polynomial algorithm; search problem

## Magic square of squares ★★

Author(s): LaBar

**Question**Does there exist a magic square composed of distinct perfect squares?

Keywords:

## Characterizing (aleph_0,aleph_1)-graphs ★★★

Call a graph an -*graph* if it has a bipartition so that every vertex in has degree and every vertex in has degree .

**Problem**Characterize the -graphs.

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

## Are all Fermat Numbers square-free? ★★★

Author(s):

**Conjecture**Are all Fermat Numbers Square-Free?

Keywords:

## 2-accessibility of primes ★★

**Question**Is the set of prime numbers 2-accessible?

Keywords: monochromatic diffsequences; primes

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

## Circular choosability of planar graphs ★

Author(s): Mohar

Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is

**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 is 2-large, then is large.

Keywords: 2-large sets; large sets

## Covering systems with big moduli ★★

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

Keywords: covering system

## 57-regular Moore graph? ★★★

Keywords: cage; Moore graph

## Switching reconstruction of digraphs ★★

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

Keywords:

## A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

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

Keywords: edge-coloring; hypergraph; Vizing

## Diophantine quintuple conjecture ★★

Author(s):

**Definition**A set of m positive integers is called a Diophantine -tuple if is a perfect square for all .

**Conjecture (1)**Diophantine quintuple does not exist.

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

**Conjecture (2)**If is a Diophantine quadruple and , then

Keywords:

## Arc-disjoint strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

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

Keywords:

## Even vs. odd latin squares ★★★

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 , the number of even latin squares of order and the number of odd latin squares of order 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 grid. The first player (if any) to occupy a set of 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.

## Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

**Conjecture**For every positive integer , every (loopless) graph with immerses .

Keywords: coloring; complete graph; immersion

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

Author(s): Beneš

**Problem ()**Find a sufficient condition for a straight -stage graph to be rearrangeable. In particular, what about a straight uniform graph?

**Conjecture ()**Let be a simple regular ordered -stage graph. Suppose that the graph is externally connected, for some . Then the graph is rearrangeable.

Keywords:

## Twin prime conjecture ★★★★

Author(s):

**Conjecture**There exist infinitely many positive integers so that both and 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 .

Keywords:

## A conjecture on iterated circumcentres ★★

Author(s): Goddyn

**Conjecture**Let be a sequence of points in with the property that for every , the points are distinct, lie on a unique sphere, and further, is the center of this sphere. If this sequence is periodic, must its period be ?

Keywords: periodic; plane geometry; sequence

## The Erdös-Hajnal Conjecture ★★★

**Conjecture**For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .

Keywords: induced subgraph

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

Author(s): Jaeger

**Conjecture**If is a finite field with at least 4 elements and is an invertible matrix with entries in , then there are column vectors which have no coordinates equal to zero such that .

Keywords: invertible; nowhere-zero flow

## Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The *Odd Distance Graph*, denoted , is the graph with vertex set and two points adjacent if the distance between them is an odd integer.

**Question**Is ?

Keywords: coloring; geometric graph; odd distance

## 3-accessibility of Fibonacci numbers ★★

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

**Question**Is 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 and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.

**Question 1**. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.

**Question 2**. What is the smallest number of disjoint spanning trees creates a graph 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:

## A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

**Conjecture**Let be integers. Set and for . Eventually we have ; put .

Example: , since , , , , , , , .

Prove or disprove: .

Keywords: Pierce expansions

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

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

Author(s): Charles Pugh

**Conjecture**Let and . Then for any neighborhood there is such that is periodic point of

There is an analogous conjecture for flows ( vector fields . In the case of diffeos this was proved by Charles Pugh for . In the case of Flows this has been solved by Sushei Hayahshy for . But in the two cases the problem is wide open for

Keywords: Dynamics , Pertubation

## Packing T-joins ★★

Author(s): DeVos

**Conjecture**There exists a fixed constant (probably suffices) so that every graft with minimum -cut size at least contains a -join packing of size at least .

## Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

**Conjecture**Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?

Keywords: crossing number; surface

## Erdös-Szekeres conjecture ★★★

**Conjecture**Every set of points in the plane in general position contains a subset of points which form a convex -gon.

Keywords: combinatorial geometry; Convex Polygons; ramsey theory

## The Two Color Conjecture ★★

Author(s): Neumann-Lara

**Conjecture**If is an orientation of a simple planar graph, then there is a partition of into so that the graph induced by is acyclic for .

## 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 vertex graph with no independent set of size has a complete graph on vertices as a minor.

Keywords: coloring; complete graph; minor

## Weighted colouring of hexagonal graphs. ★★

**Conjecture**There is an absolute constant such that for every hexagonal graph and vertex weighting ,

Keywords:

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

Author(s): Allagan

**Question**Given , what is the smallest integer such that ?

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