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

Keywords: choosability; chromatic number; list coloring; square of a 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 ★★

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

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

## Reconstruction conjecture ★★★★

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 .

Keywords: Disjoint paths; edge-connectivity; spanning trees

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

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

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

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

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.

Keywords: Discrete Geometry; Geometric Ramsey Theory

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

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

Keywords: additive basis; matrix

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

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

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

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

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

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