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

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

Keywords: compact space; compact topology; funcoid; reloid; uniform space; uniformity

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

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

Author(s): Iradmusa

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

Keywords: chromatic number, fractional power of graph, clique number

## The Berge-Fulkerson conjecture ★★★★

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

Keywords: bounded tree width; cardinality predicates; FMT03-Bedlewo; MSO

## Unions of triangle free graphs ★★★

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

Keywords: forbidden subgraph; infinite graph; triangle free

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

## List Hadwiger Conjecture ★★

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

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

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

Keywords:

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

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

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

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.

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

## Nearly spanning regular subgraphs ★★★

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

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