Recent Activity

Transversal achievement game on a square grid ★★

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

Posted by Martin Erickson
updated January 6th, 2021

3 comments

Graph Theory » Coloring » Labeling

Graceful Tree Conjecture ★★★

Author(s):

Conjecture All trees are graceful

Keywords: combinatorics; graceful labeling

Posted by kintali
updated November 29th, 2020

13 comments

Graph Theory » Extremal G.T.

Extremal problem on the number of tree endomorphism ★★

Author(s): Zhicong Lin

Conjecture An endomorphism of a graph is a mapping on the vertex set of the graph which preserves edges. Among all the $n$ vertices' trees, the star with $n$ vertices has the most endomorphisms, while the path with $n$ vertices has the least endomorphisms.

Keywords:

Posted by shudeshijie
updated November 25th, 2020

3 comments

Graph Theory » Topological G.T. » Coloring

3-Colourability of Arrangements of Great Circles ★★

Author(s): Felsner; Hurtado; Noy; Streinu

Consider a set $S$ of great circles on a sphere with no three circles meeting at a point. The arrangement graph of $S$ has a vertex for each intersection point, and an edge for each arc directly connecting two intersection points. So this arrangement graph is 4-regular and planar.

Conjecture Every arrangement graph of a set of great circles is $3$ -colourable.

Keywords: arrangement graph; graph coloring

Posted by David Wood
updated October 22nd, 2020

2 comments

Probability

KPZ Universality Conjecture ★★★

Author(s):

Conjecture Formulate a central limit theorem for the KPZ universality class.

Keywords: KPZ equation, central limit theorem

Posted by Tomas Kojar
updated October 3rd, 2020

add new comment

Graph Theory » Basic G.T.

Friendly partitions ★★

Author(s): DeVos

A friendly partition of a graph is a partition of the vertices into two sets so that every vertex has at least as many neighbours in its own class as in the other.

Problem Is it true that for every $r$ , all but finitely many $r$ -regular graphs have friendly partitions?

Keywords: edge-cut; partition; regular

Posted by mdevos
updated August 5th, 2020

1 comment

Logic » Finite Model Theory

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

Posted by LucSegoufin
updated June 15th, 2020

1 comment

Graph Theory » Algebraic G.T.

Triangle free strongly regular graphs ★★★

Author(s):

Problem Is there an eighth triangle free strongly regular graph?

Keywords: strongly regular; triangle free

Posted by mdevos
updated May 30th, 2020

4 comments

Number Theory

A discrete iteration related to Pierce expansions ★★

Author(s): Shallit

Conjecture Let $a > b > 0$ be integers. Set $b_1 = b$ and $b_{i+1} = {a \bmod {b_i}}$ for $i \geq 0$ . Eventually we have $b_{n+1} = 0$ ; put $P(a,b) = n$ .

Example: $P(35, 22) = 7$ , since $b_1 = 22$ , $b_2 = 13$ , $b_3 = 9$ , $b_4 = 8$ , $b_5 = 3$ , $b_6 = 2$ , $b_7 = 1$ , $b_8 = 0$ .

Prove or disprove: $P(a,b) = O((\log a)^2)$ .

Keywords: Pierce expansions

Posted by shallit
updated May 30th, 2020

2 comments

Graph Theory » Coloring » Vertex coloring

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

Posted by Andrew King
updated May 16th, 2020

1 comment

Graph Theory » Coloring » Vertex coloring

Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

Conjecture If $G,H$ are simple finite graphs, then $\chi(G \times H) = \min \{ \chi(G), \chi(H) \}$ .

Here $G \times H$ is the tensor product (also called the direct or categorical product) of $G$ and $H$ .

Keywords: categorical product; coloring; homomorphism; tensor product

Posted by mdevos
updated March 1st, 2020

5 comments

Number Theory

Diophantine quintuple conjecture ★★

Author(s):

Definition A set of m positive integers $\{a_1, a_2, \dots, a_m\}$ is called a Diophantine $m$ -tuple if $a_i\cdot a_j + 1$ is a perfect square for all $1 \leq i < j \leq m$ .

Conjecture (1) Diophantine quintuple does not exist.

It would follow from the following stronger conjecture [Da]:

Conjecture (2) If $\{a, b, c, d\}$ is a Diophantine quadruple and $d > \max \{a, b, c\}$ , then $d = a + b + c + 2bc + 2\sqrt{(ab+1)(ac+1)(bc+1)}.$

Keywords:

Posted by maxal
updated February 25th, 2020

1 comment

Topology

Several ways to apply a (multivalued) multiargument function to a family of filters ★★★

Author(s): Porton

Problem Let $\mathcal{X}$ be an indexed family of filters on sets. Which of the below items are always pairwise equal?

