# Random

## Edge-antipodal colorings of cubes ★★

Author(s): Norine

We let denote the -dimensional cube graph. A map is called edge-antipodal if whenever are antipodal edges.

Conjecture   If and is edge-antipodal, then there exist a pair of antipodal vertices which are joined by a monochromatic path.

Keywords: antipodal; cube; edge-coloring

## The permanent conjecture ★★

Author(s): Kahn

Conjecture   If is an invertible matrix, then there is an submatrix of so that is nonzero.

Keywords: invertible; matrix; permanent

## Crossing sequences ★★

Author(s): Archdeacon; Bonnington; Siran

Conjecture   Let be a sequence of nonnegative integers which strictly decreases until .

Then there exists a graph that be drawn on a surface with orientable (nonorientable, resp.) genus with crossings, but not with less crossings.

Keywords: crossing number; crossing sequence

## Strong matchings and covers ★★★

Author(s): Aharoni

Let be a hypergraph. A strongly maximal matching is a matching so that for every matching . A strongly minimal cover is a (vertex) cover so that for every cover .

Conjecture   If is a (possibly infinite) hypergraph in which all edges have size for some integer , then has a strongly maximal matching and a strongly minimal cover.

Keywords: cover; infinite graph; matching

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

## Algebraic independence of pi and e ★★★

Author(s):

Conjecture   and are algebraically independent

Keywords: algebraic independence

## Bases of many weights ★★★

Author(s): Schrijver; Seymour

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

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

Keywords: matroid; sumset; zero sum

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

## Big Line or Big Clique in Planar Point Sets ★★

Author(s): Kara; Por; Wood

Let be a set of points in the plane. Two points and in are visible with respect to if the line segment between and contains no other point in .

Conjecture   For all integers there is an integer such that every set of at least points in the plane contains at least collinear points or pairwise visible points.

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

## Erdős–Faber–Lovász conjecture ★★★

Author(s): Erdos; Faber; Lovasz

Conjecture   If is a simple graph which is the union of pairwise edge-disjoint complete graphs, each of which has vertices, then the chromatic number of is .

Keywords: chromatic number

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

## Random stable roommates ★★

Author(s): Mertens

Conjecture   The probability that a random instance of the stable roommates problem on people admits a solution is .

Keywords: stable marriage; stable roommates

## Convex Equipartitions with Extreme Perimeter ★★

Author(s): Nandakumar

To divide a given 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total perimeter of pieces is (1) maximized (2) minimized.

Remark: It appears maximizing the total perimeter is the easier problem.

Keywords: convex equipartition

## MSO alternation hierarchy over pictures ★★

Author(s): Grandjean

Question   Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related.

## The Bermond-Thomassen Conjecture ★★

Author(s): Bermond; Thomassen

Conjecture   For every positive integer , every digraph with minimum out-degree at least contains disjoint cycles.

Keywords: cycles

## A nowhere-zero point in a linear mapping ★★★

Author(s): Jaeger

Conjecture   If is a finite field with at least 4 elements and is an invertible matrix with entries in , then there are column vectors which have no coordinates equal to zero such that .

Keywords: invertible; nowhere-zero flow

## 5-flow conjecture ★★★★

Author(s): Tutte

Conjecture   Every bridgeless graph has a nowhere-zero 5-flow.

Keywords: cubic; nowhere-zero flow

## Number of Cliques in Minor-Closed Classes ★★

Author(s): Wood

Question   Is there a constant such that every -vertex -minor-free graph has at most cliques?

Keywords: clique; graph; minor

## The 4x5 chessboard complex is the complement of a link, which link? ★★

Author(s): David Eppstein

Problem   Ian Agol and Matthias Goerner observed that the 4x5 chessboard complex is the complement of many distinct links in the 3-sphere. Their observation is non-constructive, as it uses the resolution of the Poincare Conjecture. Find specific links that have the 4x5 chessboard complex as their complement.

## Minimal graphs with a prescribed number of spanning trees ★★

Author(s): Azarija; Skrekovski

Conjecture   Let be an integer and let denote the least integer such that there exists a simple graph on vertices having precisely spanning trees. Then

## Weak saturation of the cube in the clique ★

Author(s): Morrison; Noel

Problem

Determine .

## Funcoidal products inside an inward reloid ★★

Author(s): Porton

Conjecture   (solved) If then for every funcoid and atomic f.o. and on the source and destination of correspondingly.

A stronger conjecture:

Conjecture   If then for every funcoid and , .

