# Random

## Lonely runner conjecture ★★★

Author(s): Cusick; Wills

Conjecture   Suppose runners having distinct constant speeds start at a common point and run laps on a circular track with circumference 1. Then for any given runner, there is a time at which that runner is distance at least (along the track) away from every other runner.

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

## Triangle free strongly regular graphs ★★★

Author(s):

Problem   Is there an eighth triangle free strongly regular graph?

Keywords: strongly regular; triangle free

## Antidirected trees in digraphs ★★

Author(s): Addario-Berry; Havet; Linhares Sales; Reed; Thomassé

An antidirected tree is an orientation of a tree in which every vertex has either indegree 0 or outdergree 0.

Conjecture   Let be a digraph. If , then contains every antidirected tree of order .

Keywords:

## General position subsets ★★

Author(s): Gowers

Question   What is the least integer such that every set of at least points in the plane contains collinear points or a subset of points in general position (no three collinear)?

## P vs. NP ★★★★

Author(s): Cook; Levin

Problem   Is P = NP?

## Birch & Swinnerton-Dyer conjecture ★★★★

Author(s):

Conjecture   Let be an elliptic curve over a number field . Then the order of the zeros of its -function, , at is the Mordell-Weil rank of .

Keywords:

## Bouchet's 6-flow conjecture ★★★

Author(s): Bouchet

Conjecture   Every bidirected graph with a nowhere-zero -flow for some , has a nowhere-zero -flow.

Keywords: bidirected graph; nowhere-zero flow

## Pentagon problem ★★★

Author(s): Nesetril

Question   Let be a 3-regular graph that contains no cycle of length shorter than . Is it true that for large enough~ there is a homomorphism ?

Keywords: cubic; homomorphism

## Linear Hypergraphs with Dimension 3 ★★

Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl

Conjecture   Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.

Keywords: Hypergraphs

## Monochromatic reachability in arc-colored digraphs ★★★

Author(s): Sands; Sauer; Woodrow

Conjecture   For every , there exists an integer such that if is a digraph whose arcs are colored with colors, then has a set which is the union of stables sets so that every vertex has a monochromatic path to some vertex in .

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:

## Turán Problem for $10$-Cycles in the Hypercube ★★

Author(s): Erdos

Problem   Bound the extremal number of in the hypercube.

Keywords: cycles; extremal combinatorics; hypercube

## Unfriendly partitions ★★★

Author(s): Cowan; Emerson

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

## Monochromatic empty triangles ★★★

Author(s):

If is a finite set of points which is 2-colored, an empty triangle is a set with so that the convex hull of is disjoint from . We say that is monochromatic if all points in are the same color.

Conjecture   There exists a fixed constant with the following property. If is a set of points in general position which is 2-colored, then it has monochromatic empty triangles.

Keywords: empty triangle; general position; ramsey theory

## The robustness of the tensor product ★★★

Author(s): Ben-Sasson; Sudan

Problem   Given two codes , their Tensor Product is the code that consists of the matrices whose rows are codewords of and whose columns are codewords of . The product is said to be robust if whenever a matrix is far from , the rows (columns) of are far from (, respectively).

The problem is to give a characterization of the pairs whose tensor product is robust.

Keywords: codes; coding; locally testable; robustness

## Growth of finitely presented groups ★★★

Problem   Does there exist a finitely presented group of intermediate growth?

Keywords: finitely presented; growth

## (m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

Conjecture   Every bridgeless graph has a (5,2)-cycle-cover.

Keywords: cover; cycle

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

## Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group , let () denote the smallest integer so that every sequence of elements of has a subsequence of length (length ) which has product equal to 1 in some order.

Conjecture   for every finite group .

Keywords: subsequence sum; zero sum

## The Riemann Hypothesis ★★★★

Author(s): Riemann

The zeroes of the Riemann zeta function that are inside the Critical Strip (i.e. the vertical strip of the complex plane where the real part of the complex variable is in ]0;1[), are actually located on the Critical line ( the vertical line of the complex plane with real part equal to 1/2)

Keywords: Millenium Problems; zeta

## Few subsequence sums in Z_n x Z_n ★★

Conjecture   For every , the sequence in consisting of copes of and copies of has the fewest number of distinct subsequence sums over all zero-free sequences from of length .

Keywords: subsequence sum; zero sum

## Strong 5-cycle double cover conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Let be a circuit in a bridgeless cubic graph . Then there is a five cycle double cover of such that is a subgraph of one of these five cycles.

Keywords: cycle cover

## Ramsey properties of Cayley graphs ★★★

Author(s): Alon

Conjecture   There exists a fixed constant so that every abelian group has a subset with so that the Cayley graph has no clique or independent set of size .

Keywords: Cayley graph; Ramsey number

## Divisibility of central binomial coefficients ★★

Author(s): Graham

Problem  (1)   Prove that there exist infinitely many positive integers such that
Problem  (2)   Prove that there exists only a finite number of positive integers such that

Keywords:

## Frankl's union-closed sets conjecture ★★

