# Random

## Lovász Path Removal Conjecture ★★

Author(s): Lovasz

Conjecture   There is an integer-valued function such that if is any -connected graph and and are any two vertices of , then there exists an induced path with ends and such that is -connected.

Keywords:

## Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

Conjecture   Every planar graph is acyclically 5-choosable.

Keywords:

## Highly connected graphs with no K_n minor ★★★

Author(s): Thomas

Problem   Is it true for all , that every sufficiently large -connected graph without a minor has a set of vertices whose deletion results in a planar graph?

Keywords: connectivity; minor

## The large sets conjecture ★★★

Author(s): Brown; Graham; Landman

Conjecture   If is 2-large, then is large.

Keywords: 2-large sets; large sets

## Edge-disjoint Hamilton cycles in highly strongly connected tournaments. ★★

Author(s): Thomassen

Conjecture   For every , there is an integer so that every strongly -connected tournament has edge-disjoint Hamilton cycles.

Keywords:

## Covering a square with unit squares ★★

Author(s):

Conjecture   For any integer , it is impossible to cover a square of side greater than with unit squares.

Keywords:

## Criterion for boundedness of power series ★

Author(s): Rüdinger

Question   Give a necessary and sufficient criterion for the sequence so that the power series is bounded for all .

Keywords: boundedness; power series; real analysis

## Choosability of Graph Powers ★★

Author(s): Noel

Question  (Noel, 2013)   Does there exist a function such that for every graph ,

## Square achievement game on an n x n 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 four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

Keywords: game

## The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number of is the minimum number of crossings in all drawings of in the plane.

The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.

Conjecture

Keywords: crossing number; hypercube

## Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem   Let be a perfect graph on vertices. Is it true that either or contains a complete bipartite subgraph with bipartition so that ?

Keywords: perfect graph

## Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture   Every finite group is the Galois group of some finite algebraic extension of .

Keywords:

## Durer's Conjecture ★★★

Author(s): Durer; Shephard

Conjecture   Every convex polytope has a non-overlapping edge unfolding.

Keywords: folding; polytope

## Reconstruction conjecture ★★★★

Author(s): Kelly; Ulam

The deck of a graph is the multiset consisting of all unlabelled subgraphs obtained from by deleting a vertex in all possible ways (counted according to multiplicity).

Conjecture   If two graphs on vertices have the same deck, then they are isomorphic.

Keywords: reconstruction

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

## Beneš Conjecture ★★★

Author(s): Beneš

Given a partition of a finite set , stabilizer of , denoted , is the group formed by all permutations of preserving each block in .

Problem  ()   Find a sufficient condition for a sequence of partitions of to be universal, i.e. to yield the following decomposition of the symmetric group on : In particular, what about the sequence , where is a permutation of ?
Conjecture  (Beneš)   Let be a uniform partition of and be a permutation of such that . Suppose that the set is transitive, for some integer . Then

Keywords:

## Matching cut and girth ★★

Author(s):

Question   For every does there exists a such that every graph with average degree smaller than and girth at least has a matching-cut?

Keywords: matching cut, matching, cut

## Are there infinite number of Mersenne Primes? ★★★★

Author(s):

Conjecture   A Mersenne prime is a Mersenne number that is prime.

Are there infinite number of Mersenne Primes?

Keywords: Mersenne number; Mersenne prime

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

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

## Kriesell's Conjecture ★★

Author(s): Kriesell

Conjecture   Let be a graph and let such that for any pair there are edge-disjoint paths from to in . Then contains edge-disjoint trees, each of which contains .

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

Author(s): Allagan

Question   Given , what is the smallest integer such that ?

## Covering powers of cycles with equivalence subgraphs ★

Author(s):

Conjecture   Given and , the graph has equivalence covering number .

Keywords:

## The 3n+1 conjecture ★★★

Author(s): Collatz

Conjecture   Let if is odd and if is even. Let . Assume we start with some number and repeatedly take the of the current number. Prove that no matter what the initial number is we eventually reach .

