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

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

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

**Question**Is the set of Fibonacci numbers 3-accessible?

Keywords: Fibonacci numbers; monochromatic diffsequences

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

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.

Keywords: invertable matrices, integer matrices

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

Author(s): Mader

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

Keywords: cage; Moore 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 ?

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

Keywords: combinatorial geometry; independent set; orthogonality; projective plane; sphere

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

Keywords: Disjoint paths; edge-connectivity; spanning trees

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

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

Keywords: additive basis; matrix

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

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

**Conjecture**Any structurally stable diffeomorphism is hyperbolic.

Keywords: diffeomorphisms,; dynamical systems

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

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

Keywords: forbidden subgraph; infinite graph; triangle free

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