Random

Sums of independent random variables with unbounded variance ★★

Author(s): Feige

Conjecture   If $ X_1, \dotsc, X_n \geq 0 $ are independent random variables with $ \mathbb{E}[X_i] \leq \mu $, then $$\mathrm{Pr} \left( \sum X_i - \mathbb{E} \left[ \sum X_i \right ] < \delta \mu \right) \geq \min \left ( (1 + \delta)^{-1} \delta, e^{-1} \right).$$

Keywords: Inequality; Probability Theory; randomness in TCS

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

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

Characterizing (aleph_0,aleph_1)-graphs ★★★

Author(s): Diestel; Leader

Call a graph an $ (\aleph_0,\aleph_1) $-graph if it has a bipartition $ (A,B) $ so that every vertex in $ A $ has degree $ \aleph_0 $ and every vertex in $ B $ has degree $ \aleph_1 $.

Problem   Characterize the $ (\aleph_0,\aleph_1) $-graphs.

Keywords: binary tree; infinite graph; normal spanning tree; set theory

inverse of an integer matrix ★★

Author(s): Gregory

Question   I've been working on this for a long time and I'm getting nowhere. Could you help me or at least tell me where to look for help. Suppose D is an m-by-m diagonal matrix with integer elements all $ \ge 2 $. Suppose X is an m-by-n integer matrix $ (m \le n) $. Consider the partitioned matrix M = [D X]. Obviously M has full row rank so it has a right inverse of rational numbers. The question is, under what conditions does it have an integer right inverse? My guess, which I can't prove, is that the integers in each row need to be relatively prime.

Keywords: invertable matrices, integer matrices

Exact colorings of graphs ★★

Author(s): Erickson

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

Keywords: graph coloring; ramsey theory

Transversal achievement game on a square grid ★★

Author(s): Erickson

Problem   Two players alternately write O's (first player) and X's (second player) in the unoccupied cells of an $ n \times  n $ grid. The first player (if any) to occupy a set of $ n $ cells having no two cells in the same row or column is the winner. What is the outcome of the game given optimal play?

Keywords: game

Linear-size circuits for stable $0,1 < 2$ sorting? ★★

Author(s): Regan

Problem   Can $ O(n) $-size circuits compute the function $ f $ on $ \{0,1,2\}^* $ defined inductively by $ f(\lambda) = \lambda $, $ f(0x) = 0f(x) $, $ f(1x) = 1f(x) $, and $ f(2x) = f(x)2 $?

Keywords: Circuits; sorting

Vertex Coloring of graph fractional powers ★★★

Author(s): Iradmusa

Conjecture   Let $ G $ be a graph and $ k $ be a positive integer. The $ k- $power of $ G $, denoted by $ G^k $, is defined on the vertex set $ V(G) $, by connecting any two distinct vertices $ x $ and $ y $ with distance at most $ k $. In other words, $ E(G^k)=\{xy:1\leq d_G(x,y)\leq k\} $. Also $ k- $subdivision of $ G $, denoted by $ G^\frac{1}{k} $, is constructed by replacing each edge $ ij $ of $ G $ with a path of length $ k $. Note that for $ k=1 $, we have $ G^\frac{1}{1}=G^1=G $.
Now we can define the fractional power of a graph as follows:
Let $ G $ be a graph and $ m,n\in \mathbb{N} $. The graph $ G^{\frac{m}{n}} $ is defined by the $ m- $power of the $ n- $subdivision of $ G $. In other words $ G^{\frac{m}{n}}\isdef (G^{\frac{1}{n}})^m $.
Conjecture. Let $ G $ be a connected graph with $ \Delta(G)\geq3 $ and $ m $ be a positive integer greater than 1. Then for any positive integer $ n>m $, we have $ \chi(G^{\frac{m}{n}})=\omega(G^\frac{m}{n}) $.
In [1], it was shown that this conjecture is true in some special cases.

Keywords: chromatic number, fractional power of graph, clique number

Are there an infinite number of lucky primes?

Author(s): Lazarus: Gardiner: Metropolis; Ulam

Conjecture   If every second positive integer except 2 is remaining, then every third remaining integer except 3, then every fourth remaining integer etc. , an infinite number of the remaining integers are prime.

