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

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

**Problem**Is P = NP?

Keywords: Complexity Class; Computational Complexity; Millenium Problems; NP; P; polynomial algorithm

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

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

Keywords:

## Weighted colouring of hexagonal graphs. ★★

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

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

Keywords: complete geometric graph, edge colouring

## Consecutive non-orientable embedding obstructions ★★★

Author(s):

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

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

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

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

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

## Durer's Conjecture ★★★

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

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

Keywords: categorical product; coloring; homomorphism; tensor product

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

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

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

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

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