Keywords: inward reloid

## Partitioning the Projective Plane ★★

Author(s): Noel

Throughout this post, by projective plane we mean the set of all lines through the origin in .

Definition   Say that a subset of the projective plane is octahedral if all lines in pass through the closure of two opposite faces of a regular octahedron centered at the origin.
Definition   Say that a subset of the projective plane is weakly octahedral if every set such that is octahedral.
Conjecture   Suppose that the projective plane can be partitioned into four sets, say and such that each set is weakly octahedral. Then each is octahedral.

Keywords: Partitioning; projective plane

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

## Jaeger's modular orientation conjecture ★★★

Author(s): Jaeger

Conjecture   Every -edge-connected graph can be oriented so that (mod ) for every vertex .

Keywords: nowhere-zero flow; orientation

## Twin prime conjecture ★★★★

Author(s):

Conjecture   There exist infinitely many positive integers so that both and are prime.

Keywords: prime; twin prime

## Rainbow AP(4) in an almost equinumerous coloring ★★

Author(s): Conlon

Problem   Do 4-colorings of , for a large prime, always contain a rainbow if each of the color classes is of size of either or ?

Keywords: arithmetic progression; rainbow

## ¿Are critical k-forests tight? ★★

Author(s): Strausz

Conjecture

Let be a -uniform hypergraph. If is a critical -forest, then it is a -tree.

Keywords: heterochromatic number

## Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

Conjecture   Is it possible to color edges of the complete graph using colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?

Equivalently: is the star chromatic index of linear in ?

Keywords: complete graph; edge coloring; star coloring

## Arc-disjoint strongly connected spanning subdigraphs ★★

Author(s): Bang-Jensen; Yeo

Conjecture   There exists an ineteger so that every -arc-connected digraph contains a pair of arc-disjoint strongly connected spanning subdigraphs?

Keywords:

## Fundamental group torsion for subsets of Euclidean 3-space ★★

Author(s): Ancient/folklore

Problem   Does there exist a subset of such that its fundamental group has an element of finite order?

Keywords: subsets of euclidean space; torsion

## One-way functions exist ★★★★

Author(s):

Conjecture   One-way functions exist.

Keywords: one way function

## Forcing a $K_6$-minor ★★

Author(s): Barát ; Joret; Wood

Conjecture   Every graph with minimum degree at least 7 contains a -minor.
Conjecture   Every 7-connected graph contains a -minor.

Keywords: connectivity; graph minors

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

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

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

## Strict inequalities for products of filters ★

Author(s): Porton

Conjecture   for some filter objects , . Particularly, is this formula true for ?

A weaker conjecture:

Conjecture   for some filter objects , .

Keywords: filter products

## Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

Conjecture   Every planar graph is acyclically 5-choosable.

Keywords:

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

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

## Olson's Conjecture ★★

Author(s): Olson

Conjecture   If is a sequence of elements from a multiplicative group of order , then there exist so that .

Keywords: zero sum

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

## Laplacian Degrees of a Graph ★★

Author(s): Guo

Conjecture   If is a connected graph on vertices, then for .

Keywords: degree sequence; Laplacian matrix

## Graph product of multifuncoids ★★

Author(s): Porton

Conjecture   Let is a family of multifuncoids such that each is of the form where is an index set for every and is a set for every . Let every for some multifuncoid of the form regarding the filtrator . Let is a graph-composition of (regarding some partition and external set ). Then there exist a multifuncoid of the form such that regarding the filtrator .

Keywords: graph-product; multifuncoid

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

## Inequality of the means ★★★

Author(s):

Question   Is is possible to pack rectangular -dimensional boxes each of which has side lengths inside an -dimensional cube with side length ?

Keywords: arithmetic mean; geometric mean; Inequality; packing

## Coloring the Odd Distance Graph ★★★

Author(s): Rosenfeld

The Odd Distance Graph, denoted , is the graph with vertex set and two points adjacent if the distance between them is an odd integer.

Question   Is ?

Keywords: coloring; geometric graph; odd distance

## $C^r$ Stability Conjecture ★★★★

Author(s): Palis; Smale

Conjecture   Any structurally stable diffeomorphism is hyperbolic.

Keywords: diffeomorphisms,; dynamical systems

## Infinite distributivity of meet over join for a principal funcoid ★★

Author(s): Porton

Conjecture   for principal funcoid and a set of funcoids of appropriate sources and destinations.

Keywords: distributivity; principal funcoid