Keywords: lucky; prime; seive

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

Problem   Let $ G $ be a perfect graph on $ n $ vertices. Is it true that either $ G $ or $ \bar{G} $ contains a complete bipartite subgraph with bipartition $ (A,B) $ so that $ |A|, |B| \ge n^{1 - o(1)} $?

Keywords: perfect graph

Rota's unimodal conjecture ★★★

Author(s): Rota

Let $ M $ be a matroid of rank $ r $, and for $ 0 \le i \le r $ let $ w_i $ be the number of closed sets of rank $ i $.

Conjecture   $ w_0,w_1,\ldots,w_r $ is unimodal.
Conjecture   $ w_0,w_1,\ldots,w_r $ is log-concave.

Keywords: flat; log-concave; matroid

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

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:

The Crossing Number of the Complete Bipartite Graph ★★★

Author(s): Turan

The crossing number $ cr(G) $ of $ G $ is the minimum number of crossings in all drawings of $ G $ in the plane.

Conjecture   $ \displaystyle   cr(K_{m,n}) = \floor{\frac m2} \floor{\frac {m-1}2}                      \floor{\frac n2} \floor{\frac {n-1}2}  $

Keywords: complete bipartite graph; crossing number

Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

Question   Is every Cayley graph Hamiltonian?

Keywords:

The stubborn list partition problem ★★

Author(s): Cameron; Eschen; Hoang; Sritharan

Problem   Does there exist a polynomial time algorithm which takes as input a graph $ G $ and for every vertex $ v \in V(G) $ a subset $ \ell(v) $ of $ \{1,2,3,4\} $, and decides if there exists a partition of $ V(G) $ into $ \{A_1,A_2,A_3,A_4\} $ so that $ v \in A_i $ only if $ i \in \ell(v) $ and so that $ A_1,A_2 $ are independent, $ A_4 $ is a clique, and there are no edges between $ A_1 $ and $ A_3 $?

Keywords: list partition; polynomial algorithm

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:

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

A homomorphism problem for flows ★★

Author(s): DeVos

Conjecture   Let $ M,M' $ be abelian groups and let $ B \subseteq M $ and $ B' \subseteq M' $ satisfy $ B=-B $ and $ B' = -B' $. If there is a homomorphism from $ Cayley(M,B) $ to $ Cayley(M',B') $, then every graph with a B-flow has a B'-flow.

Keywords: homomorphism; nowhere-zero flow; tension

Unions of triangle free graphs ★★★

Author(s): Erdos; Hajnal

Problem   Does there exist a graph with no subgraph isomorphic to $ K_4 $ which cannot be expressed as a union of $ \aleph_0 $ triangle free graphs?

Keywords: forbidden subgraph; infinite graph; triangle free

Does the chromatic symmetric function distinguish between trees? ★★

Author(s): Stanley

Problem   Do there exist non-isomorphic trees which have the same chromatic symmetric function?

Keywords: chromatic polynomial; symmetric function; tree

MacEachen Conjecture

Author(s): McEachen

Conjecture   Every odd prime number must either be adjacent to, or a prime distance away from a primorial or primorial product.

Keywords: primality; prime distribution

Stable set meeting all longest directed paths. ★★

Author(s): Laborde; Payan; Xuong N.H.

Conjecture   Every digraph has a stable set meeting all longest directed paths

Keywords:

Highly connected graphs with no K_n minor ★★★

Author(s): Thomas

Problem   Is it true for all $ n \ge 0 $, that every sufficiently large $ n $-connected graph without a $ K_n $ minor has a set of $ n-5 $ vertices whose deletion results in a planar graph?

Keywords: connectivity; minor

List chromatic number and maximum degree of bipartite graphs ★★

Author(s): Alon

Conjecture   There is a constant $ c $ such that the list chromatic number of any bipartite graph $ G $ of maximum degree $ \Delta $ is at most $ c \log \Delta $.

Keywords:

Every prism over a 3-connected planar graph is hamiltonian. ★★

Author(s): Kaiser; Král; Rosenfeld; Ryjácek; Voss

Conjecture   If $ G $ is a $ 3 $-connected planar graph, then $ G\square K_2 $ has a Hamilton cycle.

