# Random

## Packing T-joins ★★

Author(s): DeVos

Conjecture   There exists a fixed constant (probably suffices) so that every graft with minimum -cut size at least contains a -join packing of size at least .

Keywords: packing; T-join

## List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given , what is the smallest integer such that ?

## Seymour's r-graph conjecture ★★★

Author(s): Seymour

An -graph is an -regular graph with the property that for every with odd size.

Conjecture   for every -graph .

Keywords: edge-coloring; r-graph

## Bouchet's 6-flow conjecture ★★★

Author(s): Bouchet

Conjecture   Every bidirected graph with a nowhere-zero -flow for some , has a nowhere-zero -flow.

Keywords: bidirected graph; nowhere-zero flow

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

Author(s): Shaltiel; Umans

Problem   Prove unconditionally that .

Keywords: Arthur-Merlin; Hitting Sets; unconditional

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

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

## Splitting a digraph with minimum outdegree constraints ★★★

Author(s): Alon

Problem   Is there a minimum integer such that the vertices of any digraph with minimum outdegree can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least ?

Keywords:

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

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

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

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

## Upgrading a completary multifuncoid ★★

Author(s): Porton

Let be a set, be the set of filters on ordered reverse to set-theoretic inclusion, be the set of principal filters on , let be an index set. Consider the filtrator .

Conjecture   If is a completary multifuncoid of the form , then is a completary multifuncoid of the form .

See below for definition of all concepts and symbols used to in this conjecture.

Refer to this Web site for the theory which I now attempt to generalize.

Keywords:

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

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

## Waring rank of determinant ★★

Author(s): Teitler

Question   What is the Waring rank of the determinant of a generic matrix?

