# Random

## Faithful cycle covers ★★★

Author(s): Seymour

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

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

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

Keywords: density problems; extremal combinatorics; homomorphism

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

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

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

Keywords: antichain; extremal combinatorics; minimum saturation; saturation; Sperner system

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

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 ?

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

Author(s): Zhu

**Question**Are there graphs for which is arbitrarily large?

Keywords: choosability; list coloring; on-line choosability

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

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

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

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

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

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

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

Keywords: choosability; complete multipartite graph; list coloring

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

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

Keywords:

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

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

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

Keywords: forbidden subgraph; infinite graph; triangle free

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

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

Keywords: bootstrap percolation; extremal combinatorics; hypercube; percolation

## Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

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

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

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

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

Keywords: Capturing PTime; counting quantifiers; Fixed-point logic; FMT03-Bedlewo

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

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.

Keywords: Discrete Geometry; Geometric Ramsey Theory