# Random

## Diophantine quintuple conjecture ★★

Author(s):

**Definition**A set of m positive integers is called a Diophantine -tuple if is a perfect square for all .

**Conjecture (1)**Diophantine quintuple does not exist.

It would follow from the following stronger conjecture [Da]:

**Conjecture (2)**If is a Diophantine quadruple and , then

Keywords:

## Finite entailment of Positive Horn logic ★★

Author(s): Martin

**Question**Positive Horn logic (pH) is the fragment of FO involving exactly . Does the fragment have the finite model property?

Keywords: entailment; finite satisfiability; horn logic

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

## Rota's basis conjecture ★★★

Author(s): Rota

**Conjecture**Let be a vector space of dimension and let be bases. Then there exist disjoint transversals of each of which is a base.

Keywords: base; latin square; linear algebra; matroid; transversal

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

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

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

## 3-accessibility of Fibonacci numbers ★★

**Question**Is the set of Fibonacci numbers 3-accessible?

Keywords: Fibonacci numbers; monochromatic diffsequences

## Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

**Question**

Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?

Keywords: algorithm; Exponential-time algorithm; homomorphism

## Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family of graphs is -*bounded* if there exists a function so that every satisfies .

**Conjecture**For every fixed tree , the family of graphs with no induced subgraph isomorphic to is -bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

## Are all Fermat Numbers square-free? ★★★

Author(s):

**Conjecture**Are all Fermat Numbers Square-Free?

Keywords:

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

## Total Colouring Conjecture ★★★

Author(s): Behzad

**Conjecture**A total coloring of a graph is an assignment of colors to the vertices and the edges of such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph , , equals the minimum number of colors needed in a total coloring of . It is an old conjecture of Behzad that for every graph , the total chromatic number equals the maximum degree of a vertex in , plus one or two. In other words,

Keywords: Total coloring

## Covering systems with big moduli ★★

**Problem**Does for every integer exist a covering system with all moduli distinct and at least equal to~?

Keywords: covering system

## Beneš Conjecture (graph-theoretic form) ★★★

Author(s): Beneš

**Problem ()**Find a sufficient condition for a straight -stage graph to be rearrangeable. In particular, what about a straight uniform graph?

**Conjecture ()**Let be a simple regular ordered -stage graph. Suppose that the graph is externally connected, for some . Then the graph is rearrangeable.

Keywords:

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

Author(s): Gallai

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

Keywords:

## One-way functions exist ★★★★

Author(s):

**Conjecture**One-way functions exist.

Keywords: one way function

## A diagram about funcoids and reloids ★★

Author(s): Porton

Define for posets with order :

- ;
- .

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

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

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

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

## Bases of many weights ★★★

Let be an (additive) abelian group, and for every let .

**Conjecture**Let be a matroid on , let be a map, put and . Then

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

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.

Keywords: additive basis; representation function

## Slice-ribbon problem ★★★★

Author(s): Fox

**Conjecture**Given a knot in which is slice, is it a ribbon knot?

## Jones' conjecture ★★

For a graph , let denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let denote the cardinality of a minimum feedback vertex set (set of vertices so that is acyclic).

**Conjecture**For every planar graph , .

Keywords: cycle packing; feedback vertex set; planar graph

## Inequality of the means ★★★

Author(s):

**Question**Is is possible to pack rectangular -dimensional boxes each of which has side lengths inside an -dimensional cube with side length ?

Keywords: arithmetic mean; geometric mean; Inequality; packing

## Domination in plane triangulations ★★

**Conjecture**Every sufficiently large plane triangulation has a dominating set of size .

Keywords: coloring; domination; multigrid; planar graph; triangulation

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

## Cycles in Graphs of Large Chromatic Number ★★

Author(s): Brewster; McGuinness; Moore; Noel

**Conjecture**If , then contains at least cycles of length .

Keywords: chromatic number; cycles

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

## Dividing up the unrestricted partitions ★★

