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

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

Author(s): Allagan

**Question**Given , what is the smallest integer such that ?

Keywords: complete bipartite graph; complete multipartite graph; list coloring

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

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

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

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

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

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

Keywords: antichain; extremal combinatorics; minimum saturation; saturation; Sperner system

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

Keywords: density problems; extremal combinatorics; homomorphism

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

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

Keywords:

## Mixing Circular Colourings ★

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

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

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

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

## Inequality for square summable complex series ★★

Author(s): Retkes

**Conjecture**For all the following inequality holds

Keywords: Inequality

## Even vs. odd latin squares ★★★

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 ?

Keywords: Algorithm construction; Exponential-time algorithm; Knapsack

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

Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm

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

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

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

Keywords: Essential singularity; Holomorphic functions; Picard's theorem; Residue of 1-form; Riemann surfaces

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

## Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

**Question**Is every Cayley graph Hamiltonian?

Keywords:

## The Borodin-Kostochka Conjecture ★★

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

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