1. The funcoid corresponding to this function (considered as a single argument function on indexed families) applied to the reloidal product of filters $\mathcal{X}$ .

2. The funcoid corresponding to this function (considered as a single argument function on indexed families) applied to the starred reloidal product of filters $\mathcal{X}$ .

3. $\bigcap_{F\in\operatorname{up}^{\mathrm{FCD}}\prod^{\mathrm{Strd}}\mathcal{X}}\langle f \rangle F$ .

Keywords: funcoid; function; multifuncoid; staroid

Posted by porton
updated January 15th, 2020

2 comments

Graph Theory » Basic G.T. » Cycles

Jones' conjecture ★★

Author(s): Kloks; Lee; Liu

For a graph $G$ , let $cp(G)$ denote the cardinality of a maximum cycle packing (collection of vertex disjoint cycles) and let $cc(G)$ denote the cardinality of a minimum feedback vertex set (set of vertices $X$ so that $G-X$ is acyclic).

Conjecture For every planar graph $G$ , $cc(G)\leq 2cp(G)$ .

Keywords: cycle packing; feedback vertex set; planar graph

Posted by cmlee
updated December 5th, 2019

3 comments

Graph Theory » Extremal G.T.

Multicolour Erdős--Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

Conjecture For every fixed $k\geq2$ and fixed colouring $\chi$ of $E(K_k)$ with $m$ colours, there exists $\varepsilon>0$ such that every colouring of the edges of $K_n$ contains either $k$ vertices whose edges are coloured according to $\chi$ or $n^\varepsilon$ vertices whose edges are coloured with at most $m-1$ colours.

Keywords: ramsey theory

Posted by Jon Noel
updated October 10th, 2019

add new comment

Graph Theory

Sidorenko's Conjecture ★★★

Author(s): Sidorenko

Conjecture For any bipartite graph $H$ and graph $G$ , the number of homomorphisms from $H$ to $G$ is at least $\left(\frac{2|E(G)|}{|V(G)|^2}\right)^{|E(H)|}|V(G)|^{|V(H)|}$ .

Keywords: density problems; extremal combinatorics; homomorphism

Posted by Jon Noel
updated October 10th, 2019

add new comment

Geometry

Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

Conjecture Every convex polyhedron has a (nonoverlapping) edge unfolding.

Keywords: folding; nets

Posted by Erik Demaine
updated June 18th, 2019

add new comment

Geometry

Point sets with no empty pentagon ★

Author(s): Wood

Problem Classify the point sets with no empty pentagon.

Keywords: combinatorial geometry; visibility graph

Posted by David Wood
updated March 25th, 2019

2 comments

Number Theory » Combinatorial N.T.

Singmaster's conjecture ★★

Author(s): Singmaster

Conjecture There is a finite upper bound on the multiplicities of entries in Pascal's triangle, other than the number $1$ .

The number $2$ appears once in Pascal's triangle, $3$ appears twice, $6$ appears three times, and $10$ appears $4$ times. There are infinite families of numbers known to appear $6$ times. The only number known to appear $8$ times is $3003$ . It is not known whether any number appears more than $8$ times. The conjectured upper bound could be $8$ ; Singmaster thought it might be $10$ or $12$ . See Singmaster's conjecture.

Keywords: Pascal's triangle

Posted by Zach Teitler
updated March 15th, 2019

add new comment

Algebra

Waring rank of determinant ★★

Author(s): Teitler

Question What is the Waring rank of the determinant of a $d \times d$ generic matrix?

For simplicity say we work over the complex numbers. The $d \times d$ generic matrix is the matrix with entries $x_{i,j}$ for $1 \leq i,j \leq d$ . Its determinant is a homogeneous form of degree $d$ , in $d^2$ variables. If $F$ is a homogeneous form of degree $d$ , a power sum expression for $F$ is an expression of the form $F = \ell_1^d+\dotsb+\ell_r^d$ , the $\ell_i$ (homogeneous) linear forms. The Waring rank of $F$ is the least number of terms $r$ in any power sum expression for $F$ . For example, the expression $xy = \frac{1}{4}(x+y)^2 - \frac{1}{4}(x-y)^2$ means that $xy$ has Waring rank $2$ (it can't be less than $2$ , as $xy \neq \ell_1^2$ ).

The $2 \times 2$ generic determinant $x_{1,1}x_{2,2}-x_{1,2}x_{2,1}$ (or $ad-bc$ ) has Waring rank $4$ . The Waring rank of the $3 \times 3$ generic determinant is at least $14$ and no more than $20$ , see for instance Lower bound for ranks of invariant forms, Example 4.1. The Waring rank of the permanent is also of interest. The comparison between the determinant and permanent is potentially relevant to Valiant's "VP versus VNP" problem.