# Random

## The Erdös-Hajnal Conjecture ★★★

**Conjecture**For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .

Keywords: induced subgraph

## Decomposing an eulerian graph into cycles. ★★

Author(s): Hajós

**Conjecture**Every simple eulerian graph on vertices can be decomposed into at most cycles.

Keywords:

## Crossing numbers and coloring ★★★

Author(s): Albertson

We let denote the crossing number of a graph .

**Conjecture**Every graph with satisfies .

Keywords: coloring; complete graph; crossing number

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

## Cyclic spanning subdigraph with small cyclomatic number ★★

Author(s): Bondy

**Conjecture**Let be a digraph all of whose strong components are nontrivial. Then contains a cyclic spanning subdigraph with cyclomatic number at most .

Keywords:

## Inscribed Square Problem ★★

Author(s): Toeplitz

**Conjecture**Does every Jordan curve have 4 points on it which form the vertices of a square?

Keywords: simple closed curve; square

## Counting 3-colorings of the hex lattice ★★

Author(s): Thomassen

**Problem**Find .

Keywords: coloring; Lieb's Ice Constant; tiling; torus

## Growth of finitely presented groups ★★★

Author(s): Adyan

**Problem**Does there exist a finitely presented group of intermediate growth?

Keywords: finitely presented; growth

## Domination in cubic graphs ★★

Author(s): Reed

**Problem**Does every 3-connected cubic graph satisfy ?

Keywords: cubic graph; domination

## Every metamonovalued reloid is monovalued ★★

Author(s): Porton

**Conjecture**Every metamonovalued reloid is monovalued.

Keywords:

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

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

## Triangle free strongly regular graphs ★★★

Author(s):

**Problem**Is there an eighth triangle free strongly regular graph?

Keywords: strongly regular; triangle free

## Euler-Mascheroni constant ★★★

Author(s):

**Question**Is Euler-Mascheroni constant an transcendental number?

Keywords: constant; Euler; irrational; Mascheroni; rational; transcendental

## Hamilton decomposition of prisms over 3-connected cubic planar graphs ★★

**Conjecture**Every prism over a -connected cubic planar graph can be decomposed into two Hamilton cycles.

Keywords:

## List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

**Question**Given , what is the smallest integer such that ?

Keywords: complete bipartite graph; complete multipartite graph; list coloring

## Odd perfect numbers ★★★

Author(s): Ancient/folklore

**Conjecture**There is no odd perfect number.

Keywords: perfect number

## Generalised Empty Hexagon Conjecture ★★

Author(s): Wood

**Conjecture**For each there is an integer such that every set of at least points in the plane contains collinear points or an empty hexagon.

Keywords: empty hexagon

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

## Saturated $k$-Sperner Systems of Minimum Size ★★

Author(s): Morrison; Noel; Scott

**Question**Does there exist a constant and a function such that if , then every saturated -Sperner system has cardinality at least ?

Keywords: antichain; extremal combinatorics; minimum saturation; saturation; Sperner system

## Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let denote the diagonal Ramsey number.

**Conjecture**exists.

**Problem**Determine the limit in the above conjecture (assuming it exists).

Keywords: Ramsey number

## 57-regular Moore graph? ★★★

Keywords: cage; Moore graph

## Singmaster's conjecture ★★

Author(s): Singmaster

**Conjecture**There is a finite upper bound on the multiplicities of entries in Pascal's triangle, other than the number .

The number appears once in Pascal's triangle, appears twice, appears three times, and appears times. There are infinite families of numbers known to appear times. The only number known to appear times is . It is not known whether any number appears more than times. The conjectured upper bound could be ; Singmaster thought it might be or . See Singmaster's conjecture.

Keywords: Pascal's triangle

## Blatter-Specker Theorem for ternary relations ★★

Author(s): Makowsky

Let be a class of finite relational structures. We denote by the number of structures in over the labeled set . For any class definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every , the function is ultimately periodic modulo .

**Question**Does the Blatter-Specker Theorem hold for ternary relations.

Keywords: Blatter-Specker Theorem; FMT00-Luminy

## Unsolvability of word problem for 2-knot complements ★★★

Author(s): Gordon

**Problem**Does there exist a smooth/PL embedding of in such that the fundamental group of the complement has an unsolvable word problem?

Keywords: 2-knot; Computational Complexity; knot theory

## Hilbert-Smith conjecture ★★

Author(s): David Hilbert; Paul A. Smith

**Conjecture**Let be a locally compact topological group. If has a continuous faithful group action on an -manifold, then is a Lie group.

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

## Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

An directed graph is -diregular if every vertex has indegree and outdegree at least .

**Conjecture**For , every -diregular oriented graph on at most vertices has a Hamilton cycle.

Keywords:

## Coloring and immersion ★★★

Author(s): Abu-Khzam; Langston

**Conjecture**For every positive integer , every (loopless) graph with immerses .

Keywords: coloring; complete graph; immersion

## Nonseparating planar continuum ★★

Author(s):

**Conjecture**Does any path-connected, compact set in the plane which does not separate the plane have the fixed point property?

A set has the fixed point property if every continuous map from it into itself has a fixed point.

Keywords: fixed point

## Infinite uniquely hamiltonian graphs ★★

Author(s): Mohar

**Problem**Are there any uniquely hamiltonian locally finite 1-ended graphs which are regular of degree ?

Keywords: hamiltonian; infinite graph; uniquely hamiltonian

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

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

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

## Convex 'Fair' Partitions Of Convex Polygons ★★

Author(s): Nandakumar; Ramana

**Basic Question:** Given any positive integer *n*, can any convex polygon be partitioned into *n* convex pieces so that all pieces have the same area and same perimeter?

**Definitions:** Define a *Fair Partition* of a polygon as a partition of it into a finite number of pieces so that every piece has both the same area and the same perimeter. Further, if all the resulting pieces are convex, call it a *Convex Fair Partition*.

**Questions:** 1. (Rephrasing the above 'basic' question) Given any positive integer *n*, can any convex polygon be convex fair partitioned into n pieces?

2. If the answer to the above is *"Not always''*, how does one decide the possibility of such a partition for a given convex polygon and a given *n*? And if fair convex partition is allowed by a specific convex polygon for a give *n*, how does one find the *optimal* convex fair partition that *minimizes* the total length of the cut segments?

3. Finally, what could one say about *higher dimensional analogs* of this question?

**Conjecture:** The authors tend to believe that the answer to the above 'basic' question is "yes". In other words they guess: *Every* convex polygon allows a convex fair partition into *n* pieces for any *n*

Keywords: Convex Polygons; Partitioning

## Approximation Ratio for Maximum Edge Disjoint Paths problem ★★

Author(s): Bentz

**Conjecture**Can the approximation ratio be improved for the Maximum Edge Disjoint Paths problem (MaxEDP) in planar graphs or can an inapproximability result stronger than -hardness?

Keywords: approximation algorithms; Disjoint paths; planar graph; polynomial algorithm

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

## (m,n)-cycle covers ★★★

Author(s): Celmins; Preissmann

**Conjecture**Every bridgeless graph has a (5,2)-cycle-cover.

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

## Cores of Cayley graphs ★★★★★

Author(s): Samal

**Conjecture**Let be an abelian group. Is the core of a Cayley graph (on some power of ) a Cayley graph (on some power of )?

Keywords: Cayley graph; core

## Rota's unimodal conjecture ★★★

Author(s): Rota

Let be a matroid of rank , and for let be the number of closed sets of rank .

**Conjecture**is unimodal.

**Conjecture**is log-concave.

Keywords: flat; log-concave; matroid

## Are all Mersenne Numbers with prime exponent square-free? ★★★

Author(s):

**Conjecture**Are all Mersenne Numbers with prime exponent Square free?

Keywords: Mersenne number

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

## Special Primes ★

Author(s): George BALAN

**Conjecture**Let be a prime natural number. Find all primes , such that .

Keywords:

## A funcoid related to directed topological spaces ★★

Author(s): Porton

**Conjecture**Let be the complete funcoid corresponding to the usual topology on extended real line . Let be the order on this set. Then is a complete funcoid.

**Proposition**It is easy to prove that is the infinitely small right neighborhood filter of point .

If proved true, the conjecture then can be generalized to a wider class of posets.

Keywords:

## Atomicity of the poset of multifuncoids ★★

Author(s): Porton

**Conjecture**The poset of multifuncoids of the form is for every sets and :

- \item atomic; \item atomistic.

See below for definition of all concepts and symbols used to in this conjecture.

Refer to this Web site for the theory which I now attempt to generalize.

Keywords: multifuncoid

## Funcoidal products inside an inward reloid ★★

Author(s): Porton

**Conjecture**(solved) If then for every funcoid and atomic f.o. and on the source and destination of correspondingly.

A stronger conjecture:

**Conjecture**If then for every funcoid and , .

Keywords: inward reloid