Begin with the generating function for unrestricted partitions:

(1+x+x^2+...)(1+x^2+x^4+...)(1+x^3+x^6+...)...

Now change some of the plus signs to minus signs. The resulting series will have coefficients congruent, mod 2, to the coefficients of the generating series for unrestricted partitions. I conjecture that the signs may be chosen such that all the coefficients of the series are either 1, -1, or zero.

Keywords: congruence properties; partition

## Ramsey properties of Cayley graphs ★★★

Author(s): Alon

**Conjecture**There exists a fixed constant so that every abelian group has a subset with so that the Cayley graph has no clique or independent set of size .

Keywords: Cayley graph; Ramsey number

## Alexa's Conjecture on Primality ★★

Author(s): Alexa

**Definition**Let be the unique integer (with respect to a fixed ) such that

**Conjecture**A natural number is a prime iff

Keywords: primality

## Aharoni-Berger conjecture ★★★

**Conjecture**If are matroids on and for every partition of , then there exists with which is independent in every .

Keywords: independent set; matroid; partition

## Seymour's self-minor conjecture ★★★

Author(s): Seymour

**Conjecture**Every infinite graph is a proper minor of itself.

Keywords: infinite graph; minor

## Which lattices occur as intervals in subgroup lattices of finite groups? ★★★★

Author(s):

**Conjecture**

There exists a finite lattice that is not an interval in the subgroup lattice of a finite group.

Keywords: congruence lattice; finite groups

## Smooth 4-dimensional Poincare conjecture ★★★★

Author(s): Poincare; Smale; Stallings

**Conjecture**If a -manifold has the homotopy type of the -sphere , is it diffeomorphic to ?

Keywords: 4-manifold; poincare; sphere

## Convex Equipartitions with Extreme Perimeter ★★

Author(s): Nandakumar

To divide a given 2D convex region C into a specified number n of convex pieces all of equal area (perimeters could be different) such that the total perimeter of pieces is (1) maximized (2) minimized.

Remark: It appears maximizing the total perimeter is the easier problem.

Keywords: convex equipartition

## Almost all non-Hamiltonian 3-regular graphs are 1-connected ★★

Author(s): Haythorpe

**Conjecture**Denote by the number of non-Hamiltonian 3-regular graphs of size , and similarly denote by the number of non-Hamiltonian 3-regular 1-connected graphs of size .

Is it true that ?

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

## Shuffle-Exchange Conjecture ★★★

Author(s): Beneš; Folklore; Stone

Given integers , let be the smallest integer such that the symmetric group on the set of all words of length over a -letter alphabet can be generated as ( times), where is the *shuffle permutation* defined by , and is the *exchange group* consisting of all permutations in preserving the first letters in the words.

**Problem (SE)**Evaluate .

**Conjecture (SE)**, for all .

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

## Universal point sets for planar graphs ★★★

Author(s): Mohar

We say that a set is -*universal* if every vertex planar graph can be drawn in the plane so that each vertex maps to a distinct point in , and all edges are (non-intersecting) straight line segments.

**Question**Does there exist an -universal set of size ?

Keywords: geometric graph; planar graph; universal set

## Odd-cycle transversal in triangle-free graphs ★★

Author(s): Erdos; Faudree; Pach; Spencer

**Conjecture**If is a simple triangle-free graph, then there is a set of at most edges whose deletion destroys every odd cycle.

Keywords:

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

## Erdős–Straus conjecture ★★

**Conjecture**

For all , there exist positive integers , , such that .

Keywords: Egyptian fraction

## Kneser–Poulsen conjecture ★★★

**Conjecture**If a finite set of unit balls in is rearranged so that the distance between each pair of centers does not decrease, then the volume of the union of the balls does not decrease.

Keywords: pushing disks

## Faithful cycle covers ★★★

Author(s): Seymour

**Conjecture**If is a graph, is admissable, and is even for every , then has a faithful cover.

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