# Random

## Directed path of length twice the minimum outdegree ★★★

Author(s): Thomassé

Conjecture   Every oriented graph with minimum outdegree contains a directed path of length .

Keywords:

## Do any three longest paths in a connected graph have a vertex in common? ★★

Author(s): Gallai

Conjecture   Do any three longest paths in a connected graph have a vertex in common?

Keywords:

## PTAS for feedback arc set in tournaments ★★

Author(s): Ailon; Alon

Question   Is there a polynomial time approximation scheme for the feedback arc set problem for the class of tournaments?

Keywords: feedback arc set; PTAS; tournament

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

## Circular coloring triangle-free subcubic planar graphs ★★

Author(s): Ghebleh; Zhu

Problem   Does every triangle-free planar graph of maximum degree three have circular chromatic number at most ?

Keywords: circular coloring; planar graph; triangle free

## List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

Conjecture   If is the total graph of a multigraph, then .

Keywords: list coloring; Total coloring; total graphs

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

## Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

Question

Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?

## Splitting a digraph with minimum outdegree constraints ★★★

Author(s): Alon

Problem   Is there a minimum integer such that the vertices of any digraph with minimum outdegree can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least ?

Keywords:

## What are hyperfuncoids isomorphic to? ★★

Author(s): Porton

Let be an indexed family of sets.

Products are for .

Hyperfuncoids are filters on the lattice of all finite unions of products.

Problem   Is a bijection from hyperfuncoids to:
\item prestaroids on ; \item staroids on ; \item completary staroids on ?

If yes, is defining the inverse bijection? If not, characterize the image of the function defined on .

Consider also the variant of this problem with the set replaced with the set of complements of elements of the set .

Keywords: hyperfuncoids; multidimensional

## Shannon capacity of the seven-cycle ★★★

Author(s):

Problem   What is the Shannon capacity of ?

Keywords:

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

## Asymptotic Distribution of Form of Polyhedra ★★

Author(s): Rüdinger

Problem   Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?

Keywords: polyhedral graphs, distribution

## Frobenius number of four or more integers ★★

Author(s):

Problem   Find an explicit formula for Frobenius number of co-prime positive integers for .

Keywords:

## Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

Question   Are there graphs for which is arbitrarily large?

## Simplexity of the n-cube ★★★

Author(s):

Question   What is the minimum cardinality of a decomposition of the -cube into -simplices?

Keywords: cube; decomposition; simplex

## Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

Conjecture   Every prism over a -connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

## Cycles in Graphs of Large Chromatic Number ★★

Author(s): Brewster; McGuinness; Moore; Noel

Conjecture   If , then contains at least cycles of length .

Keywords: chromatic number; cycles

## Smooth 4-dimensional Poincare conjecture ★★★★

Author(s): Poincare; Smale; Stallings

Conjecture   If a -manifold has the homotopy type of the -sphere , is it diffeomorphic to ?

Keywords: 4-manifold; poincare; sphere

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

## Roller Coaster permutations ★★★

Author(s): Ahmed; Snevily

Let denote the set of all permutations of . Let and denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in . Let denote the set of subsequences of with length at least three. Let denote .

A permutation is called a Roller Coaster permutation if . Let be the set of all Roller Coaster permutations in .

Conjecture   For ,
\item If , then . \item If , then with .
Conjecture  (Odd Sum conjecture)   Given ,
\item If , then is odd for . \item If , then for all .

Keywords:

## Sticky Cantor sets ★★

Author(s):

Conjecture   Let be a Cantor set embedded in . Is there a self-homeomorphism of for every greater than so that moves every point by less than and does not intersect ? Such an embedded Cantor set for which no such exists (for some ) is called "sticky". For what dimensions do sticky Cantor sets exist?

Keywords: Cantor set

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

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

Author(s): Erdos; Hajnal

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

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

Author(s): Payan

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

Keywords:

## List colorings of edge-critical graphs ★★

Author(s): Mohar

Conjecture   Suppose that is a -edge-critical graph. Suppose that for each edge of , there is a list of colors. Then is -edge-colorable unless all lists are equal to each other.

Keywords: edge-coloring; list coloring

## Elementary symmetric of a sum of matrices ★★★

Author(s):

Problem

Given a Matrix , the -th elementary symmetric function of , namely , is defined as the sum of all -by- principal minors.

Find a closed expression for the -th elementary symmetric function of a sum of N -by- matrices, with by using partitions.

Keywords:

## Decomposing an eulerian graph into cycles with no two consecutives edges on a prescribed eulerian tour. ★★

Author(s): Sabidussi

Conjecture   Let be an eulerian graph of minimum degree , and let be an eulerian tour of . Then admits a decomposition into cycles none of which contains two consecutive edges of .

Keywords:

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

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

## Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

Conjecture   If is a -chromatic graph on at most vertices, then .

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

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

## Complexity of the H-factor problem. ★★

Author(s): Kühn; Osthus

An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .

Problem  Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?

Keywords:

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

## Sums of independent random variables with unbounded variance ★★

Author(s): Feige

Conjecture   If are independent random variables with , then

## Inscribed Square Problem ★★

Author(s): Toeplitz

Conjecture   Does every Jordan curve have 4 points on it which form the vertices of a square?

Keywords: simple closed curve; square

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

## Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

## End-Devouring Rays ★

Author(s): Georgakopoulos

Problem   Let be a graph, a countable end of , and an infinite set of pairwise disjoint -rays in . Prove that there is a set of pairwise disjoint -rays that devours such that the set of starting vertices of rays in equals the set of starting vertices of rays in .

Keywords: end; ray

## Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family of graphs is -bounded if there exists a function so that every satisfies .

Conjecture   For every fixed tree , the family of graphs with no induced subgraph isomorphic to is -bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

## Mixing Circular Colourings ★

Author(s): Brewster; Noel

Question   Is always rational?

Keywords: discrete homotopy; graph colourings; mixing

## Hilbert-Smith conjecture ★★

Author(s): David Hilbert; Paul A. Smith

Conjecture   Let be a locally compact topological group. If has a continuous faithful group action on an -manifold, then is a Lie group.

Keywords:

## Snevily's conjecture ★★★

Author(s): Snevily

Conjecture   Let be an abelian group of odd order and let satisfy . Then the elements of and may be ordered and so that the sums are pairwise distinct.

Keywords: addition table; latin square; transversal

## Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

Question   Is there a constant such that every -vertex -minor-free graph has at most cliques?

Keywords: clique; graph; minor

## Dirac's Conjecture ★★

Author(s): Dirac

Conjecture   For every set of points in the plane, not all collinear, there is a point in contained in at least lines determined by , for some constant .

Keywords: point set

## Primitive pythagorean n-tuple tree ★★

Author(s):

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

Keywords:

## Seymour's r-graph conjecture ★★★

Author(s): Seymour

An -graph is an -regular graph with the property that for every with odd size.

Conjecture   for every -graph .

Keywords: edge-coloring; r-graph

## Atomicity of the poset of completary multifuncoids ★★

Author(s): Porton

Conjecture   The poset of completary multifuncoids of the form is for every sets and :
\item atomic; \item atomistic.

See below for definition of all concepts and symbols used to in this conjecture.

Refer to this Web site for the theory which I now attempt to generalize.

Keywords: multifuncoid

## Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

Conjecture   Let be an integer and let be a minor minimal clutter with . Then either has a minor for some or has Lehman's property.

Keywords: clutter; covering; MFMC property; packing