Home

Recent Activity

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
Number Theory » Analytic N.T.

Are there infinite number of Mersenne Primes? ★★★★

Author(s):

Conjecture   A Mersenne prime is a Mersenne number \[ M_n = 2^p - 1 \] that is prime.

Are there infinite number of Mersenne Primes?

Keywords: Mersenne number; Mersenne prime

Posted by kurtulmehtap
updated February 4th, 2015
add new comment
Number Theory » Analytic N.T.

Are all Mersenne Numbers with prime exponent square-free? ★★★

Author(s):

Conjecture   Are all Mersenne Numbers with prime exponent $ {2^p-1} $ Square free?

Keywords: Mersenne number

Posted by kurtulmehtap
updated February 4th, 2015
add new comment
Topology

What are hyperfuncoids isomorphic to? ★★

Author(s): Porton

Let $ \mathfrak{A} $ be an indexed family of sets.

Products are $ \prod A $ for $ A \in \prod \mathfrak{A} $.

Hyperfuncoids are filters $ \mathfrak{F} \Gamma $ on the lattice $ \Gamma $ of all finite unions of products.

Problem   Is $ \bigcap^{\mathsf{\tmop{FCD}}} $ a bijection from hyperfuncoids $ \mathfrak{F} \Gamma $ to:
    \item prestaroids on $ \mathfrak{A} $; \item staroids on $ \mathfrak{A} $; \item completary staroids on $ \mathfrak{A} $?

If yes, is $ \operatorname{up}^{\Gamma} $ defining the inverse bijection? If not, characterize the image of the function $ \bigcap^{\mathsf{\tmop{FCD}}} $ defined on $ \mathfrak{F} \Gamma $.

Consider also the variant of this problem with the set $ \Gamma $ replaced with the set $ \Gamma^{\ast} $ of complements of elements of the set $ \Gamma $.

Keywords: hyperfuncoids; multidimensional

Posted by porton
updated December 9th, 2014
add new comment
Topology

Another conjecture about reloids and funcoids ★★

Author(s): Porton

Definition   $ \square f = \bigcap^{\mathsf{RLD}} \mathrm{up}^{\Gamma (\operatorname{Src} f ; \operatorname{Dst} f)} f $ for reloid $ f $.
Conjecture   $ (\mathsf{RLD})_{\Gamma} f = \square (\mathsf{RLD})_{\mathrm{in}} f $ for every funcoid $ f $.

Note: it is known that $ (\mathsf{RLD})_{\Gamma} f \ne \square (\mathsf{RLD})_{\mathrm{out}} f $ (see below mentioned online article).

Keywords:

Posted by porton
updated November 28th, 2014
add new comment
Analysis

Inequality for square summable complex series ★★

Author(s): Retkes

Conjecture   For all $ \alpha=(\alpha_1,\alpha_2,\ldots)\in l_2(\cal{C}) $ the following inequality holds $$\sum_{n\geq 1}|\alpha_n|^2\geq \frac{6}{\pi^2}\sum_{k\geq0}\bigg| \sum_{l\geq0}\frac{1}{l+1}\alpha_{2^k(2l+1)}\bigg|^2 $$

Keywords: Inequality

Posted by tigris35711
updated October 29th, 2014
2 comments
Theoretical Comp. Sci. » Complexity

One-way functions exist ★★★★

Author(s):

Conjecture   One-way functions exist.

Keywords: one way function

Posted by porton
updated October 12th, 2014
add new comment
Graph Theory

Chromatic Number of Common Graphs ★★

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

Question   Do common graphs have bounded chromatic number?

Keywords: common graph

Posted by David Wood
updated August 15th, 2014
add new comment
Number Theory

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

Posted by ACW
updated July 14th, 2014
4 comments
Number Theory » Combinatorial N.T.

The 3n+1 conjecture ★★★

Author(s): Collatz

Conjecture   Let $ f(n) = 3n+1 $ if $ n $ is odd and $ \frac{n}{2} $ if $ n $ is even. Let $ f(1) = 1 $. Assume we start with some number $ n $ and repeatedly take the $ f $ of the current number. Prove that no matter what the initial number is we eventually reach $ 1 $.

Keywords: integer sequence

Posted by dododododo
updated July 11th, 2014
4 comments
Graph Theory » Coloring » Vertex coloring

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

Posted by David Wood
updated July 7th, 2014
add new comment
Number Theory

Lucas Numbers Modulo m ★★

Author(s):

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.

Keywords: Lucas numbers

Posted by Martin Erickson
updated July 1st, 2014
1 comment
Number Theory » Combinatorial N.T.

Divisibility of central binomial coefficients ★★

Author(s): Graham

Problem  (1)   Prove that there exist infinitely many positive integers $ n $ such that $$\gcd({2n\choose n}, 3\cdot 5\cdot 7) = 1.$$
Problem  (2)   Prove that there exists only a finite number of positive integers $ n $ such that $$\gcd({2n\choose n}, 3\cdot 5\cdot 7\cdot 11) = 1.$$

Keywords:

Posted by maxal
updated June 29th, 2014
5 comments
Graph Theory » Hypergraphs

¿Are critical k-forests tight? ★★

Author(s): Strausz

Conjecture  

Let $ H $ be a $ k $-uniform hypergraph. If $ H $ is a critical $ k $-forest, then it is a $ k $-tree.

Keywords: heterochromatic number

Posted by Dino
updated May 5th, 2014
1 comment
Combinatorics » Posets

Saturated $k$-Sperner Systems of Minimum Size ★★

Author(s): Morrison; Noel; Scott

Question   Does there exist a constant $ c>1/2 $ and a function $ n_0(k) $ such that if $ |X|\geq n_0(k) $, then every saturated $ k $-Sperner system $ \mathcal{F}\subseteq \mathcal{P}(X) $ has cardinality at least $ 2^{(1+o(1))ck} $?

Keywords: antichain; extremal combinatorics; minimum saturation; saturation; Sperner system

Posted by Jon Noel
updated April 12th, 2014
add new comment
Graph Theory » Coloring » Vertex coloring

List Colourings of Complete Multipartite Graphs with 2 Big Parts ★★

Author(s): Allagan

Question   Given $ a,b\geq2 $, what is the smallest integer $ t\geq0 $ such that $ \chi_\ell(K_{a,b}+K_t)= \chi(K_{a,b}+K_t) $?

Keywords: complete bipartite graph; complete multipartite graph; list coloring

Posted by Jon Noel
updated April 12th, 2014
add new comment
Geometry

Generalised Empty Hexagon Conjecture ★★

Author(s): Wood

Conjecture   For each $ \ell\geq3 $ there is an integer $ f(\ell) $ such that every set of at least $ f(\ell) $ points in the plane contains $ \ell $ collinear points or an empty hexagon.

Keywords: empty hexagon

Posted by David Wood
updated March 26th, 2014
add new comment
Geometry

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

Posted by David Wood
updated March 24th, 2014
add new comment