Random

Edge-Colouring Geometric Complete Graphs ★★

Author(s): Hurtado

\begin{question} What is the minimum number of colours such that every complete geometric graph on $n$ vertices has an edge colouring such that: \begin{itemize} \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. \end{itemize} \end{question}

Keywords: geometric complete graph, colouring

Continous analogue of Hirsch conjecture ★★

Author(s): Deza; Terlaky; Zinchenko

\begin{conjecture} The order of the largest total curvature of the primal central path over all polytopes defined by $n$ inequalities in dimension $d$ is $n$. \end{conjecture}

Keywords: curvature; polytope

Oriented chromatic number of planar graphs ★★

Author(s):

An oriented colouring of an oriented graph is assignment $c$ of colours to the vertices such that no two arcs receive ordered pairs of colours $(c_1,c_2)$ and $(c_2,c_1)$. It is equivalent to a homomorphism of the digraph onto some tournament of order $k$.

\begin{problem} What is the maximal possible \Def[oriented chromatic number]{Oriented_coloring} of an oriented planar graph? \end{problem}

Keywords: oriented coloring; oriented graph; planar graph

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

Author(s): Pach; Tóth

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

The \Def[crossing number]{Crossing number (graph theory)} $\text{cr}(G)$ of a graph $G$ is the minimum number of edge crossings in any drawing of $G$ in the plane. In the \emph{pairwise crossing number} $\text{pair-cr}(G)$, we minimize the number of pairs of edges that cross. %and the \emph{odd-crossing number} $(\text{odd-cr}(G))$ counts the minimum %number of pairs of edges that cross an odd number of times.

Keywords: crossing number; pair-crossing number

Jaeger's modular orientation conjecture ★★★

Author(s): Jaeger

\begin{conjecture} Every $4k$-\Def[edge-connected]{connectivity (graph theory)} graph can be oriented so that ${\mathit indegree}(v) - {\mathit outdegree}(v) \cong 0$ (mod $2k+1$) for every vertex $v$. \end{conjecture}

Keywords: nowhere-zero flow; orientation

2-colouring a graph without a monochromatic maximum clique ★★

Author(s): Hoang; McDiarmid

\begin{conjecture} If $G$ is a non-empty graph containing no induced odd cycle of length at least $5$, then there is a $2$-vertex colouring of $G$ in which no maximum clique is monochromatic. \end{conjecture}

Keywords: maximum clique; Partitioning

Combinatorial covering designs

Author(s): Gordon; Mills; Rödl; Schönheim

A $(v, k, t)$ \textit{covering design}, or \textit{covering}, is a family of $k$-subsets, called \textit{blocks}, chosen from a $v$-set, such that each $t$-subset is contained in at least one of the blocks. The number of blocks is the covering’s \textit{size}, and the minimum size of such a covering is denoted by $C(v, k, t)$.

\begin{problem} Find a closed form, recurrence, or better bounds for $C(v,k,t)$. Find a procedure for constructing minimal coverings. \end{problem}

Keywords: recreational mathematics

Shuffle-Exchange Conjecture ★★★

Author(s): Beneš; Folklore; Stone

Given integers $k,n\ge2$, let $d(k,n)$ be the smallest integer $d\ge2$ such that the symmetric group $\frak S$ on the set of all words of length $n$ over a $k$-letter alphabet can be generated as $\frak S = (\sigma \frak G)^d$, where $\sigma\in \frak S$ is the \emph{shuffle permutation} defined by $\sigma(x_1 x_2 \dots x_{n}) = x_2 \dots x_{n} x_1$, and $\frak G$ is the \emph{exchange group} consisting of all permutations in $\frak S$ preserving the first $n-1$ letters in the words.

\begin{problem}[SE] Find $d(k,n)$. \end{problem}

\begin{conjecture}[SE] $d(k,n)=2n-1$. \end{conjecture}

Keywords:

Which homology 3-spheres bound homology 4-balls? ★★★★

Author(s): Ancient/folklore

\begin{problem} Is there a complete and computable set of invariants that can determine which (rational) homology $3$-spheres bound (rational) homology $4$-balls? % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. \end{problem}

