# Random

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

## 4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

Conjecture   Every -connected graph with a Hamilton cycle has a second Hamilton cycle.

Keywords:

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

## Erdős-Posa property for long directed cycles ★★

Author(s): Havet; Maia

Conjecture   Let be an integer. For every integer , there exists an integer such that for every digraph , either has a pairwise-disjoint directed cycles of length at least , or there exists a set of at most vertices such that has no directed cycles of length at least .

Keywords:

## List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

Conjecture   There is a constant such that the list chromatic number of any bipartite graph of maximum degree is at most .

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:

## Discrete Logarithm Problem ★★★

Author(s):

If is prime and , we write if satisfies . The problem of finding such an integer for a given (with ) is the Discrete Log Problem.

Conjecture   There does not exist a polynomial time algorithm to solve the Discrete Log Problem.

Keywords: discrete log; NP

## Dirac's Conjecture ★★

Author(s): Dirac

Conjecture   For every set of points in the plane, not all collinear, there is a point in contained in at least lines determined by , for some constant .

Keywords: point set

## Singmaster's conjecture ★★

Author(s): Singmaster

Conjecture   There is a finite upper bound on the multiplicities of entries in Pascal's triangle, other than the number .

The number appears once in Pascal's triangle, appears twice, appears three times, and appears times. There are infinite families of numbers known to appear times. The only number known to appear times is . It is not known whether any number appears more than times. The conjectured upper bound could be ; Singmaster thought it might be or . See Singmaster's conjecture.

Keywords: Pascal's triangle

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

## Turán Problem for $10$-Cycles in the Hypercube ★★

Author(s): Erdos

Problem   Bound the extremal number of in the hypercube.

Keywords: cycles; extremal combinatorics; hypercube

## Aharoni-Berger conjecture ★★★

Author(s): Aharoni; Berger

Conjecture   If are matroids on and for every partition of , then there exists with which is independent in every .

Keywords: independent set; matroid; partition

## 4-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Keywords: minor; nowhere-zero flow; Petersen graph

## List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given , what is the smallest integer such that ?

## The Erdos-Turan conjecture on additive bases ★★★★

Author(s): Erdos; Turan

Let . The representation function for is given by the rule . We call an additive basis if is never .

Conjecture   If is an additive basis, then is unbounded.

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

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

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

## Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

Problem   Does every connected vertex-transitive graph have a Hamiltonian path?

Keywords: cycle; hamiltonian; path; vertex-transitive

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

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

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

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

## Asymptotic Distribution of Form of Polyhedra ★★

Author(s): Rüdinger

Problem   Consider the set of all topologically inequivalent polyhedra with edges. Define a form parameter for a polyhedron as where is the number of vertices. What is the distribution of for ?

Keywords: polyhedral graphs, distribution

## Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family of graphs is -bounded if there exists a function so that every satisfies .

Conjecture   For every fixed tree , the family of graphs with no induced subgraph isomorphic to is -bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

## Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The fatness of a 4-polytope is defined to be where is the number of faces of of dimension .

Question   Does there exist a fixed constant so that every convex 4-polytope has fatness at most ?

Keywords: f-vector; polytope

## Imbalance conjecture ★★

Author(s): Kozerenko

Conjecture   Suppose that for all edges we have . Then is graphic.

Keywords: edge imbalance; graphic sequences

## Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.

Conjecture   If is the maximal degree of a graph , then is strongly -colorable.

Keywords: strong coloring

## Monochromatic empty triangles ★★★

Author(s):

If is a finite set of points which is 2-colored, an empty triangle is a set with so that the convex hull of is disjoint from . We say that is monochromatic if all points in are the same color.

Conjecture   There exists a fixed constant with the following property. If is a set of points in general position which is 2-colored, then it has monochromatic empty triangles.

Keywords: empty triangle; general position; ramsey theory

## Packing T-joins ★★

Author(s): DeVos

Conjecture   There exists a fixed constant (probably suffices) so that every graft with minimum -cut size at least contains a -join packing of size at least .

Keywords: packing; T-join

## Criterion for boundedness of power series ★

Author(s): Rüdinger

Question   Give a necessary and sufficient criterion for the sequence so that the power series is bounded for all .

Keywords: boundedness; power series; real analysis

## Hamiltonian cycles in line graphs ★★★

Author(s): Thomassen

Conjecture   Every 4-connected line graph is hamiltonian.

Keywords: hamiltonian; line graphs

## Acyclic edge-colouring ★★

Author(s): Fiamcik

Conjecture   Every simple graph with maximum degree has a proper -edge-colouring so that every cycle contains edges of at least three distinct colours.

Keywords: edge-coloring

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

## The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture   For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .

Keywords: induced subgraph

## trace inequality ★★

Author(s):

Let be positive semidefinite, by Jensen's inequality, it is easy to see , whenever .

What about the , is it still valid?

Keywords:

## The Double Cap Conjecture ★★

Author(s): Kalai

Conjecture   The largest measure of a Lebesgue measurable subset of the unit sphere of containing no pair of orthogonal vectors is attained by two open caps of geodesic radius around the north and south poles.

## Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

Conjecture   Let be an integer and let be a minor minimal clutter with . Then either has a minor for some or has Lehman's property.

Keywords: clutter; covering; MFMC property; packing

## Burnside problem ★★★★

Author(s): Burnside

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

Keywords:

## Finding k-edge-outerplanar graph embeddings ★★

Author(s): Bentz

Conjecture   It has been shown that a -outerplanar embedding for which is minimal can be found in polynomial time. Does a similar result hold for -edge-outerplanar graphs?

Keywords: planar graph; polynomial algorithm

## Odd-cycle transversal in triangle-free graphs ★★

Author(s): Erdos; Faudree; Pach; Spencer

Conjecture   If is a simple triangle-free graph, then there is a set of at most edges whose deletion destroys every odd cycle.

Keywords:

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

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

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

## Dense rational distance sets in the plane ★★★

Author(s): Ulam

Problem   Does there exist a dense set so that all pairwise distances between points in are rational?

Keywords: integral distance; rational distance

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

Keywords: prime; prime gap

## Obstacle number of planar graphs ★

Author(s): Alpert; Koch; Laison

Does there exist a planar graph with obstacle number greater than 1? Is there some such that every planar graph has obstacle number at most ?

## Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

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

Keywords: folding; nets

## Convex uniform 5-polytopes ★★

Author(s):

Problem   Enumerate all convex uniform 5-polytopes.

Keywords:

## Bases of many weights ★★★

Author(s): Schrijver; Seymour

Let be an (additive) abelian group, and for every let .

Conjecture   Let be a matroid on , let be a map, put and . Then

Keywords: matroid; sumset; zero sum