# Random

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

## Sum of prime and semiprime conjecture ★★

Author(s): Geoffrey Marnell

Conjecture   Every even number greater than can be represented as the sum of an odd prime number and an odd semiprime .

Keywords: prime; semiprime

## Direct proof of a theorem about compact funcoids ★★

Author(s): Porton

Conjecture   Let is a -separable (the same as for symmetric transitive) compact funcoid and is a uniform space (reflexive, symmetric, and transitive endoreloid) such that . Then .

The main purpose here is to find a direct proof of this conjecture. It seems that this conjecture can be derived from the well known theorem about existence of exactly one uniformity on a compact set. But that would be what I call an indirect proof, we need a direct proof instead.

The direct proof may be constructed by correcting all errors an omissions in this draft article.

Direct proof could be better because with it we would get a little more general statement like this:

Conjecture   Let be a -separable compact reflexive symmetric funcoid and be a reloid such that
\item ; \item .

Then .

## Decomposing a connected graph into paths. ★★★

Author(s): Gallai

Conjecture   Every simple connected graph on vertices can be decomposed into at most paths.

Keywords:

## Drawing disconnected graphs on surfaces ★★

Author(s): DeVos; Mohar; Samal

Conjecture   Let be the disjoint union of the graphs and and let be a surface. Is it true that every optimal drawing of on has the property that and are disjoint?

Keywords: crossing number; surface

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

## Simultaneous partition of hypergraphs ★★

Author(s): Kühn; Osthus

Problem   Let and be two -uniform hypergraph on the same vertex set . Does there always exist a partition of into classes such that for both , at least hyperedges of meet each of the classes ?

Keywords:

## Refuting random 3SAT-instances on $O(n)$ clauses (weak form) ★★★

Author(s): Feige

Conjecture   For every rational and every rational , there is no polynomial-time algorithm for the following problem.

Given is a 3SAT (3CNF) formula on variables, for some , and clauses drawn uniformly at random from the set of formulas on variables. Return with probability at least 0.5 (over the instances) that is typical without returning typical for any instance with at least simultaneously satisfiable clauses.

Keywords: NP; randomness in TCS; satisfiability

## Outer reloid of restricted funcoid ★★

Author(s): Porton

Question   for every filter objects and and a funcoid ?

Keywords: direct product of filters; outer reloid

## Reed's omega, delta, and chi conjecture ★★★

Author(s): Reed

For a graph , we define to be the maximum degree, to be the size of the largest clique subgraph, and to be the chromatic number of .

Conjecture   for every graph .

Keywords: coloring

## Jacob Palis Conjecture(Finitude of Attractors)(Dynamical Systems) ★★★★

Author(s):

Conjecture   Let be the space of Diffeomorphisms on the connected , compact and boundaryles manifold M and the space of vector fields. There is a dense set ( ) such that exhibit a finite number of attractor whose basins cover Lebesgue almost all ambient space

This is a very Deep and Hard problem in Dynamical Systems . It present the dream of the dynamicist mathematicians .

Keywords: Attractors , basins, Finite

## Vertex Coloring of graph fractional powers ★★★

Conjecture   Let be a graph and be a positive integer. The power of , denoted by , is defined on the vertex set , by connecting any two distinct vertices and with distance at most . In other words, . Also subdivision of , denoted by , is constructed by replacing each edge of with a path of length . Note that for , we have .
Now we can define the fractional power of a graph as follows:
Let be a graph and . The graph is defined by the power of the subdivision of . In other words .
Conjecture. Let be a connected graph with and be a positive integer greater than 1. Then for any positive integer , we have .
In [1], it was shown that this conjecture is true in some special cases.

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

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

## Monadic second-order logic with cardinality predicates ★★

Author(s): Courcelle

The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:

\item \item

where is a fixed recursive set of integers.

Let us fix and a closed formula in this language.

Conjecture   Is it true that the validity of for a graph of tree-width at most can be tested in polynomial time in the size of ?

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

## The Hodge Conjecture ★★★★

Author(s): Hodge

Conjecture   Let be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of .

Keywords: Hodge Theory; Millenium Problems

Author(s): Kawarabayashi; Mohar

Conjecture   Every -minor-free graph is -list-colourable for some constant .

Keywords: Hadwiger conjecture; list colouring; minors

## KPZ Universality Conjecture ★★★

Author(s):

Conjecture   Formulate a central limit theorem for the KPZ universality class.

Keywords: KPZ equation, central limit theorem

## P vs. BPP ★★★

Author(s): Folklore

Conjecture   Can all problems that can be computed by a probabilistic Turing machine (with error probability < 1/3) in polynomial time be solved by a deterministic Turing machine in polynomial time? That is, does P = BPP?

