# Random

## Odd incongruent covering systems ★★★

**Conjecture**There is no covering system whose moduli are odd, distinct, and greater than 1.

Keywords: covering system

## Triangle-packing vs triangle edge-transversal. ★★

Author(s): Tuza

**Conjecture**If has at most edge-disjoint triangles, then there is a set of edges whose deletion destroys every triangle.

Keywords:

## Giuga's Conjecture on Primality ★★

Author(s): Giuseppe Giuga

**Conjecture**is a prime iff

Keywords: primality

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

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

## General position subsets ★★

Author(s): Gowers

**Question**What is the least integer such that every set of at least points in the plane contains collinear points or a subset of points in general position (no three collinear)?

## Are different notions of the crossing number the same? ★★★

**Problem**Does the following equality hold for every graph ?

The crossing number of a graph is the minimum number of edge crossings in any drawing of in the plane. In the *pairwise crossing number* , we minimize the number of pairs of edges that cross.

Keywords: crossing number; pair-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:

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

## A nowhere-zero point in a linear mapping ★★★

Author(s): Jaeger

**Conjecture**If is a finite field with at least 4 elements and is an invertible matrix with entries in , then there are column vectors which have no coordinates equal to zero such that .

Keywords: invertible; nowhere-zero flow

## List Hadwiger Conjecture ★★

Author(s): Kawarabayashi; Mohar

**Conjecture**Every -minor-free graph is -list-colourable for some constant .

Keywords: Hadwiger conjecture; list colouring; minors

## Upgrading a completary multifuncoid ★★

Author(s): Porton

Let be a set, be the set of filters on ordered reverse to set-theoretic inclusion, be the set of principal filters on , let be an index set. Consider the filtrator .

**Conjecture**If is a completary multifuncoid of the form , then is a completary multifuncoid of the form .

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:

## Subdivision of a transitive tournament in digraphs with large outdegree. ★★

Author(s): Mader

**Conjecture**For all there is an integer such that every digraph of minimum outdegree at least contains a subdivision of a transitive tournament of order .

Keywords:

## End-Devouring Rays ★

Author(s): Georgakopoulos

**Problem**Let be a graph, a countable end of , and an infinite set of pairwise disjoint -rays in . Prove that there is a set of pairwise disjoint -rays that devours such that the set of starting vertices of rays in equals the set of starting vertices of rays in .

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

## Strong 5-cycle double cover conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

**Conjecture**Let be a circuit in a bridgeless cubic graph . Then there is a five cycle double cover of such that is a subgraph of one of these five cycles.

Keywords: cycle cover

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

## Triangle free strongly regular graphs ★★★

Author(s):

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

Keywords: strongly regular; triangle free

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

## Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let be a finite undirected simple graph.

A *-page book embedding* of consists of a linear order of and a (non-proper) -colouring of such that edges with the same colour do not cross with respect to . That is, if for some edges , then and receive distinct colours.

One can think that the vertices are placed along the spine of a book, and the edges are drawn without crossings on the pages of the book.

The *book thickness* of , denoted by bt is the minimum integer for which there is a -page book embedding of .

Let be the graph obtained by subdividing each edge of exactly once.

**Conjecture**There is a function such that for every graph ,

Keywords: book embedding; book thickness

## Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An *alternating* walk in a digraph is a walk so that the vertex is either the head of both and or the tail of both and for every . A digraph is *universal* if for every pair of edges , there is an alternating walk containing both and

**Question**Does there exist a locally finite highly arc transitive digraph which is universal?

Keywords: arc transitive; digraph

## Chowla's cosine problem ★★★

Author(s): Chowla

**Problem**Let be a set of positive integers and set What is ?

Keywords: circle; cosine polynomial

## 3-Colourability of Arrangements of Great Circles ★★

Author(s): Felsner; Hurtado; Noy; Streinu

Consider a set of great circles on a sphere with no three circles meeting at a point. The arrangement graph of has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.

**Conjecture**Every arrangement graph of a set of great circles is -colourable.

Keywords: arrangement graph; graph coloring

## Edge-Colouring Geometric Complete Graphs ★★

Author(s): Hurtado

**Question**What is the minimum number of colours such that every complete geometric graph on vertices has an edge colouring such that:

- \item[Variant A] crossing edges get distinct colours, \item[Variant B] disjoint edges get distinct colours, \item[Variant C] non-disjoint edges get distinct colours, \item[Variant D] non-crossing edges get distinct colours.

Keywords: geometric complete graph, colouring

## Fat 4-polytopes ★★★

Author(s): Eppstein; Kuperberg; Ziegler

The *fatness* of a 4-polytope is defined to be where is the number of faces of of dimension .

**Question**Does there exist a fixed constant so that every convex 4-polytope has fatness at most ?

## Separators in string graphs ★★

**Conjecture**Every string graph with edges has a separator of size .

Keywords: separator; string graphs

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

## Finite Lattice Representation Problem ★★★★

Author(s):

**Conjecture**

There exists a finite lattice which is not the congruence lattice of a finite algebra.

Keywords: congruence lattice; finite algebra

## Subset-sums equality (pigeonhole version) ★★★

Author(s):

**Problem**Let be natural numbers with . It follows from the pigeon-hole principle that there exist distinct subsets with . Is it possible to find such a pair in polynomial time?

Keywords: polynomial algorithm; search problem

## Barnette's Conjecture ★★★

Author(s): Barnette

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

Keywords: bipartite; cubic; hamiltonian

## Acyclic list colouring of planar graphs. ★★★

Author(s): Borodin; Fon-Der-Flasss; Kostochka; Raspaud; Sopena

**Conjecture**Every planar graph is acyclically 5-choosable.

Keywords:

## Decomposing an even tournament in directed paths. ★★★

Author(s): Alspach; Mason; Pullman

**Conjecture**Every tournament on an even number of vertices can be decomposed into directed paths.

Keywords:

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

## Do any three longest paths in a connected graph have a vertex in common? ★★

Author(s): Gallai

**Conjecture**Do any three longest paths in a connected graph have a vertex in common?

Keywords:

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

## Nonrepetitive colourings of planar graphs ★★

Author(s): Alon N.; Grytczuk J.; Hałuszczak M.; Riordan O.

**Question**Do planar graphs have bounded nonrepetitive chromatic number?

Keywords: nonrepetitive colouring; planar graphs

## Erdős–Straus conjecture ★★

**Conjecture**

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

Keywords: Egyptian fraction

## Few subsequence sums in Z_n x Z_n ★★

**Conjecture**For every , the sequence in consisting of copes of and copies of has the fewest number of distinct subsequence sums over all zero-free sequences from of length .

Keywords: subsequence sum; zero sum

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

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

## Covering a square with unit squares ★★

Author(s):

**Conjecture**For any integer , it is impossible to cover a square of side greater than with unit squares.

Keywords:

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

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

## Consecutive non-orientable embedding obstructions ★★★

Author(s):

**Conjecture**Is there a graph that is a minor-minimal obstruction for two non-orientable surfaces?

## Complexity of the H-factor problem. ★★

An -factor in a graph is a set of vertex-disjoint copies of covering all vertices of .

**Problem**Let be a fixed positive real number and a fixed graph. Is it NP-hard to determine whether a graph on vertices and minimum degree contains and -factor?

Keywords:

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

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

## Friendly partitions ★★

Author(s): DeVos

A *friendly* partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

**Problem**Is it true that for every , all but finitely many -regular graphs have friendly partitions?

## Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

**Conjecture**

- \item If is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph of a locally finite graph is 4-connected, then is hamiltonian.

Keywords: hamiltonian; infinite graph; line graphs