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

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

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

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

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 ?

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

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

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

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

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

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

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

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

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

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 ?

Keywords: circular coloring; geometric graph; orthogonality

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

Keywords: Disjoint paths; edge-connectivity; spanning trees

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

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

Keywords: invertable matrices, integer matrices

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