Keywords: BPP; circuit complexity; pseudorandom generators

## Counterexamples to the Baillie-PSW primality test ★★

Author(s):

Problem  (1)   Find a counterexample to Baillie-PSW primality test or prove that there is no one.
Problem  (2)   Find a composite or which divides both (see Fermat pseudoprime) and the Fibonacci number (see Lucas pseudoprime), or prove that there is no such .

Keywords:

## Reconstruction conjecture ★★★★

Author(s): Kelly; Ulam

The deck of a graph is the multiset consisting of all unlabelled subgraphs obtained from by deleting a vertex in all possible ways (counted according to multiplicity).

Conjecture   If two graphs on vertices have the same deck, then they are isomorphic.

Keywords: reconstruction

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

## Point sets with no empty pentagon ★

Author(s): Wood

Problem   Classify the point sets with no empty pentagon.

Keywords: combinatorial geometry; visibility graph

## Switching reconstruction of digraphs ★★

Author(s): Bondy; Mercier

Question   Are there any switching-nonreconstructible digraphs on twelve or more vertices?

Keywords:

## Large induced forest in a planar graph. ★★

Author(s): Abertson; Berman

Conjecture   Every planar graph on verices has an induced forest with at least vertices.

Keywords:

## Giuga's Conjecture on Primality ★★

Author(s): Giuseppe Giuga

Conjecture   is a prime iff

Keywords: primality

## Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture   A triangle-free graph with maximum degree has chromatic number at most .

Keywords: chromatic number; girth; maximum degree; triangle free

## Concavity of van der Waerden numbers ★★

Author(s): Landman

For and positive integers, the (mixed) van der Waerden number is the least positive integer such that every (red-blue)-coloring of admits either a -term red arithmetic progression or an -term blue arithmetic progression.

Conjecture   For all and with , .

Keywords: arithmetic progression; van der Waerden

## 57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

Question   Does there exist a 57-regular graph with diameter 2 and girth 5?

Keywords: cage; Moore graph

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

## Unit vector flows ★★

Author(s): Jain

Conjecture   For every graph without a bridge, there is a flow .

Conjecture   There exists a map so that antipodal points of receive opposite values, and so that any three points which are equidistant on a great circle have values which sum to zero.

Keywords: nowhere-zero flow

## Simplexity of the n-cube ★★★

Author(s):

Question   What is the minimum cardinality of a decomposition of the -cube into -simplices?

Keywords: cube; decomposition; simplex

## Partitionning a tournament into k-strongly connected subtournaments. ★★

Author(s): Thomassen

Problem   Let be positve integer Does there exists an integer such that every -strong tournament admits a partition of its vertex set such that the subtournament induced by is a non-trivial -strong for all .

Keywords:

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

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

## Schanuel's Conjecture ★★★★

Author(s): Schanuel

Conjecture   Given any complex numbers which are linearly independent over the rational numbers , then the extension field has transcendence degree of at least over .

Keywords: algebraic independence

## Sequence defined on multisets ★★

Author(s): Erickson

Conjecture   Define a array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. For example, starting with the array , the sequence is: -> -> -> -> -> -> -> -> -> -> -> , and we now have a fixed point (loop of one array).

The process always results in a loop of 1, 2, or 3 arrays.

Keywords: multiset; sequence

## Domination in cubic graphs ★★

Author(s): Reed

Problem   Does every 3-connected cubic graph satisfy ?

Keywords: cubic graph; domination

## Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph is -degenerate if every subgraph of has a vertex of degree .

Conjecture   Every simple planar graph has a 5-coloring so that for , the union of any color classes induces a -degenerate graph.

Keywords: coloring; degenerate; planar

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

## Partition of a cubic 3-connected graphs into paths of length 2. ★★

Author(s): Kelmans

Problem   Does every -connected cubic graph on vertices admit a partition into paths of length ?

Keywords:

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

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

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

## Nearly spanning regular subgraphs ★★★

Author(s): Alon; Mubayi

Conjecture   For every and every positive integer , there exists so that every simple -regular graph with has a -regular subgraph with .

Keywords: regular; subgraph

## Monochromatic vertex colorings inherited from Perfect Matchings ★★★

Author(s):

Conjecture   For which values of and are there bi-colored graphs on vertices and different colors with the property that all the monochromatic colorings have unit weight, and every other coloring cancels out?

Keywords:

## Burnside problem ★★★★

Author(s): Burnside

Conjecture   If a group has generators and exponent , is it necessarily finite?

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:

## The 3n+1 conjecture ★★★

Author(s): Collatz

Conjecture   Let if is odd and if is even. Let . Assume we start with some number and repeatedly take the of the current number. Prove that no matter what the initial number is we eventually reach .

Keywords: integer sequence