Keywords: cobordism; homology ball; homology sphere

Every 4-connected toroidal graph has a Hamilton cycle ★★

Author(s): Grunbaum; Nash-Williams

\begin{conjecture} Every 4-connected toroidal graph has a Hamilton cycle. \end{conjecture}

Keywords:

Odd-cycle transversal in triangle-free graphs ★★

Author(s): Erdos; Faudree; Pach; Spencer

\begin{conjecture} If $G$ is a simple triangle-free graph, then there is a set of at most $n^2/25$ edges whose deletion destroys every odd cycle. \end{conjecture}

Keywords:

Total Colouring Conjecture ★★★

Author(s): Behzad

\begin{conjecture} A total coloring of a graph $G = (V,E)$ is an assignment of colors to the vertices and the edges of $G$ such that every pair of adjacent vertices, every pair of adjacent edges and every vertex and incident edge pair, receive different colors. The total chromatic number of a graph $G$, $\chi''(G)$, equals the minimum number of colors needed in a total coloring of $G$. It is an old conjecture of Behzad that for every graph $G$, the total chromatic number equals the maximum degree of a vertex in $G$, $\Delta(G)$ plus one or two. In other words, \[\chi''(G)=\Delta(G)+1\ \ or \ \ \Delta(G)+2.\] \end{conjecture}

Keywords: Total coloring

57-regular Moore graph? ★★★

Author(s): Hoffman; Singleton

\begin{question} Does there exist a 57-\Def[regular]{regular graph} graph with \Def[diameter]{diameter (graph theory)} 2 and \Def{girth} 5? \end{question}

Keywords: cage; Moore graph

Lucas Numbers Modulo m ★★

Author(s):

\begin{conjecture} The sequence {L(n) mod m}, where L(n) are the Lucas numbers, contains a complete residue system modulo m if and only if m is one of the following: 2, 4, 6, 7, 14, 3^k, k >=1. \end{conjecture}

Keywords: Lucas numbers

Petersen coloring conjecture ★★★

Author(s): Jaeger

\begin{conjecture} Let $G$ be a \Def[cubic]{cubic graph} graph with no \Def[bridge]{bridge (graph theory)}. Then there is a coloring of the edges of $G$ using the edges of the \Def[Petersen]{petersen graph} graph so that any three mutually adjacent edges of $G$ map to three mutually adjancent edges in the Petersen graph. \end{conjecture}

Keywords: cubic; edge-coloring; Petersen graph

Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

\begin{question} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. 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$? \end{question}

Keywords: algorithm; Exponential-time algorithm; homomorphism

The robustness of the tensor product ★★★

Author(s): Ben-Sasson; Sudan

\begin{problem} Given two codes $R,C$, their \textbf{Tensor Product} $R \otimes C$ is the code that consists of the matrices whose rows are codewords of $R$ and whose columns are codewords of $C$. The product $R \otimes C$ is said to be \textbf{robust} if whenever a matrix $M$ is far from $R \otimes C$, the rows (columns) of $M$ are far from $R$ ($C$, respectively).

The problem is to give a characterization of the pairs $R,C$ whose tensor product is robust. \end{problem}

Keywords: codes; coding; locally testable; robustness

Inscribed Square Problem ★★

Author(s): Toeplitz

\begin{conjecture} Does every \Def{Jordan curve} have 4 points on it which form the vertices of a square? \end{conjecture}

Keywords: simple closed curve; square

Saturation in the Hypercube ★★

Author(s): Morrison; Noel; Scott

\begin{question} What is the saturation number of cycles of length $2\ell$ in the $d$-dimensional hypercube? \end{question}

Keywords: cycles; hypercube; minimum saturation; saturation

Covering systems with big moduli ★★

Author(s): Erdos; Selfridge

\begin{problem} Does for every integer $N$ exist a \Def{covering system} with all moduli distinct and at least equal to~$N$? \end{problem}

Keywords: covering system

Chromatic Number of Common Graphs ★★

Author(s): Hatami; Hladký; Kráľ; Norine; Razborov

\begin{question} Do common graphs have bounded chromatic number? \end{question}

