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

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

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

Keywords: independent set; matroid; partition

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

Author(s): Allagan

**Question**Given , what is the smallest integer such that ?

Keywords: complete bipartite graph; complete multipartite graph; list coloring

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

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.

Keywords: additive basis; representation function

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

Keywords: cage; Moore graph

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

Author(s): Lovasz

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?

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

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

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

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

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

Keywords: combinatorial geometry; independent set; orthogonality; projective plane; sphere

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

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

Keywords: graph drawing; obstacle number; planar graph; visibility graph

## Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

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

## Convex uniform 5-polytopes ★★

Author(s):

**Problem**Enumerate all convex uniform 5-polytopes.

Keywords:

## Bases of many weights ★★★

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

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