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

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

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 ?

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

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

Keywords: algorithm; Exponential-time algorithm; homomorphism

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

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

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

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

Keywords: additive basis; prime

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

Author(s): Hurtado

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

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

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

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

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

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

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

## Switching reconstruction of digraphs ★★

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

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

Keywords: