# Random

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

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

## Partition of a cubic 3-connected graphs into paths of length 2. ★★

Author(s): Kelmans

Problem   Does every -connected cubic graph on vertices admit a partition into paths of length ?

Keywords:

## Ádám's Conjecture ★★★

Author(s): Ádám

Conjecture   Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

## Special Primes ★

Author(s): George BALAN

Conjecture   Let be a prime natural number. Find all primes , such that .

Keywords:

## r-regular graphs are not uniquely hamiltonian. ★★★

Author(s): Sheehan

Conjecture   If is a finite -regular graph, where , then is not uniquely hamiltonian.

Keywords: hamiltonian; regular; uniquely hamiltonian

## A homomorphism problem for flows ★★

Author(s): DeVos

Conjecture   Let be abelian groups and let and satisfy and . If there is a homomorphism from to , then every graph with a B-flow has a B'-flow.

Keywords: homomorphism; nowhere-zero flow; tension

## Real roots of the flow polynomial ★★

Author(s): Welsh

Conjecture   All real roots of nonzero flow polynomials are at most 4.

Keywords: flow polynomial; nowhere-zero flow

## P vs. NP ★★★★

Author(s): Cook; Levin

Problem   Is P = NP?

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

## Schanuel's Conjecture ★★★★

Author(s): Schanuel

Conjecture   Given any complex numbers which are linearly independent over the rational numbers , then the extension field has transcendence degree of at least over .

Keywords: algebraic independence

## Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set is -universal if every vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in , and all edges are (non-intersecting) straight line segments.

Question   Does there exist an -universal set of size ?

Keywords: geometric graph; planar graph; universal set

## Subgroup formed by elements of order dividing n ★★

Author(s): Frobenius

Conjecture

Suppose is a finite group, and is a positive integer dividing . Suppose that has exactly solutions to . Does it follow that these solutions form a subgroup of ?

Keywords: order, dividing

## Acyclic edge-colouring ★★

Author(s): Fiamcik

Conjecture   Every simple graph with maximum degree has a proper -edge-colouring so that every cycle contains edges of at least three distinct colours.

Keywords: edge-coloring

## Wide partition conjecture ★★

Author(s): Chow; Taylor

Conjecture   An integer partition is wide if and only if it is Latin.

Keywords:

## Weighted colouring of hexagonal graphs. ★★

Author(s): McDiarmid; Reed

Conjecture   There is an absolute constant such that for every hexagonal graph and vertex weighting ,

Keywords:

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

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

## Domination in cubic graphs ★★

Author(s): Reed

Problem   Does every 3-connected cubic graph satisfy ?

Keywords: cubic graph; domination

## Outer reloid of restricted funcoid ★★

Author(s): Porton

Question   for every filter objects and and a funcoid ?

Keywords: direct product of filters; outer reloid

## The Bollobás-Eldridge-Catlin Conjecture on graph packing ★★★

Author(s):

Conjecture  (BEC-conjecture)   If and are -vertex graphs and , then and pack.

Keywords: graph packing

## Unit vector flows ★★

Author(s): Jain

Conjecture   For every graph without a bridge, there is a flow .

Conjecture   There exists a map so that antipodal points of receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero.

Keywords: nowhere-zero flow

## Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

Conjecture   If are matroids on and for every partition of , then there exists with which is independent in every .

Keywords: independent set; matroid; partition

## Partition of Complete Geometric Graph into Plane Trees ★★

Author(s):

Conjecture   Every complete geometric graph with an even number of vertices has a partition of its edge set into plane (i.e. non-crossing) spanning trees.

## Consecutive non-orientable embedding obstructions ★★★

Author(s):

Conjecture   Is there a graph that is a minor-minimal obstruction for two non-orientable surfaces?

Keywords: minor; surface

## Criterion for boundedness of power series ★

Author(s): Rüdinger

Question   Give a necessary and sufficient criterion for the sequence so that the power series is bounded for all .

Keywords: boundedness; power series; real analysis

## Dividing up the unrestricted partitions ★★

Author(s): David S.; Newman

Begin with the generating function for unrestricted partitions:

(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...

Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.

Keywords: congruence properties; partition

## Bases of many weights ★★★

Author(s): Schrijver; Seymour

Let be an (additive) abelian group, and for every let .

Conjecture   Let be a matroid on , let be a map, put and . Then

Keywords: matroid; sumset; zero sum

## Durer's Conjecture ★★★

Author(s): Durer; Shephard

Conjecture   Every convex polytope has a non-overlapping edge unfolding.

Keywords: folding; polytope

## Closing Lemma for Diffeomorphism (Dynamical Systems) ★★★★

Author(s): Charles Pugh

Conjecture   Let and . Then for any neighborhood there is such that is periodic point of

There is an analogous conjecture for flows ( vector fields . In the case of diffeos this was proved by Charles Pugh for . In the case of Flows this has been solved by Sushei Hayahshy for . But in the two cases the problem is wide open for

Keywords: Dynamics , Pertubation

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

## Outward reloid of composition vs composition of outward reloids ★★

Author(s): Porton

Conjecture   For every composable funcoids and

Keywords: outward reloid

## Coloring random subgraphs ★★

Author(s): Bukh

If is a graph and , we let denote a subgraph of where each edge of appears in with independently with probability .

Problem   Does there exist a constant so that ?

Keywords: coloring; random graph

## Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

Conjecture   If are simple finite graphs, then .

Here is the tensor product (also called the direct or categorical product) of and .

## trace inequality ★★

Author(s):

Let be positive semidefinite, by Jensen's inequality, it is easy to see , whenever .

What about the , is it still valid?

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:

## Graceful Tree Conjecture ★★★

Author(s):

Conjecture   All trees are graceful

Keywords: combinatorics; graceful labeling

## Rota's unimodal conjecture ★★★

Author(s): Rota

Let be a matroid of rank , and for let be the number of closed sets of rank .

Conjecture   is unimodal.
Conjecture   is log-concave.

Keywords: flat; log-concave; matroid

## Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

Problem   Does every connected vertex-transitive graph have a Hamiltonian path?

Keywords: cycle; hamiltonian; path; vertex-transitive

## Combinatorial covering designs ★

Author(s): Gordon; Mills; Rödl; Schönheim

A covering design, or covering, is a family of -subsets, called blocks, chosen from a -set, such that each -subset is contained in at least one of the blocks. The number of blocks is the covering’s size, and the minimum size of such a covering is denoted by .

Problem   Find a closed form, recurrence, or better bounds for . Find a procedure for constructing minimal coverings.

Keywords: recreational mathematics

## Infinite distributivity of meet over join for a principal funcoid ★★

Author(s): Porton

Conjecture   for principal funcoid and a set of funcoids of appropriate sources and destinations.

Keywords: distributivity; principal funcoid

## What is the largest graph of positive curvature? ★

Author(s): DeVos; Mohar

Problem   What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?

Keywords: curvature; planar graph

## Beneš Conjecture ★★★

Author(s): Beneš

Given a partition of a finite set , stabilizer of , denoted , is the group formed by all permutations of preserving each block in .

Problem  ()   Find a sufficient condition for a sequence of partitions of to be universal, i.e. to yield the following decomposition of the symmetric group on : In particular, what about the sequence , where is a permutation of ?
Conjecture  (Beneš)   Let be a uniform partition of and be a permutation of such that . Suppose that the set is transitive, for some integer . Then

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:

## Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture   Every finite group is the Galois group of some finite algebraic extension of .

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

## Earth-Moon Problem ★★

Author(s): Ringel

Problem   What is the maximum number of colours needed to colour countries such that no two countries sharing a common border have the same colour in the case where each country consists of one region on earth and one region on the moon ?

Keywords:

## Odd incongruent covering systems ★★★

Author(s): Erdos; Selfridge

Conjecture   There is no covering system whose moduli are odd, distinct, and greater than 1.

Keywords: covering system

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