# Random

## Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let denote the diagonal Ramsey number.

Conjecture   exists.
Problem   Determine the limit in the above conjecture (assuming it exists).

Keywords: Ramsey number

## What are hyperfuncoids isomorphic to? ★★

Author(s): Porton

Let be an indexed family of sets.

Products are for .

Hyperfuncoids are filters on the lattice of all finite unions of products.

Problem   Is a bijection from hyperfuncoids to:
\item prestaroids on ; \item staroids on ; \item completary staroids on ?

If yes, is defining the inverse bijection? If not, characterize the image of the function defined on .

Consider also the variant of this problem with the set replaced with the set of complements of elements of the set .

Keywords: hyperfuncoids; multidimensional

## Matching cut and girth ★★

Author(s):

Question   For every does there exists a such that every graph with average degree smaller than and girth at least has a matching-cut?

Keywords: matching cut, matching, cut

## Signing a graph to have small magnitude eigenvalues ★★

Author(s): Bilu; Linial

Conjecture   If is the adjacency matrix of a -regular graph, then there is a symmetric signing of (i.e. replace some entries by ) so that the resulting matrix has all eigenvalues of magnitude at most .

Keywords: eigenvalue; expander; Ramanujan graph; signed graph; signing

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

## Strong edge colouring conjecture ★★

Author(s): Erdos; Nesetril

A strong edge-colouring of a graph is a edge-colouring in which every colour class is an induced matching; that is, any two vertices belonging to distinct edges with the same colour are not adjacent. The strong chromatic index is the minimum number of colours in a strong edge-colouring of .

Conjecture

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

## Cores of Cayley graphs ★★★★★

Author(s): Samal

Conjecture   Let be an abelian group. Is the core of a Cayley graph (on some power of ) a Cayley graph (on some power of )?

Keywords: Cayley graph; core

## Chromatic Number of Common Graphs ★★

Author(s): Hatami; Hladký; Kráľ; Norine; Razborov

Question   Do common graphs have bounded chromatic number?

Keywords: common graph

## Linear-size circuits for stable $0,1 < 2$ sorting? ★★

Author(s): Regan

Problem   Can -size circuits compute the function on defined inductively by , , , and ?

Keywords: Circuits; sorting

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

Keywords: lucky; prime; seive

## Rank vs. Genus ★★★

Author(s): Johnson

Question   Is there a hyperbolic 3-manifold whose fundamental group rank is strictly less than its Heegaard genus? How much can the two differ by?

Keywords:

## Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

Question

Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?

## Three-chromatic (0,2)-graphs ★★

Author(s): Payan

Question   Are there any (0,2)-graphs with chromatic number exactly three?

Keywords:

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

## The Hodge Conjecture ★★★★

Author(s): Hodge

Conjecture   Let be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of .

Keywords: Hodge Theory; Millenium Problems

## Cube-Simplex conjecture ★★★

Author(s): Kalai

Conjecture   For every positive integer , there exists an integer so that every polytope of dimension has a -dimensional face which is either a simplex or is combinatorially isomorphic to a -dimensional cube.

Keywords: cube; facet; polytope; simplex

## Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

Author(s): Alspach; Rosenfeld

Conjecture   Every prism over a -connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

## Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

An directed graph is -diregular if every vertex has indegree and outdegree at least .

Conjecture   For , every -diregular oriented graph on at most vertices has a Hamilton cycle.

Keywords:

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

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

## The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number of is the minimum number of crossings in all drawings of in the plane.

Conjecture

Keywords: complete bipartite graph; crossing number

## What is the smallest number of disjoint spanning trees made a graph Hamiltonian ★★

Author(s): Goldengorin

We are given a complete simple undirected weighted graph and its first arbitrary shortest spanning tree . We define the next graph and find on the second arbitrary shortest spanning tree . We continue similarly by finding on , etc. Let k be the smallest number of disjoint shortest spanning trees as defined above and let be the graph obtained as union of all disjoint trees.

Question 1. What is the smallest number of disjoint spanning trees creates a graph containing a Hamiltonian path.

Question 2. What is the smallest number of disjoint spanning trees creates a graph containing a shortest Hamiltonian path?

Questions 3 and 4. Replace in questions 1 and 2 a shortest spanning tree by a 1-tree. What is the smallest number of disjoint 1-trees creates a Hamiltonian graph? What is the smallest number of disjoint 1-trees creates a graph containing a shortest Hamiltonian cycle?

Keywords: 1-trees; cycle; Hamitonian path; spanning trees

## Goldbach conjecture ★★★★

Author(s): Goldbach

Conjecture   Every even integer greater than 2 is the sum of two primes.

## Elementary symmetric of a sum of matrices ★★★

Author(s):

Problem

Given a Matrix , the -th elementary symmetric function of , namely , is defined as the sum of all -by- principal minors.

Find a closed expression for the -th elementary symmetric function of a sum of N -by- matrices, with by using partitions.

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

## The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number of is the minimum number of crossings in all drawings of in the plane.

Conjecture

Keywords: complete graph; crossing number

## Edge-Colouring Geometric Complete Graphs ★★

Question   What is the minimum number of colours such that every complete geometric graph on vertices has an edge colouring such that:
\item[Variant A] crossing edges get distinct colours, \item[Variant B] disjoint edges get distinct colours, \item[Variant C] non-disjoint edges get distinct colours, \item[Variant D] non-crossing edges get distinct colours.

Keywords: geometric complete graph, colouring

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

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

## Coloring the union of degenerate graphs ★★

Author(s): Tarsi

Conjecture   The union of a -degenerate graph (a forest) and a -degenerate graph is -colourable.

Keywords:

## The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

The crossing number of is the minimum number of crossings in all drawings of in the plane.

The -dimensional (hyper)cube is the graph whose vertices are all binary sequences of length , and two of the sequences are adjacent in if they differ in precisely one coordinate.

Conjecture

Keywords: crossing number; hypercube

## Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture   A triangle-free graph with maximum degree has chromatic number at most .

Keywords: chromatic number; girth; maximum degree; triangle free

## Odd perfect numbers ★★★

Author(s): Ancient/folklore

Conjecture   There is no odd perfect number.

Keywords: perfect number

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

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

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

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

Author(s): Allagan

Question   Given , what is the smallest integer such that ?

## Good Edge Labelings ★★

Author(s): Araújo; Cohen; Giroire; Havet

Question   What is the maximum edge density of a graph which has a good edge labeling?

We say that a graph is good-edge-labeling critical, if it has no good edge labeling, but every proper subgraph has a good edge labeling.

Conjecture   For every , there is only a finite number of good-edge-labeling critical graphs with average degree less than .

Keywords: good edge labeling, edge labeling

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

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

## Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.

Question   Is it true that for every (sub)cubic graph , we have ?

Keywords: edge coloring; star coloring

## The Bollobás-Eldridge-Catlin Conjecture on graph packing ★★★

Author(s):

Conjecture  (BEC-conjecture)   If and are -vertex graphs and , then and pack.

Keywords: graph packing

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

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

## Switching reconstruction of digraphs ★★

Author(s): Bondy; Mercier

Question   Are there any switching-nonreconstructible digraphs on twelve or more vertices?

Keywords:

## Odd cycles and low oddness ★★

Author(s):

Conjecture   If in a bridgeless cubic graph the cycles of any -factor are odd, then , where denotes the oddness of the graph , that is, the minimum number of odd cycles in a -factor of .

Keywords:

## Edge Reconstruction Conjecture ★★★

Author(s): Harary

Conjecture

Every simple graph with at least 4 edges is reconstructible from it's edge deleted subgraphs

Keywords: reconstruction

## Hoàng-Reed Conjecture ★★★

Author(s): Hoang; Reed

Conjecture   Every digraph in which each vertex has outdegree at least contains directed cycles such that meets in at most one vertex, .

Keywords: