Pavel Paták

Interesting (open) problems

Is core of a cube-like graph cube-like?

Core of a graph G can be defined as the smallest subgraph H for which there exists a graph homomorphism of G onto H. Because of their importance for CSP (constraint satisfaction problems), graph cores received some attention during the past decade. However, many fundamental questions remain unanswered. Let us briefly sketch one such question.

Cayley graphs comprise an important tool in group theory. They are defined as follows: take a group and a set of its generators and consider the graph, whose vertices are elements of the groups and an element a is connected to b, if there exists an element g, among the chosen generators such that ag=b or bg=a.

It would be nice to understand cores of Cayley graphs, for example, are they always Cayley?

A cube like graph is a Cayley graph, where the group in question is a cube, that is some finite power of the two element group. It turns out that we do not even understand cube-likes graphs! That is a shame. What about powers of other abelian groups? More about this problem on Open Problem Garden.

Hamiltonian cycles in finite Cayley graphs

k-monotonicity

Almost everyone knows when a real function is non-increasing or convex. There is a natural generalization of these notions: a real function is called k-monotone, iff its (k-2) derivative is convex.

Given a set of points in the plane (with distict x-coordinates), we can ask, whether they lie on a graph of some k-monotone function. We can decide this question for k=1 by simply looking at every pair of consecutive points. Similarly for k=2 it is sufficient to look at triples of consecutive points.

Quite surprisingly, in Three-monotone Interpolation, we have proven that if k=3, the situation is radically different: For every fixed size s, there exists a set S of points which does not lie on a graph of a 3-monotone function, such that all its subfamilies of size s do lie on such a graph. Although we believe the situation for higher k to be similar, it remains an open question.

We can also consider the Ramsey-type question. Given m,k, does there exist n(m,k) such that for every n(m,k)-element set of points in the plane, there exists a subset of m of them lying on a graph of k-monotone function or its mirror image? For k=1,2, the question was answered both qualitatively and quantitatively for k=1,2 by Erdös and Szekeres. In Three-monotone Interpolation, we have proven that such function also exists for k=3, which is quite interesting, given the non-local behaviour of 3-monotonicity.

For other values of k, the question remains widely open. Update: It seems that the problems have been recently solved. Cannot wait for the papers to appear.

Topological (p,q)-theorem