Keywords: integer sequence

## Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.

Conjecture   If is the maximal degree of a graph , then is strongly -colorable.

Keywords: strong coloring

## Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation has a dominating set of size .

Keywords: coloring; domination; multigrid; planar graph; triangulation

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

Keywords: cube; facet; polytope; simplex

## Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let be a set of points in the plane. Two points and in are visible with respect to if the line segment between and contains no other point in .

Conjecture   For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.

## A homomorphism problem for flows ★★

Author(s): DeVos

Conjecture   Let be abelian groups and let and satisfy and . If there is a homomorphism from to , then every graph with a B-flow has a B'-flow.

Keywords: homomorphism; nowhere-zero flow; tension

## Exact colorings of graphs ★★

Author(s): Erickson

Conjecture   For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .

Keywords: graph coloring; ramsey theory

## Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

Question   Is every Cayley graph Hamiltonian?

Keywords:

## 3-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every 4-edge-connected graph has a nowhere-zero 3-flow.

Keywords: nowhere-zero flow

## The Hodge Conjecture ★★★★

Author(s): Hodge

Conjecture   Let be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of .

Keywords: Hodge Theory; Millenium Problems

## Lindelöf hypothesis ★★

Author(s): Lindelöf

Conjecture   For any

Since can be replaced by a smaller value, we can also write the conjecture as, for any positive ,

Keywords: Riemann Hypothesis; zeta

## Ádám's Conjecture ★★★

Author(s): Ádám

Conjecture   Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

## trace inequality ★★

Author(s):

Let be positive semidefinite, by Jensen's inequality, it is easy to see , whenever .

What about the , is it still valid?

Keywords:

## Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An alternating walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is universal if for every pair of edges , there is an alternating walk containing both and

Question   Does there exist a locally finite highly arc transitive digraph which is universal?

Keywords: arc transitive; digraph

## The additive basis conjecture ★★★

Author(s): Jaeger; Linial; Payan; Tarsi

Conjecture   For every prime , there is a constant (possibly ) so that the union (as multisets) of any bases of the vector space contains an additive basis.

## Another conjecture about reloids and funcoids ★★

Author(s): Porton

Definition   for reloid .
Conjecture   for every funcoid .

Note: it is known that (see below mentioned online article).

Keywords:

## Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index is the minimum number of colours in a strong edge-colouring of .

Conjecture

Keywords:

## Domination in cubic graphs ★★

Author(s): Reed

Problem   Does every 3-connected cubic graph satisfy ?

Keywords: cubic graph; domination

## Forcing a $K_6$-minor ★★

Author(s): Barát ; Joret; Wood

Conjecture   Every graph with minimum degree at least 7 contains a -minor.
Conjecture   Every 7-connected graph contains a -minor.

Keywords: connectivity; graph minors

## Turán number of a finite family. ★★

Author(s): Erdos; Simonovits

Given a finite family of graphs and an integer , the Turán number of is the largest integer such that there exists a graph on vertices with edges which contains no member of as a subgraph.

Conjecture   For every finite family of graphs there exists an such that .

Keywords:

## Wide partition conjecture ★★

Author(s): Chow; Taylor

Conjecture   An integer partition is wide if and only if it is Latin.

Keywords:

## The permanent conjecture ★★

Author(s): Kahn

Conjecture   If is an invertible matrix, then there is an submatrix of so that is nonzero.

Keywords: invertible; matrix; permanent

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

## Lucas Numbers Modulo m ★★

Author(s):

Conjecture   The sequence {L(n) mod m}, where L(n) are the Lucas numbers, contains a complete residue system modulo m if and only if m is one of the following: 2, 4, 6, 7, 14, 3^k, k >=1.

Keywords: Lucas numbers

## Friendly partitions ★★

Author(s): DeVos

A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

Problem   Is it true that for every , all but finitely many -regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

## Seymour's self-minor conjecture ★★★

Author(s): Seymour

Conjecture   Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

## Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture   is the only -chromatic double-critical graph

Keywords: coloring; complete graph