MARKO PETKOVŠEK (1955 – 2023)
Marko Petkovšek was born in 1955 and
died in 2023. He completed his PhD in
1991 at the School of Computer Science,
Carnegie Mellon University, Pittsburgh, af-
ter which he worked at the University of
Ljubljana until retirement in 2021 as a pro-
fessor, researcher, the head of the mathe-
matics department and vice-dean.
Marko Petkovšek has an outstanding
worldwide reputation in the fields of dis-
crete mathematics and theoretical comput-
er science, which he earned through his re-
search and work in the field of symbolic
computation. He is best known as a coau-
thor of the well-known book A=B and the
author of the “Hyper” algorithm for solv-
ing linear recursive difference equations
with polynomial coefficients in terms of
hypergeometric forms, nowadays called
the Petkovšek’s algorithm.
In addition to fundamental results and
publications in symbolic computation,
Marko’s work in graph theory, where he intermittently collaborated with one of us over
a period of several decades, also contributes to his visibility. Let us say a little more about
his work in this area. He explored various classes of perfect graphs, graphs with non-
empty intersections of longest paths, hereditary graph classes, Fibonacci and Lucas cubes,
and attacked several related problems. One of the first challenges suggested by Marko was
the problem of the intersection of longest paths in graphs. We wrote a joint paper that
went mostly unnoticed for a quarter of a century, only to receive wide attention in the past
decade. Marko’s mathematical breadth was extremely helpful in the treatment of various
problems, as it often led to unexpected insights. Of this kind were his contributions to the
enumeration of the vertex and edge orbits of Fibonacci cubes and Lucas cubes. Marko’s
work also established new directions of development. In his paper [Marko Petkovšek, Let-
ter graphs and well-quasi-order by induced subgraphs, Discrete Mathematics 244 (2002)
375–388] he introduced the notion of letter graphs and proved that the class of k-letter
graphs is well-quasi-ordered by the induced subgraph relation, and that it has only finitely
many minimal forbidden induced subgraphs. This visionary paper preceded developments
in the field by a decade, and is today recognized as a fundamental reference on the topic.
Let us finish with a few personal thoughts about Marko. Our deep and unbroken friend-
ship began more than 30 years ago. One of us was lucky to share an office with Marko as
a freshly minted assistant, and the other as his student. He introduced us both to the world
of research and transferred his enthusiasm for it to us. He was the best possible friend.
Despite his broad mathematical knowledge and depth of thought, he was extremely mod-
est and downplayed his strengths and contributions. His was always pleasant and soothing
company, be it on mountain trails, Saturday evening bridge sessions, or just conversations
at and around work. In addition to mathematics, he had a broad general outlook. He held
himself to the highest ethical and moral standards, inspiring others to do the same. And on
mountain hikes he could always name every flower we saw in his mother tongue Slovene,
German, and Latin.
Unfortunately, Marko left us too soon. We shall always remember the beautiful mo-
ments we spent with him and keep him in our memories as a truly exceptional man.
Andrej Bauer and Sandi Klavžar