# Random

## Chords of longest cycles ★★★

Author(s): Thomassen

Conjecture   If is a 3-connected graph, every longest cycle in has a chord.

Keywords: chord; connectivity; cycle

## Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

Conjecture   Every convex polyhedron has a (nonoverlapping) edge unfolding.

Keywords: folding; nets

## Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.

Question   Is it true that for every (sub)cubic graph , we have ?

Keywords: edge coloring; star coloring

## Upgrading a completary multifuncoid ★★

Author(s): Porton

Let be a set, be the set of filters on ordered reverse to set-theoretic inclusion, be the set of principal filters on , let be an index set. Consider the filtrator .

Conjecture   If is a completary multifuncoid of the form , then is a completary multifuncoid of the form .

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:

## 2-accessibility of primes ★★

Author(s): Landman; Robertson

Question   Is the set of prime numbers 2-accessible?

Keywords: monochromatic diffsequences; primes

## Generalized path-connectedness in proximity spaces ★★

Author(s): Porton

Let be a proximity.

A set is connected regarding iff .

Conjecture   The following statements are equivalent for every endofuncoid and a set :
\item is connected regarding . \item For every there exists a totally ordered set such that , , and for every partion of into two sets , such that , we have .

Keywords: connected; connectedness; proximity space

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

## 3-accessibility of Fibonacci numbers ★★

Author(s): Landman; Robertson

Question   Is the set of Fibonacci numbers 3-accessible?

## Decomposing an even tournament in directed paths. ★★★

Author(s): Alspach; Mason; Pullman

Conjecture   Every tournament on an even number of vertices can be decomposed into directed paths.

Keywords:

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

## Extremal problem on the number of tree endomorphism ★★

Author(s): Zhicong Lin

Conjecture   An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the vertices' trees, the star with vertices has the most endomorphisms, while the path with vertices has the least endomorphisms.

Keywords:

## Every metamonovalued reloid is monovalued ★★

Author(s): Porton

Conjecture   Every metamonovalued reloid is monovalued.

Keywords:

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

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

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

## Subdivision of a transitive tournament in digraphs with large outdegree. ★★

Conjecture   For all there is an integer  such that every digraph of minimum outdegree at least  contains a subdivision of a transitive tournament of order .

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

## Petersen coloring conjecture ★★★

Author(s): Jaeger

Conjecture   Let be a cubic graph with no bridge. Then there is a coloring of the edges of using the edges of the Petersen graph so that any three mutually adjacent edges of map to three mutually adjancent edges in the Petersen graph.

Keywords: cubic; edge-coloring; Petersen graph

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

## Linear-size circuits for stable $0,1 < 2$ sorting? ★★

Author(s): Regan

Problem   Can -size circuits compute the function on defined inductively by , , , and ?

Keywords: Circuits; sorting

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

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

## Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph is -degenerate if every subgraph of has a vertex of degree .

Conjecture   Every simple planar graph has a 5-coloring so that for , the union of any color classes induces a -degenerate graph.

Keywords: coloring; degenerate; planar

## Olson's Conjecture ★★

Author(s): Olson

Conjecture   If is a sequence of elements from a multiplicative group of order , then there exist so that .

Keywords: zero sum

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

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

## Jacobian Conjecture ★★★

Author(s): Keller

Conjecture   Let be a field of characteristic zero. A collection of polynomials in variables defines an automorphism of if and only if the Jacobian matrix is a nonzero constant.

Keywords: Affine Geometry; Automorphisms; Polynomials

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

## Graph product of multifuncoids ★★

Author(s): Porton

Conjecture   Let is a family of multifuncoids such that each is of the form where is an index set for every and is a set for every . Let every for some multifuncoid of the form regarding the filtrator . Let is a graph-composition of (regarding some partition and external set ). Then there exist a multifuncoid of the form such that regarding the filtrator .

Keywords: graph-product; multifuncoid

## Jaeger's modular orientation conjecture ★★★

Author(s): Jaeger

Conjecture   Every -edge-connected graph can be oriented so that (mod ) for every vertex .

Keywords: nowhere-zero flow; orientation

## Arc-disjoint out-branching and in-branching ★★

Author(s): Thomassen

Conjecture   There exists an integer such that every -arc-strong digraph with specified vertices and contains an out-branching rooted at and an in-branching rooted at which are arc-disjoint.

Keywords:

## Woodall's Conjecture ★★★

Author(s): Woodall

Conjecture   If is a directed graph with smallest directed cut of size , then has disjoint dijoins.

Keywords: digraph; packing

## Waring rank of determinant ★★

Author(s): Teitler

Question   What is the Waring rank of the determinant of a generic matrix?

For simplicity say we work over the complex numbers. The generic matrix is the matrix with entries for . Its determinant is a homogeneous form of degree , in variables. If is a homogeneous form of degree , a power sum expression for is an expression of the form , the (homogeneous) linear forms. The Waring rank of is the least number of terms in any power sum expression for . For example, the expression means that has Waring rank (it can't be less than , as ).

The generic determinant (or ) has Waring rank . The Waring rank of the generic determinant is at least and no more than , see for instance Lower bound for ranks of invariant forms, Example 4.1. The Waring rank of the permanent is also of interest. The comparison between the determinant and permanent is potentially relevant to Valiant's "VP versus VNP" problem.

Keywords: Waring rank, determinant

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

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

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

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

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

## $C^r$ Stability Conjecture ★★★★

Author(s): Palis; Smale

Conjecture   Any structurally stable diffeomorphism is hyperbolic.

Keywords: diffeomorphisms,; dynamical systems

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

## Dense rational distance sets in the plane ★★★

Author(s): Ulam

Problem   Does there exist a dense set so that all pairwise distances between points in are rational?

Keywords: integral distance; rational distance

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

## Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

Conjecture   It has been shown that a -outerplanar embedding for which is minimal can be found in polynomial time. Does a similar result hold for -edge-outerplanar graphs?

Keywords: planar graph; polynomial algorithm

## Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let denote the diagonal Ramsey number.

Conjecture   exists.
Problem   Determine the limit in the above conjecture (assuming it exists).

Keywords: Ramsey number

## Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture   Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?

Keywords: crossing number; surface

## What is the smallest number of disjoint spanning trees made a graph Hamiltonian ★★

Author(s): Goldengorin

We are given a complete simple undirected weighted graph and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.

Question 1. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.

Question 2. What is the smallest number of disjoint spanning trees creates a graph containing a shortest Hamiltonian path?

Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?

Keywords: 1-trees; cycle; Hamitonian path; spanning trees

## Arc-disjoint directed cycles in regular directed graphs ★★

Author(s): Alon; McDiarmid; Molloy

Conjecture   If is a -regular directed graph with no parallel arcs, then contains a collection of arc-disjoint directed cycles.

Keywords:

## Primitive pythagorean n-tuple tree ★★

Author(s):

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

Keywords:

## Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem   Does there exist a graph with no subgraph isomorphic to which cannot be expressed as a union of triangle free graphs?

## Stable set meeting all longest directed paths. ★★

Author(s): Laborde; Payan; Xuong N.H.

Conjecture   Every digraph has a stable set meeting all longest directed paths

Keywords: