# Random

## Are different notions of the crossing number the same? ★★★

Author(s): Pach; Tóth

Problem   Does the following equality hold for every graph ?

The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the pairwise crossing number , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-crossing number

## Generalised Empty Hexagon Conjecture ★★

Author(s): Wood

Conjecture   For each there is an integer such that every set of at least points in the plane contains collinear points or an empty hexagon.

Keywords: empty hexagon

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

## Simplexity of the n-cube ★★★

Author(s):

Question   What is the minimum cardinality of a decomposition of the -cube into -simplices?

Keywords: cube; decomposition; simplex

## Complexity of square-root sum ★★

Author(s): Goemans

Question   What is the complexity of the following problem?

Given , determine whether or not

Keywords: semi-definite programming

## Geodesic cycles and Tutte's Theorem ★★

Author(s): Georgakopoulos; Sprüssel

Problem   If is a -connected finite graph, is there an assignment of lengths to the edges of , such that every -geodesic cycle is peripheral?

Keywords: cycle space; geodesic cycles; peripheral cycles

## A funcoid related to directed topological spaces ★★

Author(s): Porton

Conjecture   Let be the complete funcoid corresponding to the usual topology on extended real line . Let be the order on this set. Then is a complete funcoid.
Proposition   It is easy to prove that is the infinitely small right neighborhood filter of point .

If proved true, the conjecture then can be generalized to a wider class of posets.

Keywords:

## Unit vector flows ★★

Author(s): Jain

Conjecture   For every graph without a bridge, there is a flow .

Conjecture   There exists a map so that antipodal points of receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero.

Keywords: nowhere-zero flow

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

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

## Faithful cycle covers ★★★

Author(s): Seymour

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

Keywords: cover; cycle

## Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

Conjecture
\item If is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph of a locally finite graph is 4-connected, then is hamiltonian.

Keywords: hamiltonian; infinite graph; line graphs

## Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture   Every finite group is the Galois group of some finite algebraic extension of .

Keywords:

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

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

## Lovász Path Removal Conjecture ★★

Author(s): Lovasz

Conjecture   There is an integer-valued function such that if is any -connected graph and and are any two vertices of , then there exists an induced path with ends and such that is -connected.

Keywords:

## Covering a square with unit squares ★★

Author(s):

Conjecture   For any integer , it is impossible to cover a square of side greater than with unit squares.

Keywords:

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

## Partial List Coloring ★★★

Let be a simple graph, and for every list assignment let be the maximum number of vertices of which are colorable with respect to . Define , where the minimum is taken over all list assignments with for all .

Conjecture   [2] Let be a graph with list chromatic number and . Then

Keywords: list assignment; list coloring

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

## Growth of finitely presented groups ★★★

Problem   Does there exist a finitely presented group of intermediate growth?

Keywords: finitely presented; growth

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

## Real roots of the flow polynomial ★★

Author(s): Welsh

Conjecture   All real roots of nonzero flow polynomials are at most 4.

Keywords: flow polynomial; nowhere-zero flow

## Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

## Arc-disjoint directed cycles in regular directed graphs ★★

Author(s): Alon; McDiarmid; Molloy

Conjecture   If is a -regular directed graph with no parallel arcs, then contains a collection of arc-disjoint directed cycles.

Keywords:

## Primitive pythagorean n-tuple tree ★★

Author(s):

Conjecture   Find linear transformation construction of primitive pythagorean n-tuple tree!

Keywords:

## Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

Problem   Do there exist non-isomorphic trees which have the same chromatic symmetric function?

Keywords: chromatic polynomial; symmetric function; tree

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

## The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

Conjecture   Every bridgeless cubic graph has two perfect matchings , so that does not contain an odd edge-cut.

Keywords: cubic; nowhere-zero flow; perfect matching

## Jacobian Conjecture ★★★

Author(s): Keller

Conjecture   Let be a field of characteristic zero. A collection of polynomials in variables defines an automorphism of if and only if the Jacobian matrix is a nonzero constant.

Keywords: Affine Geometry; Automorphisms; Polynomials

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

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

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

Author(s): Shaltiel; Umans

Problem   Prove unconditionally that .

Keywords: Arthur-Merlin; Hitting Sets; unconditional

## Monochromatic reachability in arc-colored digraphs ★★★

Author(s): Sands; Sauer; Woodrow

Conjecture   For every , there exists an integer such that if is a digraph whose arcs are colored with colors, then has a set which is the union of stables sets so that every vertex has a monochromatic path to some vertex in .

Keywords:

## The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

Conjecture   If is a bridgeless cubic graph, then there exist 6 perfect matchings of with the property that every edge of is contained in exactly two of .

Keywords: cubic; perfect matching

## Edge-disjoint Hamilton cycles in highly strongly connected tournaments. ★★

Author(s): Thomassen

Conjecture   For every , there is an integer so that every strongly -connected tournament has edge-disjoint Hamilton cycles.

Keywords:

## Half-integral flow polynomial values ★★

Author(s): Mohar

Let be the flow polynomial of a graph . So for every positive integer , the value equals the number of nowhere-zero -flows in .

Conjecture   for every 2-edge-connected graph .

Keywords: nowhere-zero flow

## inverse of an integer matrix ★★

Author(s): Gregory

Question   I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all . Suppose X is an m-by-n integer matrix . Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.

## S(S(f)) = S(f) for reloids ★★

Author(s): Porton

Question   for every endo-reloid ?

Keywords: reloid

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

## The Two Color Conjecture ★★

Author(s): Neumann-Lara

Conjecture   If is an orientation of a simple planar graph, then there is a partition of into so that the graph induced by is acyclic for .

Keywords: acyclic; digraph; planar

## 3 is a primitive root modulo primes of the form 16 q^4 + 1, where q>3 is prime ★★

Author(s):

Conjecture   is a primitive root modulo for all primes , where is prime.

Keywords:

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

## Odd perfect numbers ★★★

Author(s): Ancient/folklore

Conjecture   There is no odd perfect number.

Keywords: perfect number

## Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem   Let be a perfect graph on vertices. Is it true that either or contains a complete bipartite subgraph with bipartition so that ?

Keywords: perfect graph

## Few subsequence sums in Z_n x Z_n ★★

Conjecture   For every , the sequence in consisting of copes of and copies of has the fewest number of distinct subsequence sums over all zero-free sequences from of length .

Keywords: subsequence sum; zero sum

## The robustness of the tensor product ★★★

Author(s): Ben-Sasson; Sudan

Problem   Given two codes , their Tensor Product is the code that consists of the matrices whose rows are codewords of and whose columns are codewords of . The product is said to be robust if whenever a matrix is far from , the rows (columns) of are far from (, respectively).

The problem is to give a characterization of the pairs whose tensor product is robust.

Keywords: codes; coding; locally testable; robustness

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

## Turán's problem for hypergraphs ★★

Author(s): Turan

Conjecture   Every simple -uniform hypergraph on vertices which contains no complete -uniform hypergraph on four vertices has at most hyperedges.
Conjecture   Every simple -uniform hypergraph on vertices which contains no complete -uniform hypergraph on five vertices has at most hyperedges.

Keywords:

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