# Recent Activity

## trace inequality ★★

Author(s):

Let be positive semidefinite, by Jensen's inequality, it is easy to see , whenever .

What about the , is it still valid?

Keywords:

## Real roots of the flow polynomial ★★

Author(s): Welsh

Conjecture   All real roots of nonzero flow polynomials are at most 4.

Keywords: flow polynomial; nowhere-zero flow

## Hamiltonicity of Cayley graphs ★★★

Author(s): Rapaport-Strasser

Question   Is every Cayley graph Hamiltonian?

Keywords:

## Finite Lattice Representation Problem ★★★★

Author(s):

Conjecture

There exists a finite lattice which is not the congruence lattice of a finite algebra.

Keywords: congruence lattice; finite algebra

## Outer reloid of restricted funcoid ★★

Author(s): Porton

Question   for every filter objects and and a funcoid ?

Keywords: direct product of filters; outer reloid

## Star chromatic index of complete graphs ★★

Author(s): Dvorak; Mohar; Samal

Conjecture   Is it possible to color edges of the complete graph using colors, so that the coloring is proper and no 4-cycle and no 4-edge path is using only two colors?

Equivalently: is the star chromatic index of linear in ?

Keywords: complete graph; edge coloring; star coloring

## Star chromatic index of cubic graphs ★★

Author(s): Dvorak; Mohar; Samal

The star chromatic index of a graph is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored.

Question   Is it true that for every (sub)cubic graph , we have ?

Keywords: edge coloring; star coloring

## Inscribed Square Problem ★★

Author(s): Toeplitz

Conjecture   Does every Jordan curve have 4 points on it which form the vertices of a square?

Keywords: simple closed curve; square

## Lindelöf hypothesis ★★

Author(s): Lindelöf

Conjecture   For any

Since can be replaced by a smaller value, we can also write the conjecture as, for any positive ,

Keywords: Riemann Hypothesis; zeta

## Termination of the sixth Goodstein Sequence ★

Author(s): Graham

Question   How many steps does it take the sixth Goodstein sequence to terminate?

Keywords: Goodstein Sequence

## Consecutive non-orientable embedding obstructions ★★★

Author(s):

Conjecture   Is there a graph that is a minor-minimal obstruction for two non-orientable surfaces?

Keywords: minor; surface

## Diagonal Ramsey numbers ★★★★

Author(s): Erdos

Let denote the diagonal Ramsey number.

Conjecture   exists.
Problem   Determine the limit in the above conjecture (assuming it exists).

Keywords: Ramsey number

## The 4x5 chessboard complex is the complement of a link, which link? ★★

Author(s): David Eppstein

Problem   Ian Agol and Matthias Goerner observed that the 4x5 chessboard complex is the complement of many distinct links in the 3-sphere. Their observation is non-constructive, as it uses the resolution of the Poincare Conjecture. Find specific links that have the 4x5 chessboard complex as their complement.

## Elementary symmetric of a sum of matrices ★★★

Author(s):

Problem

Given a Matrix , the -th elementary symmetric function of , namely , is defined as the sum of all -by- principal minors.

Find a closed expression for the -th elementary symmetric function of a sum of N -by- matrices, with by using partitions.

Keywords:

## Monochromatic empty triangles ★★★

Author(s):

If is a finite set of points which is 2-colored, an empty triangle is a set with so that the convex hull of is disjoint from . We say that is monochromatic if all points in are the same color.

Conjecture   There exists a fixed constant with the following property. If is a set of points in general position which is 2-colored, then it has monochromatic empty triangles.

Keywords: empty triangle; general position; ramsey theory

## Edge-antipodal colorings of cubes ★★

Author(s): Norine

We let denote the -dimensional cube graph. A map is called edge-antipodal if whenever are antipodal edges.

Conjecture   If and is edge-antipodal, then there exist a pair of antipodal vertices which are joined by a monochromatic path.

Keywords: antipodal; cube; edge-coloring

## Exponential Algorithms for Knapsack ★★

Author(s): Lipton

Conjecture

The famous 0-1 Knapsack problem is: Given and integers, determine whether or not there are values so that

The best known worst-case algorithm runs in time times a polynomial in . Is there an algorithm that runs in time ?

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

Author(s): Gordon

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

Keywords: 2-knot; Computational Complexity; knot theory

## Algorithm for graph homomorphisms ★★

Author(s): Fomin; Heggernes; Kratsch

Question

Is there an algorithm that decides, for input graphs and , whether there exists a homomorphism from to in time for some constant ?

## Exact colorings of graphs ★★

Author(s): Erickson

Conjecture   For , let be the statement that given any exact -coloring of the edges of a complete countably infinite graph (that is, a coloring with colors all of which must be used at least once), there exists an exactly -colored countably infinite complete subgraph. Then is true if and only if , , or .

Keywords: graph coloring; ramsey theory