Author(s): Frankl

Conjecture   Let be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists such that is an element of at least half the members of .

Keywords:

## The Double Cap Conjecture ★★

Author(s): Kalai

Conjecture   The largest measure of a Lebesgue measurable subset of the unit sphere of containing no pair of orthogonal vectors is attained by two open caps of geodesic radius around the north and south poles.

## Jones' conjecture ★★

Author(s): Kloks; Lee; Liu

For a graph , let denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let denote the cardinality of a minimum feedback vertex set (set of vertices so that is acyclic).

Conjecture   For every planar graph , .

Keywords: cycle packing; feedback vertex set; planar graph

## 3-flow conjecture ★★★

Author(s): Tutte

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

Keywords: nowhere-zero flow

## 3 is a primitive root modulo primes of the form 16 q^4 + 1, where q>3 is prime ★★

Author(s):

Conjecture   is a primitive root modulo for all primes , where is prime.

Keywords:

## Inequality for square summable complex series ★★

Author(s): Retkes

Conjecture   For all the following inequality holds

Keywords: Inequality

## Mixing Circular Colourings ★

Author(s): Brewster; Noel

Question   Is always rational?

Keywords: discrete homotopy; graph colourings; mixing

## Nonseparating planar continuum ★★

Author(s):

Conjecture   Does any path-connected, compact set in the plane which does not separate the plane have the fixed point property?

A set has the fixed point property if every continuous map from it into itself has a fixed point.

Keywords: fixed point

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

## Convex Equipartitions with Extreme Perimeter ★★

Author(s): Nandakumar

To divide a given 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total perimeter of pieces is (1) maximized (2) minimized.

Remark: It appears maximizing the total perimeter is the easier problem.

Keywords: convex equipartition

## Counterexamples to the Baillie-PSW primality test ★★

Author(s):

Problem  (1)   Find a counterexample to Baillie-PSW primality test or prove that there is no one.
Problem  (2)   Find a composite or which divides both (see Fermat pseudoprime) and the Fibonacci number (see Lucas pseudoprime), or prove that there is no such .

Keywords:

## Quartic rationally derived polynomials ★★★

Author(s): Buchholz; MacDougall

Call a polynomial rationally derived if all roots of and the nonzero derivatives of are rational.

Conjecture   There does not exist a quartic rationally derived polynomial with four distinct roots.

Keywords: derivative; diophantine; elliptic; polynomial

## Convex uniform 5-polytopes ★★

Author(s):

Problem   Enumerate all convex uniform 5-polytopes.

Keywords:

## The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

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

Conjecture

Keywords: complete bipartite graph; crossing number

## Oriented chromatic number of planar graphs ★★

Author(s):

An oriented colouring of an oriented graph is assignment of colours to the vertices such that no two arcs receive ordered pairs of colours and . It is equivalent to a homomorphism of the digraph onto some tournament of order .

Problem   What is the maximal possible oriented chromatic number of an oriented planar graph?

Keywords: oriented coloring; oriented graph; planar graph

## Shuffle-Exchange Conjecture (graph-theoretic form) ★★★

Author(s): Beneš; Folklore; Stone

Given integers , the 2-stage Shuffle-Exchange graph/network, denoted , is the simple -regular bipartite graph with the ordered pair of linearly labeled parts and , where , such that vertices and are adjacent if and only if (see Fig.1).

Given integers , the -stage Shuffle-Exchange graph/network, denoted , is the proper (i.e., respecting all the orders) concatenation of identical copies of (see Fig.1).

Let be the smallest integer such that the graph is rearrangeable.

Problem   Find .
Conjecture   .

Keywords:

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

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

## Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

Conjecture   For every rational and every rational , there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula on variables, for some , and clauses drawn uniformly at random from the set of formulas on variables. Return with probability at least 0.5 (over the instances) that is typical without returning typical for any instance with at least simultaneously satisfiable clauses.

Keywords: NP; randomness in TCS; satisfiability

## Every metamonovalued funcoid is monovalued ★★

Author(s): Porton

Conjecture   Every metamonovalued funcoid is monovalued.

The reverse is almost trivial: Every monovalued funcoid is metamonovalued.

Keywords: monovalued

## Graphs of exact colorings ★★

Author(s):

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:

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

Keywords: acyclic; digraph; planar

## Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let be a finite undirected simple graph.

A -page book embedding of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The book thickness of , denoted by bt is the minimum integer for which there is a -page book embedding of .

Let be the graph obtained by subdividing each edge of exactly once.

Conjecture   There is a function such that for every graph ,

Keywords: book embedding; book thickness

## inverse of an integer matrix ★★

Author(s): Gregory

Question   I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all . Suppose X is an m-by-n integer matrix . Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.

## Approximation ratio for k-outerplanar graphs ★★

Author(s): Bentz

Conjecture   Is the approximation ratio for the Maximum Edge Disjoint Paths (MaxEDP) or the Maximum Integer Multiflow problem (MaxIMF) bounded by a constant in -outerplanar graphs or tree-width graphs?