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

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

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

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

Keywords: algorithm; Exponential-time algorithm; homomorphism

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

Keywords: choosability; list coloring; on-line choosability

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

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

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.

Keywords: invertable matrices, integer matrices

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

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

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 .

Keywords: choosability; complete multipartite graph; list 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

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

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

Keywords: Inequality; Probability Theory; randomness in TCS

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

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

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

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