# Random

## Unfriendly partitions ★★★

If is a graph, we say that a partition of is *unfriendly* if every vertex has at least as many neighbors in the other classes as in its own.

**Problem**Does every countably infinite graph have an unfriendly partition into two sets?

Keywords: coloring; infinite graph; partition

## Transversal achievement game on a square grid ★★

Author(s): Erickson

**Problem**Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an grid. The first player (if any) to occupy a set of cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?

Keywords: game

## Termination of the sixth Goodstein Sequence ★

Author(s): Graham

**Question**How many steps does it take the sixth Goodstein sequence to terminate?

Keywords: Goodstein Sequence

## Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set has *distinct subset sums* if distinct subsets of have distinct sums.

**Conjecture**There exists a fixed constant so that whenever has distinct subset sums.

Keywords: subset sum

## Every metamonovalued reloid is monovalued ★★

Author(s): Porton

**Conjecture**Every metamonovalued reloid is monovalued.

Keywords:

## Vertex Coloring of graph fractional powers ★★★

Author(s): Iradmusa

**Conjecture**Let be a graph and be a positive integer. The

*power of*, denoted by , is defined on the vertex set , by connecting any two distinct vertices and with distance at most . In other words, . Also

*subdivision of*, denoted by , is constructed by replacing each edge of with a path of length . Note that for , we have .

Now we can define the fractional power of a graph as follows:

Let be a graph and . The graph is defined by the power of the subdivision of . In other words .

*Conjecture.*Let be a connected graph with and be a positive integer greater than 1. Then for any positive integer , we have .

In [1], it was shown that this conjecture is true in some special cases.

Keywords: chromatic number, fractional power of graph, clique number

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

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

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

## Circular choosability of planar graphs ★

Author(s): Mohar

Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is

**Problem**What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs

## The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number of is the minimum number of crossings in all drawings of in the plane.

**Conjecture**

Keywords: complete graph; crossing number

## Matching cut and girth ★★

Author(s):

**Question**For every does there exists a such that every graph with average degree smaller than and girth at least has a matching-cut?

Keywords: matching cut, matching, cut

## Subgraph of large average degree and large girth. ★★

Author(s): Thomassen

**Conjecture**For all positive integers and , there exists an integer such that every graph of average degree at least contains a subgraph of average degree at least and girth greater than .

Keywords:

## Forcing a $K_6$-minor ★★

Author(s): Barát ; Joret; Wood

**Conjecture**Every graph with minimum degree at least 7 contains a -minor.

**Conjecture**Every 7-connected graph contains a -minor.

Keywords: connectivity; graph minors

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

## Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

**Conjecture**Every planar graph is acyclically 5-choosable.

Keywords:

## Seymour's self-minor conjecture ★★★

Author(s): Seymour

**Conjecture**Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

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

## Monochromatic reachability or rainbow triangles ★★★

Author(s): Sands; Sauer; Woodrow

In an edge-colored digraph, we say that a subgraph is *rainbow* if all its edges have distinct colors, and *monochromatic* if all its edges have the same color.

**Problem**Let be a tournament with edges colored from a set of three colors. Is it true that must have either a rainbow directed cycle of length three or a vertex so that every other vertex can be reached from by a monochromatic (directed) path?

Keywords: digraph; edge-coloring; tournament

## Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

**Conjecture**Every planar graph of girth has a homomorphism to .

Keywords: girth; homomorphism; planar graph

## Nearly spanning regular subgraphs ★★★

**Conjecture**For every and every positive integer , there exists so that every simple -regular graph with has a -regular subgraph with .

## Edge list coloring conjecture ★★★

Author(s):

**Conjecture**Let be a loopless multigraph. Then the edge chromatic number of equals the list edge chromatic number of .

Keywords:

## A diagram about funcoids and reloids ★★

Author(s): Porton

Define for posets with order :

- ;
- .

Note that the above is a generalization of monotone Galois connections (with and replaced with suprema and infima).

Then we have the following diagram:

What is at the node "other" in the diagram is unknown.

**Conjecture**"Other" is .

**Question**What repeated applying of and to "other" leads to? Particularly, does repeated applying and/or to the node "other" lead to finite or infinite sets?

Keywords: Galois connections

## Covering systems with big moduli ★★

**Problem**Does for every integer exist a covering system with all moduli distinct and at least equal to~?

Keywords: covering system

## Chromatic number of random lifts of complete graphs ★★

Author(s): Amit

**Question**Is the chromatic number of a random lift of concentrated on a single value?

Keywords: random lifts, coloring

## Are there only finite Fermat Primes? ★★★

Author(s):

**Conjecture**A Fermat prime is a Fermat number that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.

Keywords:

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

## Three-chromatic (0,2)-graphs ★★

Author(s): Payan

**Question**Are there any (0,2)-graphs with chromatic number exactly three?

Keywords:

