# Random

## Faithful cycle covers ★★★

Author(s): Seymour

Conjecture   If is a graph, is admissable, and is even for every , then has a faithful cover.

Keywords: cover; cycle

## 3-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every 4-edge-connected graph has a nowhere-zero 3-flow.

Keywords: nowhere-zero flow

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

## Linial-Berge path partition duality ★★★

Author(s): Berge; Linial

Conjecture   The minimum -norm of a path partition on a directed graph is no more than the maximal size of an induced -colorable subgraph.

Keywords: coloring; directed path; partition

## Sidorenko's Conjecture ★★★

Author(s): Sidorenko

Conjecture   For any bipartite graph and graph , the number of homomorphisms from to is at least .

## Jorgensen's Conjecture ★★★

Author(s): Jorgensen

Conjecture   Every 6-connected graph without a minor is apex (planar plus one vertex).

Keywords: connectivity; minor

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

## Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation has a dominating set of size .

Keywords: coloring; domination; multigrid; planar graph; triangulation

## 3-Edge-Coloring Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Suppose with is a connected cubic graph admitting a -edge coloring. Then there is an edge such that the cubic graph homeomorphic to has a -edge coloring.

Keywords: 3-edge coloring; 4-flow; removable edge

## Grunbaum's Conjecture ★★★

Author(s): Grunbaum

Conjecture   If is a simple loopless triangulation of an orientable surface, then the dual of is 3-edge-colorable.

Keywords: coloring; surface

## Saturated $k$-Sperner Systems of Minimum Size ★★

Author(s): Morrison; Noel; Scott

Question   Does there exist a constant and a function such that if , then every saturated -Sperner system has cardinality at least ?

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

Author(s): Shaltiel; Umans

Problem   Prove unconditionally that .

Keywords: Arthur-Merlin; Hitting Sets; unconditional

## Convex Equipartitions with Extreme Perimeter ★★

Author(s): Nandakumar

To divide a given 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total perimeter of pieces is (1) maximized (2) minimized.

Remark: It appears maximizing the total perimeter is the easier problem.

Keywords: convex equipartition

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

## Every 4-connected toroidal graph has a Hamilton cycle ★★

Author(s): Grunbaum; Nash-Williams

Conjecture   Every 4-connected toroidal graph has a Hamilton cycle.

Keywords:

## Average diameter of a bounded cell of a simple arrangement ★★

Author(s): Deza; Terlaky; Zinchenko

Conjecture   The average diameter of a bounded cell of a simple arrangement defined by hyperplanes in dimension is not greater than .

Keywords: arrangement; diameter; polytope

## A conjecture about direct product of funcoids ★★

Author(s): Porton

Conjecture   Let and are monovalued, entirely defined funcoids with . Then there exists a pointfree funcoid such that (for every filter on ) (The join operation is taken on the lattice of filters with reversed order.)

A positive solution of this problem may open a way to prove that some funcoids-related categories are cartesian closed.

Keywords: category theory; general topology

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

## Antichains in the cycle continuous order ★★

Author(s): DeVos

If , are graphs, a function is called cycle-continuous if the pre-image of every element of the (binary) cycle space of is a member of the cycle space of .

Problem   Does there exist an infinite set of graphs so that there is no cycle continuous mapping between and whenever ?

Keywords: antichain; cycle; poset

## Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

Question   Are there graphs for which is arbitrarily large?

## The permanent conjecture ★★

Author(s): Kahn

Conjecture   If is an invertible matrix, then there is an submatrix of so that is nonzero.

Keywords: invertible; matrix; permanent

## 57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

Question   Does there exist a 57-regular graph with diameter 2 and girth 5?

Keywords: cage; Moore graph

## Twin prime conjecture ★★★★

Author(s):

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

Keywords: prime; twin prime

## Odd perfect numbers ★★★

Author(s): Ancient/folklore

Conjecture   There is no odd perfect number.

Keywords: perfect number

## Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

## The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

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

Keywords:

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

## Cyclic spanning subdigraph with small cyclomatic number ★★

Author(s): Bondy

Conjecture   Let be a digraph all of whose strong components are nontrivial. Then contains a cyclic spanning subdigraph with cyclomatic number at most .

Keywords:

## Perfect 2-error-correcting codes over arbitrary finite alphabets. ★★

Author(s):

Conjecture   Does there exist a nontrivial perfect 2-error-correcting code over any finite alphabet, other than the ternary Golay code?

Keywords: 2-error-correcting; code; existence; perfect; perfect code

## Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

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

Keywords: regular; subgraph

## Blatter-Specker Theorem for ternary relations ★★

Author(s): Makowsky

Let be a class of finite relational structures. We denote by the number of structures in over the labeled set . For any class definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every , the function is ultimately periodic modulo .

Question   Does the Blatter-Specker Theorem hold for ternary relations.

Keywords: Blatter-Specker Theorem; FMT00-Luminy

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

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

## Another conjecture about reloids and funcoids ★★

Author(s): Porton

Definition   for reloid .
Conjecture   for every funcoid .

Note: it is known that (see below mentioned online article).

Keywords:

## Choice Number of k-Chromatic Graphs of Bounded Order ★★

Author(s): Noel

Conjecture   If is a -chromatic graph on at most vertices, then .

## Snevily's conjecture ★★★

Author(s): Snevily

Conjecture   Let be an abelian group of odd order and let satisfy . Then the elements of and may be ordered and so that the sums are pairwise distinct.

Keywords: addition table; latin square; transversal

## Large induced forest in a planar graph. ★★

Author(s): Abertson; Berman

Conjecture   Every planar graph on verices has an induced forest with at least vertices.

Keywords:

## Complexity of the H-factor problem. ★★

Author(s): Kühn; Osthus

An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .

Problem  Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?

Keywords:

## Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem   Does there exist a graph with no subgraph isomorphic to which cannot be expressed as a union of triangle free graphs?

## A generalization of Vizing's Theorem? ★★

Author(s): Rosenfeld

Conjecture   Let be a simple -uniform hypergraph, and assume that every set of points is contained in at most edges. Then there exists an -edge-coloring so that any two edges which share vertices have distinct colors.

Keywords: edge-coloring; hypergraph; Vizing

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

Author(s): Morrison; Noel

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

## Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

Conjecture   Every convex polyhedron has a (nonoverlapping) edge unfolding.

Keywords: folding; nets

## Partial List Coloring ★★★

Author(s): Albertson; Grossman; Haas

Conjecture   Let be a simple graph with vertices and list chromatic number . Suppose that and each vertex of is assigned a list of colors. Then at least vertices of can be colored from these lists.

Keywords: list assignment; list coloring

## Large acyclic induced subdigraph in a planar oriented graph. ★★

Author(s): Harutyunyan

Conjecture   Every planar oriented graph has an acyclic induced subdigraph of order at least .

Keywords:

## Tarski's exponential function problem ★★

Author(s): Tarski

Conjecture   Is the theory of the real numbers with the exponential function decidable?

Keywords: Decidability

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

## Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph , we let be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and be the size of the smallest feedback edge set.

Conjecture  If is a simple digraph without directed cycles of length , then .

Keywords: acyclic; digraph; feedback edge set; triangle free

## Vertex Coloring of graph fractional powers ★★★

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.

## Fixed-point logic with counting ★★

Author(s): Blass

Question   Can either of the following be expressed in fixed-point logic plus counting:
\item Given a graph, does it have a perfect matching, i.e., a set of edges such that every vertex is incident to exactly one edge from ? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?

## Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let be a set of points in the plane. Two points and in are visible with respect to if the line segment between and contains no other point in .

Conjecture   For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.