# Random

## Ádám's Conjecture ★★★

Author(s): Ádám

Conjecture   Every digraph with at least one directed cycle has an arc whose reversal reduces the number of directed cycles.

Keywords:

## Inequality for square summable complex series ★★

Author(s): Retkes

Conjecture   For all the following inequality holds

Keywords: Inequality

## Ding's tau_r vs. tau conjecture ★★★

Author(s): Ding

Conjecture   Let be an integer and let be a minor minimal clutter with . Then either has a minor for some or has Lehman's property.

Keywords: clutter; covering; MFMC property; packing

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

## Jorgensen's Conjecture ★★★

Author(s): Jorgensen

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

Keywords: connectivity; minor

## Frobenius number of four or more integers ★★

Author(s):

Problem   Find an explicit formula for Frobenius number of co-prime positive integers for .

Keywords:

## Sticky Cantor sets ★★

Author(s):

Conjecture   Let be a Cantor set embedded in . Is there a self-homeomorphism of for every greater than so that moves every point by less than and does not intersect ? Such an embedded Cantor set for which no such exists (for some ) is called "sticky". For what dimensions do sticky Cantor sets exist?

Keywords: Cantor set

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

## Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

Conjecture
\item If is a countable connected graph then its third power is hamiltonian. \item If is a 2-connected countable graph then its square is hamiltonian.

Keywords: hamiltonian; infinite graph

## Seagull problem ★★★

Author(s): Seymour

Conjecture   Every vertex graph with no independent set of size has a complete graph on vertices as a minor.

Keywords: coloring; complete graph; minor

## Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

Conjecture   If is a -connected planar graph, then has a Hamilton cycle.

Keywords:

## Hamiltonian paths and cycles in vertex transitive graphs ★★★

Author(s): Lovasz

Problem   Does every connected vertex-transitive graph have a Hamiltonian path?

Keywords: cycle; hamiltonian; path; vertex-transitive

## One-way functions exist ★★★★

Author(s):

Conjecture   One-way functions exist.

Keywords: one way function

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

## Kneser–Poulsen conjecture ★★★

Author(s): Kneser; Poulsen

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

## Discrete Logarithm Problem ★★★

Author(s):

If is prime and , we write if satisfies . The problem of finding such an integer for a given (with ) is the Discrete Log Problem.

Conjecture   There does not exist a polynomial time algorithm to solve the Discrete Log Problem.

Keywords: discrete log; NP

## Hamiltonian cycles in line graphs ★★★

Author(s): Thomassen

Conjecture   Every 4-connected line graph is hamiltonian.

Keywords: hamiltonian; line graphs

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

## 4-connected graphs are not uniquely hamiltonian ★★

Author(s): Fleischner

Conjecture   Every -connected graph with a Hamilton cycle has a second Hamilton cycle.

Keywords:

## The intersection of two perfect matchings ★★

Author(s): Macajova; Skoviera

Conjecture   Every bridgeless cubic graph has two perfect matchings , so that does not contain an odd edge-cut.

Keywords: cubic; nowhere-zero flow; perfect matching

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

## Stable set meeting all longest directed paths. ★★

Author(s): Laborde; Payan; Xuong N.H.

Conjecture   Every digraph has a stable set meeting all longest directed paths

Keywords:

## The circular embedding conjecture ★★★

Author(s): Haggard

Conjecture   Every 2-connected graph may be embedded in a surface so that the boundary of each face is a cycle.

Keywords: cover; cycle

## Frankl's union-closed sets conjecture ★★

Author(s): Frankl

Conjecture   Let be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists such that is an element of at least half the members of .

Keywords:

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

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

## Arc-disjoint out-branching and in-branching ★★

Author(s): Thomassen

Conjecture   There exists an integer such that every -arc-strong digraph with specified vertices and contains an out-branching rooted at and an in-branching rooted at which are arc-disjoint.

Keywords:

## Lindelöf hypothesis ★★

Author(s): Lindelöf

Conjecture   For any

Since can be replaced by a smaller value, we can also write the conjecture as, for any positive ,

Keywords: Riemann Hypothesis; zeta

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

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

## Snevily's conjecture ★★★

Author(s): Snevily

Conjecture   Let be an abelian group of odd order and let satisfy . Then the elements of and may be ordered and so that the sums are pairwise distinct.

Keywords: addition table; latin square; transversal

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

## Unfriendly partitions ★★★

Author(s): Cowan; Emerson

If is a graph, we say that a partition of is unfriendly if every vertex has at least as many neighbors in the other classes as in its own.

Problem   Does every countably infinite graph have an unfriendly partition into two sets?

Keywords: coloring; infinite graph; partition

## Circular colouring the orthogonality graph ★★

Author(s): DeVos; Ghebleh; Goddyn; Mohar; Naserasr

Let denote the graph with vertex set consisting of all lines through the origin in and two vertices adjacent in if they are perpendicular.

Problem   Is ?

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

## Shuffle-Exchange Conjecture (graph-theoretic form) ★★★

Author(s): Beneš; Folklore; Stone

Given integers , the 2-stage Shuffle-Exchange graph/network, denoted , is the simple -regular bipartite graph with the ordered pair of linearly labeled parts and , where , such that vertices and are adjacent if and only if (see Fig.1).

Given integers , the -stage Shuffle-Exchange graph/network, denoted , is the proper (i.e., respecting all the orders) concatenation of identical copies of (see Fig.1).

Let be the smallest integer such that the graph is rearrangeable.

Problem   Find .
Conjecture   .

Keywords:

## Kriesell's Conjecture ★★

Author(s): Kriesell

Conjecture   Let be a graph and let such that for any pair there are edge-disjoint paths from to in . Then contains edge-disjoint trees, each of which contains .

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

## Is Skewes' number e^e^e^79 an integer? ★★

Author(s):

Conjecture

Skewes' number is not an integer.

Keywords:

## Long directed cycles in diregular digraphs ★★★

Author(s): Jackson

Conjecture   Every strong oriented graph in which each vertex has indegree and outdegree at least contains a directed cycle of length at least .

Keywords:

## Non-edges vs. feedback edge sets in digraphs ★★★

Author(s): Chudnovsky; Seymour; Sullivan

For any simple digraph , we let be the number of unordered pairs of nonadjacent vertices (i.e. the number of non-edges), and be the size of the smallest feedback edge set.

Conjecture  If is a simple digraph without directed cycles of length , then .

Keywords: acyclic; digraph; feedback edge set; triangle free

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

## Burnside problem ★★★★

Author(s): Burnside

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

Keywords:

## Covering powers of cycles with equivalence subgraphs ★

Author(s):

Conjecture   Given and , the graph has equivalence covering number .

Keywords:

## inverse of an integer matrix ★★

Author(s): Gregory

Question   I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all . Suppose X is an m-by-n integer matrix . Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.

## Every metamonovalued funcoid is monovalued ★★

Author(s): Porton

Conjecture   Every metamonovalued funcoid is monovalued.

The reverse is almost trivial: Every monovalued funcoid is metamonovalued.

Keywords: monovalued

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

## Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

## Closing Lemma for Diffeomorphism (Dynamical Systems) ★★★★

Author(s): Charles Pugh

Conjecture   Let and . Then for any neighborhood there is such that is periodic point of

There is an analogous conjecture for flows ( vector fields . In the case of diffeos this was proved by Charles Pugh for . In the case of Flows this has been solved by Sushei Hayahshy for . But in the two cases the problem is wide open for

Keywords: Dynamics , Pertubation

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