# Random

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

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

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

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

## Large acyclic induced subdigraph in a planar oriented graph. ★★

Author(s): Harutyunyan

Conjecture   Every planar oriented graph has an acyclic induced subdigraph of order at least .

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

## Magic square of squares ★★

Author(s): LaBar

Question   Does there exist a magic square composed of distinct perfect squares?

Keywords:

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

## Covering powers of cycles with equivalence subgraphs ★

Author(s):

Conjecture   Given and , the graph has equivalence covering number .

Keywords:

## Strong colorability ★★★

Author(s): Aharoni; Alon; Haxell

Let be a positive integer. We say that a graph is strongly -colorable if for every partition of the vertices to sets of size at most there is a proper -coloring of in which the vertices in each set of the partition have distinct colors.

Conjecture   If is the maximal degree of a graph , then is strongly -colorable.

Keywords: strong coloring

## A diagram about funcoids and reloids ★★

Author(s): Porton

Define for posets with order :

1. ;
2. .

Note that the above is a generalization of monotone Galois connections (with and replaced with suprema and infima).

Then we have the following diagram:

What is at the node "other" in the diagram is unknown.

Conjecture   "Other" is .
Question   What repeated applying of and to "other" leads to? Particularly, does repeated applying and/or to the node "other" lead to finite or infinite sets?

Keywords: Galois connections

## Matching cut and girth ★★

Author(s):

Question   For every does there exists a such that every graph with average degree smaller than and girth at least has a matching-cut?

Keywords: matching cut, matching, cut

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

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

## Saturation in the Hypercube ★★

Author(s): Morrison; Noel; Scott

Question   What is the saturation number of cycles of length in the -dimensional hypercube?

Keywords: cycles; hypercube; minimum saturation; saturation

## trace inequality ★★

Author(s):

Let be positive semidefinite, by Jensen's inequality, it is easy to see , whenever .

What about the , is it still valid?

Keywords:

## Negative association in uniform forests ★★

Author(s): Pemantle

Conjecture   Let be a finite graph, let , and let be the edge set of a forest chosen uniformly at random from all forests of . Then

Keywords: forest; negative association

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

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

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

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

Conjecture   Every planar graph is acyclically 5-choosable.

Keywords:

## Roller Coaster permutations ★★★

Author(s): Ahmed; Snevily

Let denote the set of all permutations of . Let and denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in . Let denote the set of subsequences of with length at least three. Let denote .

A permutation is called a Roller Coaster permutation if . Let be the set of all Roller Coaster permutations in .

Conjecture   For ,
\item If , then . \item If , then with .
Conjecture  (Odd Sum conjecture)   Given ,
\item If , then is odd for . \item If , then for all .

Keywords:

## Exact colorings of graphs ★★

Author(s): Erickson

Conjecture   For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .

Keywords: graph coloring; ramsey theory

## Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.

Question   Is it true that for every (sub)cubic graph , we have ?

Keywords: edge coloring; star coloring

## Fixed-point logic with counting ★★

Author(s): Blass

Question   Can either of the following be expressed in fixed-point logic plus counting:
\item Given a graph, does it have a perfect matching, i.e., a set of edges such that every vertex is incident to exactly one edge from ? \item Given a square matrix over a finite field (regarded as a structure in the natural way, as described in [BGS02]), what is its determinant?

## Rank vs. Genus ★★★

Author(s): Johnson

Question   Is there a hyperbolic 3-manifold whose fundamental group rank is strictly less than its Heegaard genus? How much can the two differ by?

Keywords:

## Finite Lattice Representation Problem ★★★★

Author(s):

Conjecture

There exists a finite lattice which is not the congruence lattice of a finite algebra.

Keywords: congruence lattice; finite algebra

## P vs. PSPACE ★★★

Author(s): Folklore

Problem   Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE?

Keywords: P; PSPACE; separation; unconditional

## Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem   Does there exist a graph with no subgraph isomorphic to which cannot be expressed as a union of triangle free graphs?

## Pentagon problem ★★★

Author(s): Nesetril

Question   Let be a 3-regular graph that contains no cycle of length shorter than . Is it true that for large enough~ there is a homomorphism ?

Keywords: cubic; homomorphism

## Growth of finitely presented groups ★★★

Problem   Does there exist a finitely presented group of intermediate growth?

Keywords: finitely presented; growth

## Antichains in the cycle continuous order ★★

Author(s): DeVos

If , are graphs, a function is called cycle-continuous if the pre-image of every element of the (binary) cycle space of is a member of the cycle space of .

Problem   Does there exist an infinite set of graphs so that there is no cycle continuous mapping between and whenever ?

Keywords: antichain; cycle; poset

## Double-critical graph conjecture ★★

Author(s): Erdos; Lovasz

A connected simple graph is called double-critical, if removing any pair of adjacent vertexes lowers the chromatic number by two.

Conjecture   is the only -chromatic double-critical graph

Keywords: coloring; complete graph

## The Erdos-Turan conjecture on additive bases ★★★★

Author(s): Erdos; Turan

Let . The representation function for is given by the rule . We call an additive basis if is never .

Conjecture   If is an additive basis, then is unbounded.

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

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

## Weak pentagon problem ★★

Author(s): Samal

Conjecture   If is a cubic graph not containing a triangle, then it is possible to color the edges of by five colors, so that the complement of every color class is a bipartite graph.

## Imbalance conjecture ★★

Author(s): Kozerenko

Conjecture   Suppose that for all edges we have . Then is graphic.

Keywords: edge imbalance; graphic sequences

## Edge list coloring conjecture ★★★

Author(s):

Conjecture   Let be a loopless multigraph. Then the edge chromatic number of equals the list edge chromatic number of .

Keywords:

## Special Primes ★

Author(s): George BALAN

Conjecture   Let be a prime natural number. Find all primes , such that .

Keywords:

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

## Which outer reloids are equal to inner ones ★★

Author(s): Porton

Warning: This formulation is vague (not exact).

Question   Characterize the set . In other words, simplify this formula.

The problem seems rather difficult.

Keywords:

## Pebbling a cartesian product ★★★

Author(s): Graham

We let denote the pebbling number of a graph .

Conjecture   .

Keywords: pebbling; zero sum

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

## Chromatic number of random lifts of complete graphs ★★

Author(s): Amit

Question   Is the chromatic number of a random lift of concentrated on a single value?

Keywords: random lifts, coloring

## Point sets with no empty pentagon ★

Author(s): Wood

Problem   Classify the point sets with no empty pentagon.

Keywords: combinatorial geometry; visibility graph

## Decomposing an even tournament in directed paths. ★★★

Author(s): Alspach; Mason; Pullman

Conjecture   Every tournament on an even number of vertices can be decomposed into directed paths.

Keywords:

## 3-Colourability of Arrangements of Great Circles ★★

Consider a set of great circles on a sphere with no three circles meeting at a point. The arrangement graph of has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.

Conjecture   Every arrangement graph of a set of great circles is -colourable.

Keywords: arrangement graph; graph coloring

## A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture   Let be integers. Set and for . Eventually we have ; put .

Example: , since , , , , , , , .

Prove or disprove: .

Keywords: Pierce expansions

## Linear Hypergraphs with Dimension 3 ★★

Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl

Conjecture   Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane.

Keywords: Hypergraphs

## 4-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every bridgeless graph with no Petersen minor has a nowhere-zero 4-flow.

Keywords: minor; nowhere-zero flow; Petersen graph