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

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

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

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

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.

Keywords: Discrete Geometry; Geometric Ramsey Theory

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

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

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

Keywords: FMT12-LesHouches; MSO, alternation hierarchy; picture languages

## The Bermond-Thomassen Conjecture ★★

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

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

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

Keywords: knot theory, links, chessboard complex

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

Keywords: number of spanning trees, asymptotics

## Weak saturation of the cube in the clique ★

**Problem**

Determine .

Keywords: bootstrap percolation; hypercube; Weak saturation

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

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

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