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

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

Keywords: binary tree; infinite graph; normal spanning tree; set theory

## Even vs. odd latin squares ★★★

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.

Keywords: additive basis; matrix

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

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

## 3-accessibility of Fibonacci numbers ★★

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

Keywords: Fibonacci numbers; monochromatic diffsequences

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

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

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

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

Keywords: circular coloring; geometric graph; orthogonality

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

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

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

Keywords:

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

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

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.

Keywords: Clebsch graph; cut-continuous mapping; edge-coloring; homomorphism; pentagon

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