# Random

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

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

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

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

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

Author(s): Iradmusa

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

Author(s): Adyan

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

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

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

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

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

Keywords: invertable matrices, integer matrices

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

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

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

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