Keywords: common graph

The large sets conjecture ★★★

Author(s): Brown; Graham; Landman

\begin{conjecture} If $A$ is 2-large, then $A$ is large. \end{conjecture}

Keywords: 2-large sets; large sets

Sum of prime and semiprime conjecture ★★

Author(s): Geoffrey Marnell

\begin{conjecture} Every even number greater than $10$ can be represented as the sum of an odd prime number and an odd \Def {semiprime} . \end{conjecture}

Keywords: prime; semiprime

Approximation ratio for k-outerplanar graphs ★★

Author(s): Bentz

\begin{conjecture} Is the approximation ratio for the \emph{Maximum Edge Disjoint Paths} (MaxEDP) or the \emph{Maximum Integer Multiflow} problem (MaxIMF) bounded by a constant in $k$-outerplanar graphs or tree-width graphs? \end{conjecture}

Keywords: approximation algorithms; planar graph; polynomial algorithm

Direct proof of a theorem about compact funcoids ★★

Author(s): Porton

\begin{conjecture} Let $f$ is a $T_1$-separable (the same as $T_2$ for symmetric transitive) compact funcoid and $g$ is a uniform space (reflexive, symmetric, and transitive endoreloid) such that $( \mathsf{\tmop{FCD}}) g = f$. Then $g = \langle f \times f \rangle^{\ast} \Delta$. \end{conjecture}

The main purpose here is to find a \emph{direct} proof of this conjecture. It seems that this conjecture can be derived from the well known theorem about existence of exactly one uniformity on a compact set. But that would be what I call an indirect proof, we need a direct proof instead.

