Recent Activity

Obstacle number of planar graphs

Author(s): Alpert; Koch; Laison

Does there exist a planar graph with obstacle number greater than 1? Is there some $ k $ such that every planar graph has obstacle number at most $ k $?

Keywords: graph drawing; obstacle number; planar graph; visibility graph

Twin prime conjecture ★★★★

Author(s):

Conjecture   There exist infinitely many positive integers $ n $ so that both $ n $ and $ n+2 $ are prime.

Keywords: prime; twin prime

Cores of strongly regular graphs ★★★

Author(s): Cameron; Kazanidis

Question   Does every strongly regular graph have either itself or a complete graph as a core?

Keywords: core; strongly regular

Square achievement game on an n x n 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 four cells at the vertices of a square with horizontal and vertical sides is the winner. What is the outcome of the game given optimal play? Note: Roland Bacher and Shalom Eliahou proved that every 15 x 15 binary matrix contains four equal entries (all 0's or all 1's) at the vertices of a square with horizontal and vertical sides. So the game must result in a winner (the first player) when n=15.

Keywords: game

What is the largest graph of positive curvature?

Author(s): DeVos; Mohar

Problem   What is the largest connected planar graph of minimum degree 3 which has everywhere positive combinatorial curvature, but is not a prism or antiprism?

Keywords: curvature; planar graph

Extension complexity of (convex) polygons ★★

Author(s):

The extension complexity of a polytope $ P $ is the minimum number $ q $ for which there exists a polytope $ Q $ with $ q $ facets and an affine mapping $ \pi $ with $ \pi(Q) = P $.

Question   Does there exists, for infinitely many integers $ n $, a convex polygon on $ n $ vertices whose extension complexity is $ \Omega(n) $?

Keywords: polytope, projection, extension complexity, convex polygon

Strict inequalities for products of filters

Author(s): Porton

Conjecture   $ \mathcal{A} \times^{\mathsf{\ensuremath{\operatorname{RLD}}}}_F \mathcal{B}   \subset \mathcal{A} \ltimes \mathcal{B} \subset \mathcal{A}   \times^{\mathsf{\ensuremath{\operatorname{RLD}}}} \mathcal{B} $ for some filter objects $ \mathcal{A} $, $ \mathcal{B} $. Particularly, is this formula true for $ \mathcal{A} = \mathcal{B} = \Delta \cap \uparrow^{\mathbb{R}} \left( 0 ; +   \infty \right) $?

A weaker conjecture:

Conjecture   $ \mathcal{A} \times^{\mathsf{\ensuremath{\operatorname{RLD}}}}_F \mathcal{B}   \subset \mathcal{A} \ltimes \mathcal{B} $ for some filter objects $ \mathcal{A} $, $ \mathcal{B} $.

Keywords: filter products

Barnette's Conjecture ★★★

Author(s): Barnette

Conjecture   Every 3-connected cubic planar bipartite graph is Hamiltonian.

Keywords: bipartite; cubic; hamiltonian

Covering a square with unit squares ★★

Author(s):

Conjecture   For any integer $ n \geq 1 $, it is impossible to cover a square of side greater than $ n $ with $ n^2+1 $ unit squares.

Keywords:

Sequence defined on multisets ★★

Author(s): Erickson

Conjecture   Define a $ 2 \times n $ array of positive integers where the first row consists of some distinct positive integers arranged in increasing order, and the second row consists of any positive integers in any order. Create a new array where the first row consists of all the integers that occur in the first array, arranged in increasing order, and the second row consists of their multiplicities. Repeat the process. For example, starting with the array $ [1; 1] $, the sequence is: $ [1; 1] $ -> $ [1; 2] $ -> $ [1, 2; 1, 1] $ -> $ [1, 2; 3, 1] $ -> $ [1, 2, 3; 2, 1, 1] $ -> $ [1, 2, 3; 3, 2, 1] $ -> $ [1, 2, 3; 2, 2, 2] $ -> $ [1, 2, 3; 1, 4, 1] $ -> $ [1, 2, 3, 4; 3, 1, 1, 1] $ -> $ [1, 2, 3, 4; 4, 1, 2, 1] $ -> $ [1, 2, 3, 4; 3, 2, 1, 2] $ -> $ [1, 2, 3, 4; 2, 3, 2, 1] $, and we now have a fixed point (loop of one array).

The process always results in a loop of 1, 2, or 3 arrays.

Keywords: multiset; sequence

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

Covering powers of cycles with equivalence subgraphs

Author(s):

Conjecture   Given $ k $ and $ n $, the graph $ C_{n}^k $ has equivalence covering number $ \Omega(k) $.

Keywords:

Complexity of square-root sum ★★

Author(s): Goemans

Question   What is the complexity of the following problem?

Given $ a_1,\dots,a_n; k $, determine whether or not $  \sum_i \sqrt{a_i} \leq k.  $

Keywords: semi-definite programming

Snevily's conjecture ★★★

Author(s): Snevily

Conjecture   Let $ G $ be an abelian group of odd order and let $ A,B \subseteq G $ satisfy $ |A| = |B| = k $. Then the elements of $ A $ and $ B $ may be ordered $ A = \{a_1,\ldots,a_k\} $ and $ B = \{b_1,\ldots,b_k\} $ so that the sums $ a_1+b_1, a_2+b_2 \ldots, a_k + b_k $ are pairwise distinct.

Keywords: addition table; latin square; transversal

Primitive pythagorean n-tuple tree ★★

Author(s):

Conjecture   Find linear transformation construction of primitive pythagorean n-tuple tree!

Keywords:

3-flow conjecture ★★★

Author(s): Tutte

Conjecture   Every 4-edge-connected graph has a nowhere-zero 3-flow.

Keywords: nowhere-zero flow

Invariant subspace problem ★★★

Author(s):

Problem   Does every bounded linear operator on an infinite-dimensional separable Hilbert space have a non-trivial closed invariant subspace?

Keywords: subspace

Sets with distinct subset sums ★★★

Author(s): Erdos

Say that a set $ S \subseteq {\mathbb Z} $ has distinct subset sums if distinct subsets of $ S $ have distinct sums.

Conjecture   There exists a fixed constant $ c $ so that $ |S| \le \log_2(n) + c $ whenever $ S \subseteq \{1,2,\ldots,n\} $ has distinct subset sums.

Keywords: subset sum

Seymour's Second Neighbourhood Conjecture ★★★

Author(s): Seymour

Conjecture   Any oriented graph has a vertex whose outdegree is at most its second outdegree.

Keywords: Caccetta-Häggkvist; neighbourhood; second; Seymour

Which lattices occur as intervals in subgroup lattices of finite groups? ★★★★

Author(s):

Conjecture  

There exists a finite lattice that is not an interval in the subgroup lattice of a finite group.

Keywords: congruence lattice; finite groups