# Random

## The three 4-flows conjecture ★★

Author(s): DeVos

Conjecture   For every graph with no bridge, there exist three disjoint sets with so that has a nowhere-zero 4-flow for .

Keywords: nowhere-zero flow

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

## Davenport's constant ★★★

Author(s):

For a finite (additive) abelian group , the Davenport constant of , denoted , is the smallest integer so that every sequence of elements of with length has a nontrivial subsequence which sums to zero.

Conjecture

Keywords: Davenport constant; subsequence sum; zero sum

## 4-regular 4-chromatic graphs of high girth ★★

Author(s): Grunbaum

Problem   Do there exist 4-regular 4-chromatic graphs of arbitrarily high girth?

Keywords: coloring; girth

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

## Characterizing (aleph_0,aleph_1)-graphs ★★★

Call a graph an -graph if it has a bipartition so that every vertex in has degree and every vertex in has degree .

Problem   Characterize the -graphs.

## Even vs. odd latin squares ★★★

Author(s): Alon; Tarsi

A latin square is even if the product of the signs of all of the row and column permutations is 1 and is odd otherwise.

Conjecture   For every positive even integer , the number of even latin squares of order and the number of odd latin squares of order are different.

Keywords: latin square

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

## The Alon-Tarsi basis conjecture ★★

Author(s): Alon; Linial; Meshulam

Conjecture   If are invertible matrices with entries in for a prime , then there is a submatrix of so that is an AT-base.

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

## Universal Steiner triple systems ★★

Author(s): Grannell; Griggs; Knor; Skoviera

Problem   Which Steiner triple systems are universal?

Keywords: cubic graph; Steiner triple system

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

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

## Are there an infinite number of lucky primes? ★

Author(s): Lazarus: Gardiner: Metropolis; Ulam

Conjecture   If every second positive integer except 2 is remaining, then every third remaining integer except 3, then every fourth remaining integer etc. , an infinite number of the remaining integers are prime.

Keywords: lucky; prime; seive

## A gold-grabbing game ★★

Author(s): Rosenfeld

Setup Fix a tree and for every vertex a non-negative integer which we think of as the amount of gold at .

2-Player game Players alternate turns. On each turn, a player chooses a leaf vertex of the tree, takes the gold at this vertex, and then deletes . The game ends when the tree is empty, and the winner is the player who has accumulated the most gold.

Problem   Find optimal strategies for the players.

Keywords: game; tree

## 3-accessibility of Fibonacci numbers ★★

Author(s): Landman; Robertson

Question   Is the set of Fibonacci numbers 3-accessible?

## Unsolvability of word problem for 2-knot complements ★★★

Author(s): Gordon

Problem   Does there exist a smooth/PL embedding of in such that the fundamental group of the complement has an unsolvable word problem?

Keywords: 2-knot; Computational Complexity; knot theory

## Half-integral flow polynomial values ★★

Author(s): Mohar

Let be the flow polynomial of a graph . So for every positive integer , the value equals the number of nowhere-zero -flows in .

Conjecture   for every 2-edge-connected graph .

Keywords: nowhere-zero flow

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

## End-Devouring Rays ★

Author(s): Georgakopoulos

Problem   Let be a graph, a countable end of , and an infinite set of pairwise disjoint -rays in . Prove that there is a set of pairwise disjoint -rays that devours such that the set of starting vertices of rays in equals the set of starting vertices of rays in .

Keywords: end; ray

## Simplexity of the n-cube ★★★

Author(s):

Question   What is the minimum cardinality of a decomposition of the -cube into -simplices?

Keywords: cube; decomposition; simplex

## Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

Conjecture   If is a -connected planar graph, then has a Hamilton cycle.

Keywords:

## Alexa's Conjecture on Primality ★★

Author(s): Alexa

Definition   Let be the unique integer (with respect to a fixed ) such that

Conjecture   A natural number is a prime iff

Keywords: primality

## P vs. PSPACE ★★★

Author(s): Folklore

Problem   Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?

Keywords: P; PSPACE; separation; unconditional

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

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

## S(S(f)) = S(f) for reloids ★★

Author(s): Porton

Question   for every endo-reloid ?

Keywords: reloid

## Circular colouring the orthogonality graph ★★

Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr

Let denote the graph with vertex set consisting of all lines through the origin in and two vertices adjacent in if they are perpendicular.

Problem   Is ?

## Square achievement game on an n x n 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 four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

Keywords: game

## Circular flow number of regular class 1 graphs ★★

Author(s): Steffen

A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and . The circular flow number of is inf has a nowhere-zero -flow , and it is denoted by .

A graph with maximum vertex degree is a class 1 graph if its edge chromatic number is .

Conjecture   Let be an integer and a -regular graph. If is a class 1 graph, then .

## Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

Question   Is every proper vertex-minor closed class of graphs chi-bounded?

Keywords: chi-bounded; circle graph; coloring; vertex minor

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

## A sextic counterexample to Euler's sum of powers conjecture ★★

Author(s): Euler

Problem   Find six positive integers such that or prove that such integers do not exist.

Keywords:

## Negative association in uniform forests ★★

Author(s): Pemantle

Conjecture   Let be a finite graph, let , and let be the edge set of a forest chosen uniformly at random from all forests of . Then

Keywords: forest; negative association

## Cores of strongly regular graphs ★★★

Author(s): Cameron; Kazanidis

Question   Does every strongly regular graph have either itself or a complete graph as a core?

Keywords: core; strongly regular

## Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture   Let be a sequence of nonnegative integers which strictly decreases until .

Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus with crossings, but not with less crossings.

Keywords: crossing number; crossing sequence

## Arc-disjoint strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

Conjecture   There exists an ineteger so that every -arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs?

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

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

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

## Reed's omega, delta, and chi conjecture ★★★

Author(s): Reed

For a graph , we define to be the maximum degree, to be the size of the largest clique subgraph, and to be the chromatic number of .

Conjecture   for every graph .

Keywords: coloring

## Twin prime conjecture ★★★★

Author(s):

Conjecture   There exist infinitely many positive integers so that both and are prime.

Keywords: prime; twin prime

## The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

Conjecture   Every graph with maximum degree has chromatic number at most .

Keywords:

## Covering systems with big moduli ★★

Author(s): Erdos; Selfridge

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

Keywords: covering system

## Strict inequalities for products of filters ★

Author(s): Porton

Conjecture   for some filter objects , . Particularly, is this formula true for ?

A weaker conjecture:

Conjecture   for some filter objects , .

Keywords: filter products

## Circular flow numbers of $r$-graphs ★★

Author(s): Steffen

A nowhere-zero -flow on is an orientation of together with a function from the edge set of into the real numbers such that , for all , and .

A -regular graph is a -graph if for every with odd.

Conjecture   Let be an integer. If is a -graph, then .

Keywords: flow conjectures; nowhere-zero flows

## Unconditional derandomization of Arthur-Merlin games ★★★

Author(s): Shaltiel; Umans

Problem   Prove unconditionally that .

Keywords: Arthur-Merlin; Hitting Sets; unconditional

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

## Weak pentagon problem ★★

Author(s): Samal

Conjecture   If is a cubic graph not containing a triangle, then it is possible to color the edges of by five colors, so that the complement of every color class is a bipartite graph.

## Generalised Empty Hexagon Conjecture ★★

Author(s): Wood

Conjecture   For each there is an integer such that every set of at least points in the plane contains collinear points or an empty hexagon.

Keywords: empty hexagon