The direct proof may be constructed by correcting all errors an omissions in \href[this draft article]{http://www.mathematics21.org/binaries/compact.pdf}.

Direct proof could be better because with it we would get a little more general statement like this:

\begin{conjecture} Let $f$ be a $T_1$-separable compact reflexive symmetric funcoid and $g$ be a reloid such that \begin{enumerate} \item $( \mathsf{\tmop{FCD}}) g = f$; \item $g \circ g^{- 1} \sqsubseteq g$. \end{enumerate} Then $g = \langle f \times f \rangle^{\ast} \Delta$. \end{conjecture}

Keywords: compact space; compact topology; funcoid; reloid; uniform space; uniformity

Are all Fermat Numbers square-free? ★★★

Author(s):

\begin{conjecture} Are all Fermat Numbers \[ F_n = 2^{2^{n } } + 1 \] Square-Free?

\end{conjecture}

Keywords:

The Bollobás-Eldridge-Catlin Conjecture on graph packing ★★★

Author(s):

\begin{conjecture}[BEC-conjecture] If $G_1$ and $G_2$ are $n$-vertex graphs and $(\Delta(G_1) + 1) (\Delta(G_2) + 1) < n + 1$, then $G_1$ and $G_2$ pack. \end{conjecture}

Keywords: graph packing

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.

\begin{conjecture} Every arrangement graph of a set of great circles is $3$-colourable. \end{conjecture}

Keywords: arrangement graph; graph coloring

A funcoid related to directed topological spaces ★★

Author(s): Porton

\begin{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. \end{conjecture}

\begin{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]$. \end{proposition}

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

Keywords:

Domination in cubic graphs ★★

Author(s): Reed

\begin{problem} Does every 3-connected cubic graph $G$ satisfy $\gamma(G) \le \lceil |G|/3 \rceil$ ? \end{problem}

Keywords: cubic graph; domination

Cores of strongly regular graphs ★★★

Author(s): Cameron; Kazanidis

\begin{question} Does every \Def{strongly regular graph} have either itself or a complete graph as a \Def[core]{core (graph theory)}? \end{question}

Keywords: core; strongly regular

Smooth 4-dimensional Schoenflies problem ★★★★

Author(s): Alexander

\begin{problem} Let $M$ be a $3$-dimensional smooth submanifold of $S^4$, $M$ diffeomorphic to $S^3$. By the Jordan-Brouwer separation theorem, $M$ separates $S^4$ into the union of two compact connected $4$-manifolds which share $M$ as a common boundary. The Schoenflies problem asks, are these $4$-manifolds diffeomorphic to $D^4$? ie: is $M$ unknotted? \end{problem}

Keywords: 4-dimensional; Schoenflies; sphere

Counting 3-colorings of the hex lattice ★★

Author(s): Thomassen

\begin{problem} Find $\lim_{n \rightarrow \infty} (\chi( H_n , 3)) ^{ 1 / |V(H_n)| }$. \end{problem}

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

Gao's theorem for nonabelian groups ★★

Author(s): DeVos

For every finite multiplicative group $G$, let $s(G)$ ($s'(G)$) denote the smallest integer $m$ so that every sequence of $m$ elements of $G$ has a subsequence of length $>0$ (length $|G|$) which has product equal to 1 in some order.

\begin{conjecture} $s'(G) = s(G) + |G| - 1$ for every finite group $G$. \end{conjecture}

Keywords: subsequence sum; zero sum

4-flow conjecture ★★★

Author(s): Tutte

\begin{conjecture} Every \Def[bridgeless]{bridge (graph theory)} graph with no \Def[Petersen]{petersen graph} \Def[minor]{minor (graph theory)} has a \Def[nowhere-zero]{nowhere-zero flows} 4-flow. \end{conjecture}

Keywords: minor; nowhere-zero flow; Petersen graph

Crossing numbers and coloring ★★★

Author(s): Albertson

We let $cr(G)$ denote the \Def[crossing number]{crossing number (graph theory)} of a graph $G$.

\begin{conjecture} Every graph $G$ with $\chi(G) \ge t$ satisfies $cr(G) \ge cr(K_t)$. \end{conjecture}

Keywords: coloring; complete graph; crossing number

What is the largest graph of positive curvature?

Author(s): DeVos; Mohar

\begin{problem} What is the largest connected \Def{planar graph} of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a \Def[prism]{prism (geometry)} or \Def{antiprism}? \end{problem}

Keywords: curvature; planar graph

Turán's problem for hypergraphs ★★

Author(s): Turan

\begin{conjecture} Every simple $3$-uniform hypergraph on $3n$ vertices which contains no complete $3$-uniform hypergraph on four vertices has at most $\frac12 n^2(5n-3)$ hyperedges. \end{conjecture}

\begin{conjecture} Every simple $3$-uniform hypergraph on $2n$ vertices which contains no complete $3$-uniform hypergraph on five vertices has at most $n^2(n-1)$ hyperedges. \end{conjecture}

Keywords:

End-Devouring Rays

Author(s): Georgakopoulos

\begin{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$. \end{problem}

Keywords: end; ray

Roller Coaster permutations ★★★

Author(s): Ahmed; Snevily

Let $S_n$ denote the set of all permutations of $[n]=\set{1,2,\ldots,n}$. Let $i(\pi)$ and $d(\pi)$ denote respectively the number of increasing and the number of decreasing sequences of contiguous numbers in $\pi$. Let $X(\pi)$ denote the set of subsequences of $\pi$ with length at least three. Let $t(\pi)$ denote $\sum_{\tau\in X(\pi)}(i(\tau)+d(\tau))$.

A permutation $\pi\in S_n$ is called a \emph{Roller Coaster permutation} if $t(\pi)=\max_{\tau\in S_n}t(\tau)$. Let $RC(n)$ be the set of all Roller Coaster permutations in $S_n$.

\begin{conjecture} For $n\geq 3$, \begin{itemize} \item If $n=2k$, then $|RC(n)|=4$. \item If $n=2k+1$, then $|RC(n)|=2^j$ with $j\leq k+1$. \end{itemize} \end{conjecture}

\begin{conjecture}[Odd Sum conjecture] Given $\pi\in RC(n)$, \begin{itemize} \item If $n=2k+1$, then $\pi_j+\pi_{n-j+1}$ is odd for $1\leq j\leq k$. \item If $n=2k$, then $\pi_j + \pi_{n-j+1} = 2k+1$ for all $1\leq j\leq k$. \end{itemize} \end{conjecture}

Keywords:

Exact colorings of graphs ★★

Author(s): Erickson

\begin{conjecture} For $c \geq m \geq 1$, let $P(c,m)$ be the statement that given any exact $c$-coloring of the edges of a complete countably infinite graph (that is, a coloring with $c$ colors all of which must be used at least once), there exists an exactly $m$-colored countably infinite complete subgraph. Then $P(c,m)$ is true if and only if $m=1$, $m=2$, or $c=m$. \end{conjecture}

Keywords: graph coloring; ramsey theory

Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

\begin{question} Is every proper vertex-minor closed class of graphs chi-bounded? \end{question}

Keywords: chi-bounded; circle graph; coloring; vertex minor

Convex 'Fair' Partitions Of Convex Polygons ★★

Author(s): Nandakumar; Ramana

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

\textbf{Definitions:} Define a \emph{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 \emph{Convex Fair Partition}.

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

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

3. Finally, what could one say about \emph{higher dimensional analogs} of this question?

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

Keywords: Convex Polygons; Partitioning

P vs. PSPACE ★★★

Author(s): Folklore

\begin{problem} Is there a problem that can be computed by a Turing machine in polynomial space and unbounded time but not in polynomial time? More formally, does P = PSPACE? \end{problem}

Keywords: P; PSPACE; separation; unconditional

Beneš Conjecture ★★★

Author(s): Beneš

Given a partition $\bf h$ of a finite set $E$, \emph{stabilizer} of $\bf h$, denoted $S(\bf h)$, is the group formed by all permutations of $E$ preserving each block in $\mathbf h$.

\begin{problem}[$\star$] Find a sufficient condition for a sequence of partitions ${\bf h}_1, \dots, {\bf h}_\ell$ of $E$ to be \emph{universal}, i.e. to yield the following decomposition of the symmetric group $\frak S(E)$ on $E$: $$ (1)\quad \frak S(E) = S({\bf h}_1) S({\bf h}_2) \dots S({\bf h}_\ell). $$ In particular, what about the sequence $\bf h,\delta(\bf h),\dots,\delta^{\ell-1}(\bf h)$, where $\delta$ is a permutation of $E$? \end{problem}

\begin{conjecture}[Beneš] Let $\bf u$ be a uniform partition of $E$ and $\varphi$ be a permutation of $E$ such that $\bf u\wedge\varphi(\bf u)=\bf 0$. Suppose that the set $\big(\varphi S({\bf u})\big)^{n}$ is transitive, for some integer $n\ge2$. Then $$ \frak S(E) = \big(\varphi S({\bf u})\big)^{2n-1}. $$ \end{conjecture}

Keywords:

Are almost all graphs determined by their spectrum? ★★★

Author(s):

\begin{problem} Are almost all graphs uniquely determined by the spectrum of their adjacency matrix? \end{problem}

Keywords: cospectral; graph invariant; spectrum

Linear Hypergraphs with Dimension 3 ★★

Author(s): de Fraysseix; Ossona de Mendez; Rosenstiehl

\begin{conjecture} Any linear hypergraph with incidence poset of dimension at most 3 is the intersection hypergraph of a family of triangles and segments in the plane. \end{conjecture}

Keywords: Hypergraphs

Half-integral flow polynomial values ★★

Author(s): Mohar

Let $\Phi(G,x)$ be the flow polynomial of a graph $G$. So for every positive integer $k$, the value $\Phi(G,k)$ equals the number of \Def[nowhere-zero]{nowhere-zero flows} $k$-flows in $G$.

\begin{conjecture} $\Phi(G,5.5) > 0$ for every 2-edge-connected graph $G$. \end{conjecture}

Keywords: nowhere-zero flow

Three-chromatic (0,2)-graphs ★★

Author(s): Payan

\begin{question} Are there any (0,2)-graphs with chromatic number exactly three? \end{question}

Keywords:

Hamilton cycle in small d-diregular graphs ★★

Author(s): Jackson

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

\begin{conjecture} For $d >2$, every $d$-diregular oriented graph on at most $4d+1$ vertices has a Hamilton cycle. \end{conjecture}

Keywords: