Αγαπητά μέλη της ακαδημαϊκής κοινότητας,

Το Γενικό Σεμινάριο του Τμήματος συνεχίζεται εκτάκτως την ερχόμενη Δευτέρα 08/12/2025.

Η ομιλία έχει προγραμματιστεί να διεξαχθεί τη Δευτέρα 08 Δεκεμβρίου στην αίθουσα 342 από τις 14:15 έως τις 15:00:

Ομιλητής: Ιωάννης Μίχος (Ευρωπαικό Πανεπιστήμιο Κύπρου)

Τίτλος: Combinatorial Comparison of Trace Monoids via Their Dependence Graph Symmetries

Σύνοψη της ομιλίας:
Trace monoids model the occurrence of events in concurrent systems. Given a
finite alphabet whose letters correspond to actions/events, certain letters commute when the
corresponding actions can occur simultaneously, and certain others do not, when the actions
can only run sequentially. Mathematically this is described with two binary relations on : a
reflexive and symmetric relation called dependence relation, and its complement in , called
independence relation. Both these can be visualized by their corresponding graphs and . The
former is an undirected graph with loops, called dependence graph, and the latter is an
undirected loop-less graph, called independence graph.


We ask whether there exist non-isomorphic trace monoids over a fixed alphabet that have the
same average parallelism. This question is related to the bivariate generating series F which
counts traces by their height and length; trace monoids with the same F also possess the
same average parallelism. The series F is known to be rational and has been calculated
efficiently via the symmetries of the dependence graph, when the latter is connected.


In this work we investigate the existence of non-isomorphic dependence graphs (over a
common fixed alphabet) with the same series F. Using fractional graph isomorphisms and
certain equitable partitions of the Cartier-Foata clique automaton, we prove two classification
results.


First, we show that all 2-regular independence graphs of the same order share the same
generating series F if and only if they have the same number of triangular connected
components.


Secondly, for any, all triangle-free -regular independence graphs of the same order β€”except
for the complete bipartite graph β€” have the same generating series F. The smallest instance
of this result for, is the pair consisting of the cube graph and the Wagner graph, both on
eight vertices.




Μετά το πέρας της ομιλίας θα ακολουθήσει συζήτηση.



Εκ μέρους της επιτροπής σεμιναρίων.