Home

Recent Activity

Graph Theory

Monochromatic vertex colorings inherited from Perfect Matchings ★★★

Author(s):

Conjecture   For which values of $ n $ and $ d $ are there bi-colored graphs on $ n $ vertices and $ d $ different colors with the property that all the $ d $ monochromatic colorings have unit weight, and every other coloring cancels out?

Keywords:

Posted by Mario Krenn
updated March 4th, 2019
add new comment
Graph Theory

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

Author(s): Arthur; Hoffmann-Ostenhof

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 $).

Keywords:

Posted by arthur
updated June 21st, 2017
add new comment
Graph Theory » Directed Graphs

Monochromatic reachability in arc-colored digraphs ★★★

Author(s): Sands; Sauer; Woodrow

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 $.

Keywords:

Posted by fhavet
updated April 4th, 2017
add new comment
Graph Theory

3-Decomposition Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

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

Keywords: cubic graph

Posted by arthur
updated January 24th, 2017
add new comment
Topology

Which outer reloids are equal to inner ones ★★

Author(s): Porton

Warning: This formulation is vague (not exact).

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.

The problem seems rather difficult.

Keywords:

Posted by porton
updated December 1st, 2016
add new comment
Topology

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

Posted by porton
updated November 29th, 2016
2 comments | 2 attachments
Topology

Outward reloid of composition vs composition of outward reloids ★★

Author(s): Porton

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.$$

Keywords: outward reloid

Posted by porton
updated September 10th, 2016
add new comment
Number Theory

Sum of prime and semiprime conjecture ★★

Author(s): Geoffrey Marnell

Conjecture   Every even number greater than $ 10 $ can be represented as the sum of an odd prime number and an odd semiprime .

Keywords: prime; semiprime

Posted by princeps
updated July 31st, 2016
2 comments
Topology

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:

Posted by porton
updated July 28th, 2016
add new comment
Topology

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

Author(s): Porton

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.

Keywords: distributivity; principal funcoid

Posted by porton
updated July 27th, 2016
add new comment
Graph Theory » Extremal G.T.

Weak saturation of the cube in the clique ★

Author(s): Morrison; Noel

Problem  

Determine $ \text{wsat}(K_n,Q_3) $.

Keywords: bootstrap percolation; hypercube; Weak saturation

Posted by Jon Noel
updated April 6th, 2016
add new comment
Geometry

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

Posted by Nandakumar
updated October 22nd, 2015
add new comment
Combinatorics

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

Author(s): Erdos

Problem   Bound the extremal number of $ C_{10} $ in the hypercube.

Keywords: cycles; extremal combinatorics; hypercube

Posted by Jon Noel
updated September 20th, 2015
add new comment
Combinatorics

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

Author(s): Morrison; Noel

Problem   Determine the smallest percolating set for the $ 4 $-neighbour bootstrap process in the hypercube.

Keywords: bootstrap percolation; extremal combinatorics; hypercube; percolation

Posted by Jon Noel
updated September 20th, 2015
add new comment
Combinatorics

Saturation in the Hypercube ★★

Author(s): Morrison; Noel; Scott

Question   What is the saturation number of cycles of length $ 2\ell $ in the $ d $-dimensional hypercube?

Keywords: cycles; hypercube; minimum saturation; saturation

Posted by Jon Noel
updated September 20th, 2015
add new comment
Graph Theory » Coloring » Vertex coloring

Cycles in Graphs of Large Chromatic Number ★★

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

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

Keywords: chromatic number; cycles

Posted by Jon Noel
updated September 20th, 2015
add new comment
Combinatorics

The Double Cap Conjecture ★★

Author(s): Kalai

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.

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

Posted by Jon Noel
updated September 15th, 2015
add new comment
Graph Theory

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.

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

Keywords: flow conjectures; nowhere-zero flows

Posted by Eckhard Steffen
updated August 6th, 2015
add new comment
Graph Theory » Coloring » 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 $.

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} $.

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

Posted by Eckhard Steffen
updated August 5th, 2015
add new comment
Geometry

Chromatic number of associahedron ★★

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

Conjecture   Associahedra have unbounded chromatic number.

Keywords: associahedron, graph colouring, chromatic number

Posted by David Wood
updated June 2nd, 2015
add new comment