Keywords:

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

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

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:

Slice-ribbon problem ★★★★

Author(s): Fox

Conjecture   Given a knot in $ S^3 $ which is slice, is it a ribbon knot?

Keywords: cobordism; knot; ribbon; slice

Jacobian Conjecture ★★★

Author(s): Keller

Conjecture   Let $ k $ be a field of characteristic zero. A collection $ f_1,\ldots,f_n $ of polynomials in variables $ x_1,\ldots,x_n $ defines an automorphism of $ k^n $ if and only if the Jacobian matrix is a nonzero constant.

Keywords: Affine Geometry; Automorphisms; Polynomials

Minimum number of arc-disjoint transitive subtournaments of order 3 in a tournament ★★

Author(s): Yuster

Conjecture   If $ T $ is a tournament of order $ n $, then it contains $ \left \lceil n(n-1)/6 - n/3\right\rceil $ arc-disjoint transitive subtournaments of order 3.

Keywords:

3-Edge-Coloring Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

Conjecture   Suppose $ G $ with $ |V(G)|>2 $ is a connected cubic graph admitting a $ 3 $-edge coloring. Then there is an edge $ e \in E(G) $ such that the cubic graph homeomorphic to $ G-e $ has a $ 3 $-edge coloring.

Keywords: 3-edge coloring; 4-flow; removable edge

Hilbert-Smith conjecture ★★

Author(s): David Hilbert; Paul A. Smith

Conjecture   Let $ G $ be a locally compact topological group. If $ G $ has a continuous faithful group action on an $ n $-manifold, then $ G $ is a Lie group.

Keywords:

Domination in plane triangulations ★★

Author(s): Matheson; Tarjan

Conjecture   Every sufficiently large plane triangulation $ G $ has a dominating set of size $ \le \frac{1}{4} |V(G)| $.

Keywords: coloring; domination; multigrid; planar graph; triangulation

Unsolvability of word problem for 2-knot complements ★★★

Author(s): Gordon

Problem   Does there exist a smooth/PL embedding of $ S^2 $ in $ S^4 $ such that the fundamental group of the complement has an unsolvable word problem?

Keywords: 2-knot; Computational Complexity; knot theory

Pentagon problem ★★★

Author(s): Nesetril

Question   Let $ G $ be a 3-regular graph that contains no cycle of length shorter than $ g $. Is it true that for large enough~$ g $ there is a homomorphism $ G \to C_5 $?

Keywords: cubic; homomorphism

Distribution and upper bound of mimic numbers ★★

Author(s): Bhattacharyya

Problem  

Let the notation $ a|b $ denote ''$ a $ divides $ b $''. The mimic function in number theory is defined as follows [1].

Definition   For any positive integer $ \mathcal{N} = \sum_{i=0}^{n}\mathcal{X}_{i}\mathcal{M}^{i} $ divisible by $ \mathcal{D} $, the mimic function, $ f(\mathcal{D} | \mathcal{N}) $, is given by,

$$ f(\mathcal{D} | \mathcal{N}) = \sum_{i=0}^{n}\mathcal{X}_{i}(\mathcal{M}-\mathcal{D})^{i} $$

By using this definition of mimic function, the mimic number of any non-prime integer is defined as follows [1].

Definition   The number $ m $ is defined to be the mimic number of any positive integer $ \mathcal{N} = \sum_{i=0}^{n}\mathcal{X}_{i}\mathcal{M}^{i} $, with respect to $ \mathcal{D} $, for the minimum value of which $ f^{m}(\mathcal{D} | \mathcal{N}) = \mathcal{D} $.

Given these two definitions and a positive integer $ \mathcal{D} $, find the distribution of mimic numbers of those numbers divisible by $ \mathcal{D} $.

Again, find whether there is an upper bound of mimic numbers for a set of numbers divisible by any fixed positive integer $ \mathcal{D} $.

Keywords: Divisibility; mimic function; mimic number

Discrete Logarithm Problem ★★★

Author(s):