## Burnside problem ★★★★

Author(s): Burnside

**Conjecture**If a group has generators and exponent , is it necessarily finite?

Keywords:

## Quartic rationally derived polynomials ★★★

Author(s): Buchholz; MacDougall

Call a polynomial *rationally derived* if all roots of and the nonzero derivatives of are rational.

**Conjecture**There does not exist a quartic rationally derived polynomial with four distinct roots.

Keywords: derivative; diophantine; elliptic; polynomial

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

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

## Colouring the square of a planar graph ★★

Author(s): Wegner

**Conjecture**Let be a planar graph of maximum degree . The chromatic number of its square is

- \item at most if , \item at most if , \item at most if .

Keywords:

## Which compact boundaryless 3-manifolds embed smoothly in the 4-sphere? ★★★

Author(s): Kirby

**Problem**Determine a computable set of invariants that allow one to determine, given a compact boundaryless 3-manifold, whether or not it embeds smoothly in the 4-sphere. This should include a constructive procedure to find an embedding if the manifold is embeddable.

Keywords: 3-manifold; 4-sphere; embedding

## Every metamonovalued funcoid is monovalued ★★

Author(s): Porton

**Conjecture**Every metamonovalued funcoid is monovalued.

The reverse is almost trivial: Every monovalued funcoid is metamonovalued.

Keywords: monovalued

## Polignac's Conjecture ★★★

Author(s): de Polignac

**Conjecture**Polignac's Conjecture: For any positive even number n, there are infinitely many prime gaps of size n. In other words: There are infinitely many cases of two consecutive prime numbers with difference n.

In particular, this implies:

**Conjecture**Twin Prime Conjecture: There are an infinite number of twin primes.

## Goldbach conjecture ★★★★

Author(s): Goldbach

**Conjecture**Every even integer greater than 2 is the sum of two primes.

Keywords: additive basis; prime

## Extension complexity of (convex) polygons ★★

Author(s):

The extension complexity of a polytope is the minimum number for which there exists a polytope with facets and an affine mapping with .

**Question**Does there exists, for infinitely many integers , a convex polygon on vertices whose extension complexity is ?

Keywords: polytope, projection, extension complexity, convex polygon

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

## Length of surreal product ★

Author(s): Gonshor

**Conjecture**Every surreal number has a unique sign expansion, i.e. function , where is some ordinal. This is the

*length*of given sign expansion and also the birthday of the corresponding surreal number. Let us denote this length of as .

It is easy to prove that

What about

?

Keywords: surreal numbers

## Realisation problem for the space of knots in the 3-sphere ★★

Author(s): Budney

**Problem**Given a link in , let the symmetry group of be denoted ie: isotopy classes of diffeomorphisms of which preserve , where the isotopies are also required to preserve .

Now let be a hyperbolic link. Assume has the further `Brunnian' property that there exists a component of such that is the unlink. Let be the subgroup of consisting of diffeomorphisms of which preserve together with its orientation, and which preserve the orientation of .

There is a representation given by restricting the diffeomorphism to the . It's known that is always a cyclic group. And is a signed symmetric group -- the wreath product of a symmetric group with .

Problem: What representations can be obtained?

Keywords: knot space; symmetry

## Seagull problem ★★★

Author(s): Seymour

**Conjecture**Every vertex graph with no independent set of size has a complete graph on vertices as a minor.

Keywords: coloring; complete graph; minor

## Algebraic independence of pi and e ★★★

Author(s):

**Conjecture**and are algebraically independent

Keywords: algebraic independence

## Melnikov's valency-variety problem ★

Author(s): Melnikov

**Problem**The valency-variety of a graph is the number of different degrees in . Is the chromatic number of any graph with at least two vertices greater than

Keywords:

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

## Edge Reconstruction Conjecture ★★★

Author(s): Harary

**Conjecture**

Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs

Keywords: reconstruction

## Cycle Double Covers Containing Predefined 2-Regular Subgraphs ★★★

Author(s): Arthur; Hoffmann-Ostenhof

**Conjecture**Let be a -connected cubic graph and let be a -regular subgraph such that is connected. Then has a cycle double cover which contains (i.e all cycles of ).

Keywords:

## Extremal $4$-Neighbour Bootstrap Percolation in the Hypercube ★★

**Problem**Determine the smallest percolating set for the -neighbour bootstrap process in the hypercube.

Keywords: bootstrap percolation; extremal combinatorics; hypercube; percolation

## Sub-atomic product of funcoids is a categorical product ★★

Author(s):

**Conjecture**In the category of continuous funcoids (defined similarly to the category of topological spaces) the following is a direct categorical product:

- \item Product morphism is defined similarly to the category of topological spaces. \item Product object is the sub-atomic product. \item Projections are sub-atomic projections.

See details, exact definitions, and attempted proofs here.

Keywords: