Random

Odd incongruent covering systems ★★★

Author(s): Erdos; Selfridge

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 $ G $ has at most $ k $ edge-disjoint triangles, then there is a set of $ 2k $ edges whose deletion destroys every triangle.

Keywords:

Giuga's Conjecture on Primality ★★

Author(s): Giuseppe Giuga

Conjecture   $ p $ is a prime iff $ ~\displaystyle \sum_{i=1}^{p-1} i^{p-1} \equiv -1 \pmod p $

Keywords: primality

The Hodge Conjecture ★★★★

Author(s): Hodge

Conjecture   Let $ X $ be a complex projective variety. Then every Hodge class is a rational linear combination of the cohomology classes of complex subvarieties of $ X $.

Keywords: Hodge Theory; Millenium Problems

The Berge-Fulkerson conjecture ★★★★

Author(s): Berge; Fulkerson

Conjecture   If $ G $ is a bridgeless cubic graph, then there exist 6 perfect matchings $ M_1,\ldots,M_6 $ of $ G $ with the property that every edge of $ G $ is contained in exactly two of $ M_1,\ldots,M_6 $.

Keywords: cubic; perfect matching

General position subsets ★★

Author(s): Gowers

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

Keywords: general position subset, no-three-in-line problem

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

Author(s): Pach; Tóth

Problem   Does the following equality hold for every graph $ G $? \[ \text{pair-cr}(G) = \text{cr}(G) \]

The crossing number $ \text{cr}(G) $ of a graph $ G $ is the minimum number of edge crossings in any drawing of $ G $ in the plane. In the pairwise crossing number $ \text{pair-cr}(G) $, 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 $ 3 $-connected cubic graph on $ 3k $ vertices admit a partition into $ k $ paths of length $ 2 $?

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 $ {\mathbb F} $ is a finite field with at least 4 elements and $ A $ is an invertible $ n \times n $ matrix with entries in $ {\mathbb F} $, then there are column vectors $ x,y \in {\mathbb F}^n $ which have no coordinates equal to zero such that $ Ax=y $.

Keywords: invertible; nowhere-zero flow

List Hadwiger Conjecture ★★

Author(s): Kawarabayashi; Mohar

Conjecture   Every $ K_t $-minor-free graph is $ c t $-list-colourable for some constant $ c\geq1 $.

Keywords: Hadwiger conjecture; list colouring; minors

Upgrading a completary multifuncoid ★★

Author(s): Porton

Let $ \mho $ be a set, $ \mathfrak{F} $ be the set of filters on $ \mho $ ordered reverse to set-theoretic inclusion, $ \mathfrak{P} $ be the set of principal filters on $ \mho $, let $ n $ be an index set. Consider the filtrator $ \left( \mathfrak{F}^n ; \mathfrak{P}^n \right) $.

Conjecture   If $ f $ is a completary multifuncoid of the form $ \mathfrak{P}^n $, then $ E^{\ast} f $ is a completary multifuncoid of the form $ \mathfrak{F}^n $.

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 $ k $ there is an integer $ f(k) $ such that every digraph of minimum outdegree at least $ f(k) $ contains a subdivision of a transitive tournament of order $ k $.

Keywords:

End-Devouring Rays

Author(s): Georgakopoulos

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

Keywords: end; ray

Splitting a digraph with minimum outdegree constraints ★★★

Author(s): Alon

Problem   Is there a minimum integer $ f(d) $ such that the vertices of any digraph with minimum outdegree $ d $ can be partitioned into two classes so that the minimum outdegree of the subgraph induced by each class is at least $ d $?

Keywords:

Strong 5-cycle double cover conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

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

Keywords: cycle cover

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

Author(s): Charles Pugh

Conjecture   Let $ f\in Diff^{r}(M) $ and $ p\in\omega_{f}  $. Then for any neighborhood $ V_{f}\subset Diff^{r}(M)  $ there is $ g\in V_{f} $ such that $ p $ is periodic point of $ g $

There is an analogous conjecture for flows ( $ C^{r} $ vector fields . In the case of diffeos this was proved by Charles Pugh for $ r = 1 $. In the case of Flows this has been solved by Sushei Hayahshy for $ r = 1 $ . But in the two cases the problem is wide open for $ r > 1 $

Keywords: Dynamics , Pertubation

S(S(f)) = S(f) for reloids ★★

Author(s): Porton

Question   $ S(S(f)) = S(f) $ for every endo-reloid $ f $?

Keywords: reloid

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 $ F $ be a finite family of finite sets, not all empty, that is closed under taking unions. Then there exists $ x $ such that $ x $ is an element of at least half the members of $ F $.

Keywords:

Book Thickness of Subdivisions ★★

Author(s): Blankenship; Oporowski

Let $ G $ be a finite undirected simple graph.

A $ k $-page book embedding of $ G $ consists of a linear order $ \preceq $ of $ V(G) $ and a (non-proper) $ k $-colouring of $ E(G) $ such that edges with the same colour do not cross with respect to $ \preceq $. That is, if $ v\prec x\prec w\prec y $ for some edges $ vw,xy\in E(G) $, then $ vw $ and $ xy $ 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 $ G $, denoted by bt$ (G) $ is the minimum integer $ k $ for which there is a $ k $-page book embedding of $ G $.

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

Conjecture   There is a function $ f $ such that for every graph $ G $, $$   \text{bt}(G) \leq f( \text{bt}(G') )\enspace.   $$

Keywords: book embedding; book thickness

Universal highly arc transitive digraphs ★★★

Author(s): Cameron; Praeger; Wormald

An alternating walk in a digraph is a walk $ v_0,e_1,v_1,\ldots,v_m $ so that the vertex $ v_i $ is either the head of both $ e_i $ and $ e_{i+1} $ or the tail of both $ e_i $ and $ e_{i+1} $ for every $ 1 \le i \le m-1 $. A digraph is universal if for every pair of edges $ e,f $, there is an alternating walk containing both $ e $ and $ f $

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 $ A \subseteq {\mathbb N} $ be a set of $ n $ positive integers and set \[m(A) = - \min_x \sum_{a \in A} \cos(ax).\] What is $ m(n) = \min_A m(A) $?

Keywords: circle; cosine polynomial

3-Colourability of Arrangements of Great Circles ★★

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

Consider a set $ S $ of great circles on a sphere with no three circles meeting at a point. The arrangement graph of $ S $ 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 $ 3 $-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 $ n $ 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 $ P $ is defined to be $ (f_1 + f_2)/(f_0 + f_3) $ where $ f_i $ is the number of faces of $ P $ of dimension $ i $.

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

Keywords: f-vector; polytope

Separators in string graphs ★★

Author(s): Fox; Pach; Tóth

Conjecture   Every string graph with $ m $ edges has a separator of size $ O(\sqrt{m}) $.

Keywords: separator; string graphs

Hamiltonian cycles in powers of infinite graphs ★★

Author(s): Georgakopoulos

Conjecture  
    \item If $ G $ is a countable connected graph then its third power is hamiltonian. \item If $ G $ 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 $ a_1,a_2,\ldots,a_n $ be natural numbers with $ \sum_{i=1}^n a_i < 2^n - 1 $. It follows from the pigeon-hole principle that there exist distinct subsets $ I,J \subseteq \{1,\ldots,n\} $ with $ \sum_{i \in I} a_i = \sum_{j \in J} a_j $. Is it possible to find such a pair $ I,J $ 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 $ D $ on an even number of vertices can be decomposed into $ \sum_{v\in V}\max\{0,d^+(v)-d^-(v)\} $ 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 $ G $ and $ H $, whether there exists a homomorphism from $ G $ to $ H $ in time $ O(c^{|V(G)|+|V(H)|}) $ for some constant $ c $?

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

Author(s): Erdos; Straus

Conjecture  

For all $ n > 2 $, there exist positive integers $ x $, $ y $, $ z $ such that $$1/x + 1/y + 1/z = 4/n$$.

Keywords: Egyptian fraction

Few subsequence sums in Z_n x Z_n ★★

Author(s): Bollobas; Leader

Conjecture   For every $ 0 \le t \le n-1 $, the sequence in $ {\mathbb Z}_n^2 $ consisting of $ n-1 $ copes of $ (1,0) $ and $ t $ copies of $ (0,1) $ has the fewest number of distinct subsequence sums over all zero-free sequences from $ {\mathbb Z}_n^2 $ of length $ n-1+t $.

Keywords: subsequence sum; zero sum

Bounding the chromatic number of triangle-free graphs with fixed maximum degree ★★

Author(s): Kostochka; Reed

Conjecture   A triangle-free graph with maximum degree $ \Delta $ has chromatic number at most $ \ceil{\frac{\Delta}{2}}+2 $.

Keywords: chromatic number; girth; maximum degree; triangle free

Degenerate colorings of planar graphs ★★★

Author(s): Borodin

A graph $ G $ is $ k $-degenerate if every subgraph of $ G $ has a vertex of degree $ \le k $.

Conjecture   Every simple planar graph has a 5-coloring so that for $ 1 \le k \le 4 $, the union of any $ k $ color classes induces a $ (k-1) $-degenerate graph.

Keywords: coloring; degenerate; planar

Covering a square with unit squares ★★

Author(s):

Conjecture   For any integer $ n \geq 1 $, it is impossible to cover a square of side greater than $ n $ with $ n^2+1 $ unit squares.

Keywords:

Blatter-Specker Theorem for ternary relations ★★

Author(s): Makowsky

Let $ C $ be a class of finite relational structures. We denote by $ f_C(n) $ the number of structures in $ C $ over the labeled set $ \{0, \dots, n-1 \} $. For any class $ C $ definable in monadic second-order logic with unary and binary relation symbols, Specker and Blatter showed that, for every $ m \in \mathbb{N} $, the function $ f_C(n) $ is ultimately periodic modulo $ m $.

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 $ R $ be the complete funcoid corresponding to the usual topology on extended real line $ [-\infty,+\infty] = \mathbb{R}\cup\{-\infty,+\infty\} $. Let $ \geq $ be the order on this set. Then $ R\sqcap^{\mathsf{FCD}}\mathord{\geq} $ is a complete funcoid.
Proposition   It is easy to prove that $ \langle R\sqcap^{\mathsf{FCD}}\mathord{\geq}\rangle \{x\} $ is the infinitely small right neighborhood filter of point $ x\in[-\infty,+\infty] $.

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 $ G $ that is a minor-minimal obstruction for two non-orientable surfaces?

Keywords: minor; surface

Complexity of the H-factor problem. ★★

Author(s): Kühn; Osthus

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

Problem  Let $ c $ be a fixed positive real number and $ H $ a fixed graph. Is it NP-hard to determine whether a graph $ G $ on $ n $ vertices and minimum degree $ cn $ contains and $ H $-factor?

Keywords:

A diagram about funcoids and reloids ★★

Author(s): Porton

Define for posets with order $ \sqsubseteq $:

  1. $ \Phi_{\ast} f = \lambda b \in \mathfrak{B}: \bigcup \{ x \in \mathfrak{A} \mid f x \sqsubseteq b \} $;
  2. $ \Phi^{\ast} f = \lambda b \in \mathfrak{A}: \bigcap \{ x \in \mathfrak{B} \mid f x \sqsupseteq b \} $.

Note that the above is a generalization of monotone Galois connections (with $ \max $ and $ \min $ 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 $ \lambda f\in\mathsf{FCD}: \top $.
Question   What repeated applying of $ \Phi_{\ast} $ and $ \Phi^{\ast} $ to "other" leads to? Particularly, does repeated applying $ \Phi_{\ast} $ and/or $ \Phi^{\ast} $ 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 $ {\mathcal O} $ denote the graph with vertex set consisting of all lines through the origin in $ {\mathbb R}^3 $ and two vertices adjacent in $ {\mathcal O} $ if they are perpendicular.

Problem   Is $ \chi_c({\mathcal O}) = 4 $?

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 $ r $, all but finitely many $ r $-regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

Hamiltonian cycles in line graphs of infinite graphs ★★

Author(s): Georgakopoulos

Conjecture  
    \item If $ G $ is a 4-edge-connected locally finite graph, then its line graph is hamiltonian. \item If the line graph $ L(G) $ of a locally finite graph $ G $ is 4-connected, then $ L(G) $ is hamiltonian.

Keywords: hamiltonian; infinite graph; line graphs