If $ p $ is prime and $ g,h \in {\mathbb Z}_p^* $, we write $ \log_g(h) = n $ if $ n \in {\mathbb Z} $ satisfies $ g^n =  h $. The problem of finding such an integer $ n $ for a given $ g,h \in {\mathbb Z}^*_p $ (with $ g \neq 1 $) is the Discrete Log Problem.

Conjecture   There does not exist a polynomial time algorithm to solve the Discrete Log Problem.

Keywords: discrete log; NP

Partitionning a tournament into k-strongly connected subtournaments. ★★

Author(s): Thomassen

Problem   Let $ k_1, \dots , k_p $ be positve integer Does there exists an integer $ g(k_1, \dots , k_p) $ such that every $ g(k_1, \dots , k_p) $-strong tournament $ T $ admits a partition $ (V_1\dots , V_p) $ of its vertex set such that the subtournament induced by $ V_i $ is a non-trivial $ k_i $-strong for all $ 1\leq i\leq p $.

Keywords:

Finite entailment of Positive Horn logic ★★

Author(s): Martin

Question   Positive Horn logic (pH) is the fragment of FO involving exactly $ \exists, \forall, \wedge, = $. Does the fragment $ pH \wedge \neg pH $ have the finite model property?

Keywords: entailment; finite satisfiability; horn logic

Bases of many weights ★★★

Author(s): Schrijver; Seymour

Let $ G $ be an (additive) abelian group, and for every $ S \subseteq G $ let $ {\mathit stab}(S) = \{ g \in G : g + S = S \} $.

Conjecture   Let $ M $ be a matroid on $ E $, let $ w : E \rightarrow G $ be a map, put $ S = \{ \sum_{b \in B} w(b) : B \mbox{ is a base} \} $ and $ H = {\mathit stab}(S) $. Then $$|S| \ge |H| \left( 1 - rk(M) + \sum_{Q \in G/H} rk(w^{-1}(Q)) \right).$$

Keywords: matroid; sumset; zero sum

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

Monochromatic empty triangles ★★★

Author(s):

If $ X \subseteq {\mathbb R}^2 $ is a finite set of points which is 2-colored, an empty triangle is a set $ T \subseteq X $ with $ |T|=3 $ so that the convex hull of $ T $ is disjoint from $ X \setminus T $. We say that $ T $ is monochromatic if all points in $ T $ are the same color.

Conjecture   There exists a fixed constant $ c $ with the following property. If $ X \subseteq {\mathbb R}^2 $ is a set of $ n $ points in general position which is 2-colored, then it has $ \ge cn^2 $ monochromatic empty triangles.

Keywords: empty triangle; general position; ramsey theory

Cube-Simplex conjecture ★★★

Author(s): Kalai

Conjecture   For every positive integer $ k $, there exists an integer $ d $ so that every polytope of dimension $ \ge d $ has a $ k $-dimensional face which is either a simplex or is combinatorially isomorphic to a $ k $-dimensional cube.

Keywords: cube; facet; polytope; simplex

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

Problem   What is the maximal possible oriented chromatic number of an oriented planar graph?

Keywords: oriented coloring; oriented graph; planar graph

Almost all non-Hamiltonian 3-regular graphs are 1-connected ★★

Author(s): Haythorpe

Conjecture   Denote by $ NH(n) $ the number of non-Hamiltonian 3-regular graphs of size $ 2n $, and similarly denote by $ NHB(n) $ the number of non-Hamiltonian 3-regular 1-connected graphs of size $ 2n $.

Is it true that $ \lim\limits_{n \rightarrow \infty} \displaystyle\frac{NHB(n)}{NH(n)} = 1 $?

Keywords: Hamiltonian, Bridge, 3-regular, 1-connected

Mapping planar graphs to odd cycles ★★★

Author(s): Jaeger

Conjecture   Every planar graph of girth $ \ge 4k $ has a homomorphism to $ C_{2k+1} $.

Keywords: girth; homomorphism; planar graph

Partitioning edge-connectivity ★★

Author(s): DeVos

Question   Let $ G $ be an $ (a+b+2) $-edge-connected graph. Does there exist a partition $ \{A,B\} $ of $ E(G) $ so that $ (V,A) $ is $ a $-edge-connected and $ (V,B) $ is $ b $-edge-connected?

Keywords: edge-coloring; edge-connectivity