# Recent Activity

## Hedetniemi's Conjecture ★★★

Author(s): Hedetniemi

**Conjecture**If are simple finite graphs, then .

Here is the tensor product (also called the direct or categorical product) of and .

Keywords: categorical product; coloring; homomorphism; tensor product

## Diophantine quintuple conjecture ★★

Author(s):

**Definition**A set of m positive integers is called a Diophantine -tuple if is a perfect square for all .

**Conjecture (1)**Diophantine quintuple does not exist.

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

**Conjecture (2)**If is a Diophantine quadruple and , then

Keywords:

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

Author(s): Porton

**Problem**Let 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 .

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

3. .

Keywords: funcoid; function; multifuncoid; staroid

## Jones' conjecture ★★

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

**Conjecture**For every planar graph , .

Keywords: cycle packing; feedback vertex set; planar graph

## Multicolour Erdős--Hajnal Conjecture ★★★

**Conjecture**For every fixed and fixed colouring of with colours, there exists such that every colouring of the edges of contains either vertices whose edges are coloured according to or vertices whose edges are coloured with at most colours.

Keywords: ramsey theory

## Sidorenko's Conjecture ★★★

Author(s): Sidorenko

**Conjecture**For any bipartite graph and graph , the number of homomorphisms from to is at least .

Keywords: density problems; extremal combinatorics; homomorphism

## Edge-Unfolding Convex Polyhedra ★★

Author(s): Shephard

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

## Point sets with no empty pentagon ★

Author(s): Wood

**Problem**Classify the point sets with no empty pentagon.

Keywords: combinatorial geometry; visibility graph

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

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

Keywords: Pascal's triangle

## Waring rank of determinant ★★

Author(s): Teitler

**Question**What is the Waring rank of the determinant of a generic matrix?

For simplicity say we work over the complex numbers. The generic matrix is the matrix with entries for . Its determinant is a homogeneous form of degree , in variables. If is a homogeneous form of degree , a power sum expression for is an expression of the form , the (homogeneous) linear forms. The Waring rank of is the least number of terms in any power sum expression for . For example, the expression means that has Waring rank (it can't be less than , as ).

The generic determinant (or ) has Waring rank . The Waring rank of the generic determinant is at least and no more than , 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.

Keywords: Waring rank, determinant

## Monochromatic vertex colorings inherited from Perfect Matchings ★★★

Author(s):

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

Keywords:

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

Author(s): Arthur; Hoffmann-Ostenhof

**Conjecture**Let be a -connected cubic graph and let be a -regular subgraph such that is connected. Then has a cycle double cover which contains (i.e all cycles of ).

Keywords:

## Monochromatic reachability in arc-colored digraphs ★★★

Author(s): Sands; Sauer; Woodrow

**Conjecture**For every , there exists an integer such that if is a digraph whose arcs are colored with colors, then has a set which is the union of stables sets so that every vertex has a monochromatic path to some vertex in .

Keywords:

## 3-Decomposition Conjecture ★★★

Author(s): Arthur; Hoffmann-Ostenhof

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

Keywords: cubic graph

## Which outer reloids are equal to inner ones ★★

Author(s): Porton

Warning: This formulation is vague (not exact).

**Question**Characterize the set . In other words, simplify this formula.

The problem seems rather difficult.

Keywords:

## A diagram about funcoids and reloids ★★

Author(s): Porton

Define for posets with order :

- ;
- .

Note that the above is a generalization of monotone Galois connections (with and 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 .

**Question**What repeated applying of and to "other" leads to? Particularly, does repeated applying and/or to the node "other" lead to finite or infinite sets?

Keywords: Galois connections

## Outward reloid of composition vs composition of outward reloids ★★

Author(s): Porton

**Conjecture**For every composable funcoids and

Keywords: outward reloid

## Sum of prime and semiprime conjecture ★★

Author(s): Geoffrey Marnell

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

## A funcoid related to directed topological spaces ★★

Author(s): Porton

**Conjecture**Let be the complete funcoid corresponding to the usual topology on extended real line . Let be the order on this set. Then is a complete funcoid.

**Proposition**It is easy to prove that is the infinitely small right neighborhood filter of point .

If proved true, the conjecture then can be generalized to a wider class of posets.

Keywords:

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

Author(s): Porton

**Conjecture**for principal funcoid and a set of funcoids of appropriate sources and destinations.

Keywords: distributivity; principal funcoid