For simplicity say we work over the complex numbers. The generic matrix is the matrix with entries for . Its determinant is a homogeneous form of degree , in variables. If is a homogeneous form of degree , a power sum expression for is an expression of the form , the (homogeneous) linear forms. The Waring rank of is the least number of terms in any power sum expression for . For example, the expression means that has Waring rank (it can't be less than , as ).

The generic determinant (or ) has Waring rank . The Waring rank of the generic determinant is at least and no more than , see for instance Lower bound for ranks of invariant forms, Example 4.1. The Waring rank of the permanent is also of interest. The comparison between the determinant and permanent is potentially relevant to Valiant's "VP versus VNP" problem.

Keywords: Waring rank, determinant

## A conjecture on iterated circumcentres ★★

Author(s): Goddyn

Conjecture   Let be a sequence of points in with the property that for every , the points are distinct, lie on a unique sphere, and further, is the center of this sphere. If this sequence is periodic, must its period be ?

Keywords: periodic; plane geometry; sequence

## Sidorenko's Conjecture ★★★

Author(s): Sidorenko

Conjecture   For any bipartite graph and graph , the number of homomorphisms from to is at least .

## Lucas Numbers Modulo m ★★

Author(s):

Conjecture   The sequence {L(n) mod m}, where L(n) are the Lucas numbers, contains a complete residue system modulo m if and only if m is one of the following: 2, 4, 6, 7, 14, 3^k, k >=1.

Keywords: Lucas numbers

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

Author(s): Alspach; Rosenfeld

Conjecture   Every prism over a -connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

## Mixing Circular Colourings ★

Author(s): Brewster; Noel

Question   Is always rational?

Keywords: discrete homotopy; graph colourings; mixing

## Decomposition of completions of reloids ★★

Author(s): Porton

Conjecture   For composable reloids and it holds
\item if is a co-complete reloid; \item if is a complete reloid; \item ; \item ; \item .

Keywords: co-completion; completion; reloid

## Rendezvous on a line ★★★

Author(s): Alpern

Problem   Two players start at a distance of 2 on an (undirected) line (so, neither player knows the direction of the other) and both move at a maximum speed of 1. What is the infimum expected meeting time (first time when the players occupy the same point) which can be achieved assuming the two players must adopt the same strategy?

Keywords: game theory; optimization; rendezvous

## The Crossing Number of the Hypercube ★★

Author(s): Erdos; Guy

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

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

## Continous analogue of Hirsch conjecture ★★

Author(s): Deza; Terlaky; Zinchenko

Conjecture   The order of the largest total curvature of the primal central path over all polytopes defined by inequalities in dimension is .

Keywords: curvature; polytope

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

Author(s): Porton

Question   for every endo-reloid ?

Keywords: reloid

## Inequality for square summable complex series ★★

Author(s): Retkes

Conjecture   For all the following inequality holds

Keywords: Inequality

## Even vs. odd latin squares ★★★

Author(s): Alon; Tarsi

A latin square is even if the product of the signs of all of the row and column permutations is 1 and is odd otherwise.

Conjecture   For every positive even integer , the number of even latin squares of order and the number of odd latin squares of order are different.

Keywords: latin square

## Exponential Algorithms for Knapsack ★★

Author(s): Lipton

Conjecture

The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?

## Shannon capacity of the seven-cycle ★★★

Author(s):

Problem   What is the Shannon capacity of ?

Keywords:

## Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

Conjecture   Can the approximation ratio be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than -hardness?

## Circular coloring triangle-free subcubic planar graphs ★★

Author(s): Ghebleh; Zhu

Problem   Does every triangle-free planar graph of maximum degree three have circular chromatic number at most ?

Keywords: circular coloring; planar graph; triangle free

## Ádám's Conjecture ★★★

Author(s): Ádám

Conjecture   Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

## Petersen coloring conjecture ★★★

Author(s): Jaeger

Conjecture   Let be a cubic graph with no bridge. Then there is a coloring of the edges of using the edges of the Petersen graph so that any three mutually adjacent edges of map to three mutually adjancent edges in the Petersen graph.

Keywords: cubic; edge-coloring; Petersen graph

## Cores of strongly regular graphs ★★★

Author(s): Cameron; Kazanidis

Question   Does every strongly regular graph have either itself or a complete graph as a core?

Keywords: core; strongly regular

## Beneš Conjecture ★★★

Author(s): Beneš

Let be a non-empty finite set. Given a partition of , the stabilizer of , denoted , is the group formed by all permutations of preserving each block of .

Problem  ()   Find a sufficient condition for a sequence of partitions of to be complete, i.e. such that the product of their stabilizers is equal to the whole symmetric group on . In particular, what about completeness of the sequence , given a partition of and a permutation of ?
Conjecture  (Beneš)   Let be a uniform partition of and be a permutation of such that . Suppose that the set is transitive, for some integer . Then

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:

## The three 4-flows conjecture ★★

Author(s): DeVos

Conjecture   For every graph with no bridge, there exist three disjoint sets with so that has a nowhere-zero 4-flow for .

Keywords: nowhere-zero flow

## Something like Picard for 1-forms ★★

Author(s): Elsner

Conjecture   Let be the open unit disk in the complex plane and let be open sets such that . Suppose there are injective holomorphic functions such that for the differentials we have on any intersection . Then those differentials glue together to a meromorphic 1-form on .

## General position subsets ★★

Author(s): Gowers

Question   What is the least integer such that every set of at least points in the plane contains collinear points or a subset of points in general position (no three collinear)?

## Ryser's conjecture ★★★

Author(s): Ryser

Conjecture   Let be an -uniform -partite hypergraph. If is the maximum number of pairwise disjoint edges in , and is the size of the smallest set of vertices which meets every edge, then .

Keywords: hypergraph; matching; packing

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

## Jorgensen's Conjecture ★★★

Author(s): Jorgensen

Conjecture   Every 6-connected graph without a minor is apex (planar plus one vertex).

Keywords: connectivity; minor

## Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

Question   Is every Cayley graph Hamiltonian?

Keywords:

## The Borodin-Kostochka Conjecture ★★

Author(s): Borodin; Kostochka

Conjecture   Every graph with maximum degree has chromatic number at most .

Keywords:

## Birch & Swinnerton-Dyer conjecture ★★★★

Author(s):

Conjecture   Let be an elliptic curve over a number field . Then the order of the zeros of its -function, , at is the Mordell-Weil rank of .

Keywords:

## 2-colouring a graph without a monochromatic maximum clique ★★

Author(s): Hoang; McDiarmid

Conjecture   If is a non-empty graph containing no induced odd cycle of length at least , then there is a -vertex colouring of in which no maximum clique is monochromatic.

Keywords: maximum clique; Partitioning

## Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set has distinct subset sums if distinct subsets of have distinct sums.

Conjecture   There exists a fixed constant so that whenever has distinct subset sums.

Keywords: subset sum

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