Recent Activity

Cycle Double Covers Containing Predefined 2-Regular Subgraphs ★★★

Author(s): Arthur; Hoffmann-Ostenhof

\begin{conjecture} Let $G$ be a $2$-connected cubic graph and let $S$ be a $2$-regular subgraph such that $G-E(S)$ is connected. Then $G$ has a cycle double cover which contains $S$ (i.e all cycles of $S$). \end{conjecture}

Keywords:

Monochromatic reachability in arc-colored digraphs ★★★

Author(s): Sands; Sauer; Woodrow

\begin{conjecture} For every $k$, there exists an integer $f(k)$ such that if $D$ is a digraph whose arcs are colored with $k$ colors, then $D$ has a $S$ set which is the union of $f(k)$ stables sets so that every vertex has a monochromatic path to some vertex in $S$. \end{conjecture}

Keywords:

3-Decomposition Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

\begin{conjecture} (3-Decomposition Conjecture) Every connected cubic graph $G$ has a decomposition into a spanning tree, a family of cycles and a matching. \end{conjecture}

Keywords: cubic graph

Which outer reloids are equal to inner ones ★★

Author(s): Porton

Warning: This formulation is vague (not exact).

\begin{question} Characterize the set $\{f\in\mathsf{FCD} \mid (\mathsf{RLD})_{\mathrm{in}} f=(\mathsf{RLD})_{\mathrm{out}} f\}$. In other words, simplify this formula. \end{question}

The problem seems rather difficult.

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:

\Image{diagram2.png}

What is at the node "other" in the diagram is unknown.

\begin{conjecture} "Other" is $\lambda f\in\mathsf{FCD}: \top$. \end{conjecture}

\begin{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? \end{question}

Keywords: Galois connections

Outward reloid of composition vs composition of outward reloids ★★

Author(s): Porton

\begin{conjecture} For every composable funcoids $f$ and $g$ $$(\mathsf{RLD})_{\mathrm{out}}(g\circ f)\sqsupseteq(\mathsf{RLD})_{\mathrm{out}}g\circ(\mathsf{RLD})_{\mathrm{out}}f.$$ \end{conjecture}

Keywords: outward reloid

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

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:

Infinite distributivity of meet over join for a principal funcoid ★★

Author(s): Porton

\begin{conjecture} $f \sqcap \bigsqcup S = \bigsqcup \langle f \sqcap \rangle^{\ast} S$ for principal funcoid $f$ and a set $S$ of funcoids of appropriate sources and destinations. \end{conjecture}

Keywords: distributivity; principal funcoid

Entourages of a composition of funcoids ★★

Author(s): Porton

\begin{conjecture} $\forall H \in \operatorname{up} (g \circ f) \exists F \in \operatorname{up} f, G \in \operatorname{up} g : H \sqsupseteq G \circ F$ for every composable funcoids $f$ and $g$. \end{conjecture}

Keywords: composition of funcoids; funcoids

Weak saturation of the cube in the clique

Author(s): Morrison; Noel

\begin{problem} % Enter your conjecture in LaTeX % You may change "conjecture" to "question" or "problem" if you prefer. Determine $\text{wsat}(K_n,Q_3)$. \end{problem}

Keywords: bootstrap percolation; hypercube; Weak saturation

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

Turán Problem for $10$-Cycles in the Hypercube ★★

Author(s): Erdos

\begin{problem} Bound the extremal number of $C_{10}$ in the hypercube. \end{problem}

Keywords: cycles; extremal combinatorics; hypercube

Extremal $4$-Neighbour Bootstrap Percolation in the Hypercube ★★

Author(s): Morrison; Noel

\begin{problem} Determine the smallest percolating set for the $4$-neighbour bootstrap process in the hypercube. \end{problem}

Keywords: bootstrap percolation; extremal combinatorics; hypercube; percolation

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

Cycles in Graphs of Large Chromatic Number ★★

Author(s): Brewster; McGuinness; Moore; Noel

\begin{conjecture} If $\chi(G)>k$, then $G$ contains at least $\frac{(k+1)(k-1)!}{2}$ cycles of length $0\bmod k$. \end{conjecture}

Keywords: chromatic number; cycles

The Double Cap Conjecture ★★

Author(s): Kalai

\begin{conjecture} The largest measure of a Lebesgue measurable subset of the unit sphere of $\mathbb{R}^n$ containing no pair of orthogonal vectors is attained by two open caps of geodesic radius $\pi/4$ around the north and south poles. \end{conjecture}

Keywords: combinatorial geometry; independent set; orthogonality; projective plane; sphere

Circular flow numbers of $r$-graphs ★★

Author(s): Steffen

A nowhere-zero $r$-flow $(D(G),\phi)$ on $G$ is an orientation $D$ of $G$ together with a function $\phi$ from the edge set of $G$ into the real numbers such that $1 \leq |\phi(e)| \leq r-1$, for all $e \in E(G)$, and $\sum_{e \in E^+(v)}\phi(e) = \sum_{e \in E^-(v)}\phi(e), \textrm{ for all } v \in V(G)$.

A $(2t+1)$-regular graph $G$ is a $(2t+1)$-graph if $|\partial_G(X)| \geq 2t+1$ for every $X \subseteq V(G)$ with $|X|$ odd.

\begin{conjecture} Let $t > 1$ be an integer. If $G$ is a $(2t+1)$-graph, then $F_c(G) \leq 2 + \frac{2}{t}$. \end{conjecture}

Keywords: flow conjectures; nowhere-zero flows

Circular flow number of regular class 1 graphs ★★

Author(s): Steffen

A nowhere-zero $r$-flow $(D(G),\phi)$ on $G$ is an orientation $D$ of $G$ together with a function $\phi$ from the edge set of $G$ into the real numbers such that $1 \leq |\phi(e)| \leq r-1$, for all $e \in E(G)$, and $\sum_{e \in E^+(v)}\phi(e) = \sum_{e \in E^-(v)}\phi(e), \textrm{ for all } v \in V(G)$. The circular flow number of $G$ is inf$\{ r | G$ has a nowhere-zero $r$-flow $\}$, and it is denoted by $F_c(G)$.

A graph with maximum vertex degree $k$ is a class 1 graph if its edge chromatic number is $k$.

\begin{conjecture} Let $t \geq 1$ be an integer and $G$ a $(2t+1)$-regular graph. If $G$ is a class 1 graph, then $F_c(G) \leq 2 + \frac{2}{t}$. \end{conjecture}

Keywords: nowhere-zero flow, edge-colorings, regular graphs

Chromatic number of associahedron ★★

Author(s): Fabila-Monroy; Flores-Penaloza; Huemer; Hurtado; Urrutia; Wood

\begin{conjecture} Associahedra have unbounded chromatic number. \end{conjecture}

Keywords: associahedron, graph colouring, chromatic number