# Random

Author(s): Harvey; Reed; Seymour; Wood

Conjecture   For every graph ,
(a)
(b)
(c) .

Keywords: fractional coloring, minors

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

## Inequality for square summable complex series ★★

Author(s): Retkes

Conjecture   For all the following inequality holds

Keywords: Inequality

## Three-chromatic (0,2)-graphs ★★

Author(s): Payan

Question   Are there any (0,2)-graphs with chromatic number exactly three?

Keywords:

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

## Distribution and upper bound of mimic numbers ★★

Author(s): Bhattacharyya

Problem

Let the notation denote '' divides ''. The mimic function in number theory is defined as follows [1].

Definition   For any positive integer divisible by , the mimic function, , is given by,

By using this definition of mimic function, the mimic number of any non-prime integer is defined as follows [1].

Definition   The number is defined to be the mimic number of any positive integer , with respect to , for the minimum value of which .

Given these two definitions and a positive integer , find the distribution of mimic numbers of those numbers divisible by .

Again, find whether there is an upper bound of mimic numbers for a set of numbers divisible by any fixed positive integer .

Keywords: Divisibility; mimic function; mimic number

## Transversal achievement game on a square grid ★★

Author(s): Erickson

Problem   Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an grid. The first player (if any) to occupy a set of cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?

Keywords: game

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

## Triangle-packing vs triangle edge-transversal. ★★

Author(s): Tuza

Conjecture   If has at most edge-disjoint triangles, then there is a set of edges whose deletion destroys every triangle.

Keywords:

## The Crossing Number of the Complete Graph ★★★

Author(s):

The crossing number of is the minimum number of crossings in all drawings of in the plane.

Conjecture

Keywords: complete graph; crossing number

## Directed path of length twice the minimum outdegree ★★★

Author(s): Thomassé

Conjecture   Every oriented graph with minimum outdegree contains a directed path of length .

Keywords:

## Cube-Simplex conjecture ★★★

Author(s): Kalai

Conjecture   For every positive integer , there exists an integer so that every polytope of dimension has a -dimensional face which is either a simplex or is combinatorially isomorphic to a -dimensional cube.

Keywords: cube; facet; polytope; simplex

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

## Rota's unimodal conjecture ★★★

Author(s): Rota

Let be a matroid of rank , and for let be the number of closed sets of rank .

Conjecture   is unimodal.
Conjecture   is log-concave.

Keywords: flat; log-concave; matroid

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

## Growth of finitely presented groups ★★★

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

Keywords: finitely presented; growth

## Circular choosability of planar graphs ★

Author(s): Mohar

Let be a graph. If and are two integers, a -colouring of is a function from to such that for each edge . Given a list assignment of , i.e.~a mapping that assigns to every vertex a set of non-negative integers, an -colouring of is a mapping such that for every . A list assignment is a --list-assignment if and for each vertex . Given such a list assignment , the graph G is --colourable if there exists a --colouring , i.e. is both a -colouring and an -colouring. For any real number , the graph is --choosable if it is --colourable for every --list-assignment . Last, is circularly -choosable if it is --choosable for any , . The circular choosability (or circular list chromatic number or circular choice number) of G is

Problem   What is the best upper bound on circular choosability for planar graphs?

Keywords: choosability; circular colouring; planar graphs

## Graphs of exact colorings ★★

Author(s):

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:

## Jorgensen's Conjecture ★★★

Author(s): Jorgensen

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

Keywords: connectivity; minor

## Woodall's Conjecture ★★★

Author(s): Woodall

Conjecture   If is a directed graph with smallest directed cut of size , then has disjoint dijoins.

Keywords: digraph; packing

## Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

Conjecture
\item If is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph of a locally finite graph is 4-connected, then is hamiltonian.

Keywords: hamiltonian; infinite graph; line graphs

## Linial-Berge path partition duality ★★★

Author(s): Berge; Linial

Conjecture   The minimum -norm of a path partition on a directed graph is no more than the maximal size of an induced -colorable subgraph.

Keywords: coloring; directed path; partition

## Wall-Sun-Sun primes and Fibonacci divisibility ★★

Author(s):

Conjecture   For any prime , there exists a Fibonacci number divisible by exactly once.

Equivalently:

Conjecture   For any prime , does not divide where is the Legendre symbol.

Keywords: Fibonacci; prime

## Subset-sums equality (pigeonhole version) ★★★

Author(s):

Problem   Let be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?

Keywords: polynomial algorithm; search problem

## A homomorphism problem for flows ★★

Author(s): DeVos

Conjecture   Let be abelian groups and let and satisfy and . If there is a homomorphism from to , then every graph with a B-flow has a B'-flow.

Keywords: homomorphism; nowhere-zero flow; tension

## Giuga's Conjecture on Primality ★★

Author(s): Giuseppe Giuga

Conjecture   is a prime iff

Keywords: primality

## The Double Cap Conjecture ★★

Author(s): Kalai

Conjecture   The largest measure of a Lebesgue measurable subset of the unit sphere of containing no pair of orthogonal vectors is attained by two open caps of geodesic radius around the north and south poles.

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

## Every 4-connected toroidal graph has a Hamilton cycle ★★

Author(s): Grunbaum; Nash-Williams

Conjecture   Every 4-connected toroidal graph has a Hamilton cycle.

Keywords:

## Are almost all graphs determined by their spectrum? ★★★

Author(s):

Problem   Are almost all graphs uniquely determined by the spectrum of their adjacency matrix?

Keywords: cospectral; graph invariant; spectrum

## Bounding the on-line choice number in terms of the choice number ★★

Author(s): Zhu

Question   Are there graphs for which is arbitrarily large?

## Algebraic independence of pi and e ★★★

Author(s):

Conjecture   and are algebraically independent

Keywords: algebraic independence

## Are there only finite Fermat Primes? ★★★

Author(s):

Conjecture   A Fermat prime is a Fermat number that is prime. The only known Fermat primes are F_0 =3,F_1=5,F_2=17,F_3 =257 ,F_4=65537 It is unknown if other fermat primes exist.

Keywords:

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

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

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

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

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

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

## List Total Colouring Conjecture ★★

Author(s): Borodin; Kostochka; Woodall

Conjecture   If is the total graph of a multigraph, then .

Keywords: list coloring; Total coloring; total graphs

## Edge-disjoint Hamilton cycles in highly strongly connected tournaments. ★★

Author(s): Thomassen

Conjecture   For every , there is an integer so that every strongly -connected tournament has edge-disjoint Hamilton cycles.

Keywords:

## Inverse Galois Problem ★★★★

Author(s): Hilbert

Conjecture   Every finite group is the Galois group of some finite algebraic extension of .

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:

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

## Euler-Mascheroni constant ★★★

Author(s):

Question   Is Euler-Mascheroni constant an transcendental number?

Keywords: constant; Euler; irrational; Mascheroni; rational; transcendental

## Oriented trees in n-chromatic digraphs ★★★

Author(s): Burr

Conjecture   Every digraph with chromatic number at least contains every oriented tree of order as a subdigraph.

Keywords:

## Laplacian Degrees of a Graph ★★

Author(s): Guo

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

Keywords: degree sequence; Laplacian matrix

## 5-flow conjecture ★★★★

Author(s): Tutte

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

Keywords: cubic; nowhere-zero flow

## Erdös-Szekeres conjecture ★★★

Author(s): Erdos; Szekeres

Conjecture   Every set of points in the plane in general position contains a subset of points which form a convex -gon.

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