Output

All Algebraic graph theory AI for mathematics AI & machine learning Complex systems Cognitive science

peer-reviewed publications

Pastorek, J. (2026). “AutoGraphForge: Towards Automated Graph Theory Discovery.” Accepted, to appear in ITAT 2026, Aachen: CEUR-WS. Preprint: arXiv:2609.03478 ai aimath graphs

Cingel, V., Jajcayová, T., Pastorek, J. (2024). “Partial automorphisms and level of symmetry of asymmetric graphs.” In ITAT 2024, Aachen: CEUR-WS, pp. 162-170. PDF graphs

preprints and manuscripts under review

Jajcayová, T., Pastorek, J. “Maximal asymmetric depth of graphs” graphs

Pastorek, J. “Extremal Asymmetric Depth of Planar Graphs and Hidden Near-Mirror Symmetries of IPR Fullerenes.” Preprint: arXiv:2609.02585 graphs

Lane, J., Puga-Gonzalez, I., Normann, R., Shults, L. R., Pastorek, J. (2024). “Emotional Contagion in Scandinavia during the COVID-19 Public Health Crisis.” Preprint: PsyArXiv, 10.31234/osf.io/9e5f7 complex cogsci ai

Petruskova, J., Pastorek, J., Mucskova, L., Harazim, H., Stourac, P. “Facial Recognition–Based Artificial Intelligence Models for Difficult Airway Prediction: A Systematic Review.” ai

in preparation

Maceková, M., Pastorek, J., Soták, R., Švecová, D. “Four-color defective colorings of toroidal graphs.” graphs

Pastorek, J., Sarto-Jackson, I. “Austrian Roots of Cognitive Science: An Interdisciplinary Analysis of Ernst Mach’s Contributions.” cogsci complex ai

Jedlička, P., Pastorek, J., Varchola, J. “Causation and emergence in neuroscience from a dynamical complex systems perspective.” complex

invited talks

• Pastorek, J. (2026). Title to be announced, Mirka Miller Combinatorics Webinar Series, 18.11.2026 graphs

• Pastorek, J. (2025). “Forth from Extensions of Partial Automorphisms to the Weisfeiler–Leman Algorithm & Counting Logic & Bijective Pebble Games—and Back Again”, Algebraic Graph Theory Seminar, 12.12.2025 graphs

  Abstract

  The graph isomorphism (GI) problem sits in an unresolved position between P and NP-complete and is polynomially equivalent to computing an orbit partition of a graph’s automorphism group. The Weisfeiler–Leman (WL) algorithm is a central combinatorial method for isomorphism testing that iteratively aggregates local neighbourhood information to approximate this orbit structure. A partial automorphism of a graph is an isomorphism between induced subgraphs of a graph. The set of all partial automorphisms under composition and inverses forms a partial automorphism inverse monoid which encodes complete algebraic information.

  In this talk, we discuss how these viewpoints of WL and partial automorphisms can be related. In particular, we review four different but equivalent perspectives on WL and show how they interact. After reviewing the necessary background, we revisit the $k$-dimensional WL algorithm and its logical characterization via bijective pebble games. From duplicator strategies in the bijective k-pebble game played on two copies of the same graph, one can collect all pebbled positions into a set of partial automorphisms of rank at most k. Among others, this set inherits back-and-forth extension properties from the underlying game.

• Pastorek, J. (2025). “Partial automorphisms and Asymmetric depth of not only sparse graphs.” Košický kombinatorický seminár, 28.10.2025 graphs complex

  Abstract

  While it is well-established that almost all graphs are asymmetric, possessing no nontrivial global automorphisms, all graphs contain non-trivial local symmetries which we study using isomorphisms between induced subgraphs, known as partial automorphisms. The set of all partial automorphisms, along with the operations of partial composition and partial inverse of partial maps, forms an inverse monoid, which is a rich and complex algebraic structure. However, it is hard to compute. In this talk, we are motivated by the study of partial automorphism inverse monoids of graphs initiated by [1]. We investigate the extent of these local symmetries through the measure of asymmetric depth of graphs defined through the rank of the largest non-trivial partial automorphism. We established a new, tight lower bound for the asymmetric depth of any simple graph $\Gamma$ on $n$ vertices. Any graph achieving this bound must be a strongly regular graph with parameters $(n,(n-1)/2,(n-5)/4,(n-1)/4)$, also known as a conference graph. We implemented a parallel algorithm for checking asymmetric depth on a high-performance cluster. Using this algorithm, we identified an asymmetric conference graph on 37 vertices that attains this bound, thereby proving its tightness. We also showed that it is one of the smallest possible graphs to attain this bound by checking all asymmetric conference graphs up to 37 vertices. We showed how the bound applies to sparse graphs such as planar graphs.

• Pastorek, J. (2025). “Maximal Asymmetric Depth and Conference Graphs.” Bratislavský seminár z teórie grafov, 23.10.2025 graphs

  Abstract

  Almost all graphs are asymmetric, possessing no nontrivial global automorphisms. Despite this fact, all graphs contain non-trivial local symmetries which we study using isomorphisms between induced subgraphs, known as partial automorphisms. We investigate the extent of asymmetry of graphs through the measure of asymmetric depth defined through the rank of the largest non-trivial partial automorphism. We will show a lower bound for the asymmetric depth of any simple graph $\Gamma$ on $n$ vertices. Any graph achieving this bound must be a strongly regular graph with parameters $(n,(n-1)/2,(n-5)/4,(n-1)/4)$, also known as a conference graph. We implemented a parallel algorithm for checking asymmetric depth on a high-performance cluster. Using this algorithm, we identified an asymmetric conference graph on 37 vertices that attains this bound, thereby proving its tightness. We showed that it is of the smallest possible order to attain this bound by checking all asymmetric conference graphs up to 37 vertices. The talk is based on joint work with Tatiana Jajcayová

contributed talks

• Pastorek, J. (2026). “AutoGraphForge: Towards Automated Graph Theory Discovery” at ITAT 2026 ai aimath graphs

• Pastorek, J. (2026). “AutoGraphForge: Conjecturing, Refutation and Lean Formalization in One Loop” at CICM 2026, AI4Math ai aimath graphs

• Pastorek, J. (2026). “Extremal asymmetric depth of planar and higher-genus graphs” at CSGT 2026 graphs

  Abstract

  Although almost all graphs are known to be asymmetric — having no nontrivial global automorphisms — they may still possess local symmetries in the form of isomorphisms between induced subgraphs, i.e., partial automorphisms. We study such local symmetries via asymmetric depth, defined as $d(\Gamma )=n-k_{\max }(\Gamma )$, where $k_{\max }(\Gamma )$ is the maximum rank of a nontrivial partial automorphism of an $n$-vertex graph $\Gamma$. Continuing this line of work on specific graph classes, we prove a tight upper bound $d(\Gamma )\le 5$ in the class of planar graphs and show that duals of IPR fullerenes can attain this extremal value: any fullerene whose dual achieves $d=5$ must satisfy the isolated pentagon rule, the smallest examples occurring on $90$ and $92$ vertices. Exhaustive computations up to $n=120$ indicate that almost all IPR fullerenes are asymmetric with depth $4$, and those that fail to attain the maximum exhibit hidden, almost-global symmetries broken only locally. We extend the bound to surfaces of higher genus, obtaining $d(\Gamma )\le 5+\sqrt{1+48g}$. Paralleling Frucht’s gadget technique, we construct an explicit family $\{A_h{\}}_{h\ge 2}$ by attaching columns of varying lengths of $h$-dimensional hypercubes to a central copy of $Q_h$, and prove $d(A_h)=2(h-2)$ for $h\ge 3$. Combined with a depth-monotonicity result for induced subgraphs, this realizes every positive integer as an asymmetric depth with increasingly high genus.

• Pastorek, J. (2025). “Deeply Asymmetric Structures.” Doctoral Colloquia at Comenius University, 8.12.2025 graphs complex

  Abstract

  What are symmetries? Symmetries are typically understood globally: an object is symmetric if it has nontrivial automorphisms—transformations preserving the whole structure. It is well-established that almost all graphs are asymmetric, possessing no “global” symmetries. However, global asymmetry does not imply a lack of structure. Every graph exhibits rich “local” symmetries, which we study using isomorphisms between induced subgraphs, known as partial automorphisms. How far can graphs be from having global symmetries? We investigate this question through the measure of asymmetric depth of graphs defined through the order of the domain of the largest non-trivial partial automorphism. We will report on our progress from previous years. Earlier, we established a new, tight upper bound for the asymmetric depth of any graph. We proved that any graph achieving this bound must be a strongly regular graph. We implemented a parallel algorithm on high-performing cluster Clara for checking asymmetric depth on a high-performance cluster. Using this algorithm, we identified an asymmetric conference graph on 37 vertices that attains this bound, thereby proving its tightness. Given that most real-world networks such as brain networks are sparse due to connection costs, we have begun extending this investigation to sparse graphs where we can improve the general upper bound. For planar graphs, we established a tight upper bound by finding duals of asymmetric fullerenes.

• Pastorek, J. (2025). “Partial automorphisms and Asymmetric depth of graphs.” 12th PhD Summer School in Discrete Mathematics, Koper, Slovenia graphs

  Abstract

  While it is well-established that almost all graphs are asymmetric, possessing no nontrivial global automorphisms, all graphs contain non-trivial local symmetries which we study using isomorphisms between induced subgraphs, known as partial automorphisms. The set of all partial automorphisms, along with the operations of partial composition and partial inverse of partial maps, forms an inverse monoid, which is a rich and complex algebraic structure. However, it is hard to compute. In this talk, we are motivated by the study of partial automorphism inverse monoids of graphs initiated by [1]. We investigate the extent of these local symmetries through the measure of asymmetric depth of graphs defined through the rank of the largest non-trivial partial automorphism. In [2], we established a new, tight lower bound for the asymmetric depth of any simple graph $\Gamma$ on $n$ vertices. Any graph achieving this bound must be a strongly regular graph with parameters $(n,(n-1)/2,(n-5)/4,(n-1)/4)$ also known as conference graph. We implemented a parallel algorithm for checking asymmetric depth on a high-performance cluster. Using this algorithm, we identified an asymmetric conference graph on 37 vertices that meets this bound, thereby proving its tightness. We also showed that it is one of the smallest possible graphs to meet this bound by checking all asymmetric conference graphs up to 37 vertices.

• Pastorek, J. (2025). “Graph isomorphism, asymmetric graphs and partial symmetries”, Doctoral Colloquia at Comenius University in Bratislava graphs

• Pastorek, J., Jajcayová, T. (2024). “Asymmetric Graphs and Partial Automorphisms.” In Abstracts, CSGT 2024, Ostrava: VŠB–TU Ostrava, pp. 28-29. graphs

• Jajcayová, T., Pastorek, J. (2024). “Partial automorphism monoid of graphs and k-Weisfeiler-Lehman.” In CSD 10, Leuven: KU Leuven, p. 26. graphs

• Pastorek, J., Jajcayová, T. (2024). “Partial automorphism monoid of graphs and Weisfeiler-Leman.” In Študentská vedecká konferencia FMFI UK, Bratislava, p. 366. graphs

• Cingel, V., Jajcayová, T., Pastorek, J. (2024). “Partial automorphisms and level of symmetry of asymmetric graphs.” In ITAT CADM 2024 graphs

• Pastorek, J. (2024). “Search for correspondences between operations on partial automorphisms and k-dimensional Weisfeiler-Leman algorithm.” At the Constructions of Expanders and Extremal Graphs workshop. graphs

• Pastorek, J. (2023). “Global Versus Local Symmetries.” MEi: CogSci Conference. PDF cogsci graphs

  Abstract

  Symmetry has been a cornerstone of human thought and aesthetics since ancient times in various civilizations. While the ancient interpretation of symmetry encompassed the idea of equal arrangement and proportion, the modern understanding is limited to the set of transformations that leave the object invariant. We investigate the concept of partial (local) symmetry, which may be viewed as a sort of return to the original meaning of the term symmetry, stressing the importance of proportionality but capturing the current meaning of symmetry as well. Moreover, we investigate its significance in various disciplines, such as neuroaesthetics and mathematics. Furthermore, we argue that the concept of local (partial) symmetry, as opposed to global (total) symmetry, is more natural, more general, and better describes natural phenomena and symmetries in abstract structures.

• Pastorek, J. (2023). “Semantic Primitives in Word Embeddings.” MEi: CogSci Conference. PDF · Poster cogsci ai

  Abstract

  Semantic primitives are the core concepts that possibly all humans share. They cannot be defined by any other concepts, for the chain of definitions ends in them. Finding such a set would provide us with a common communication “mother language”. We could use such a set to communicate ethical norms to less developed communities. The list of such primes is already stable, numbering 65 in total including words such as TRUE, GOOD, NOT, YOU, etc. Modern NLP models can capture the semantic similarity of words based on statistical co-occurrences of words. Such models create global embeddings, vectors for each word that occurs in the training where words that co-occur in similar contexts should occupy a similar place in the vector space. The vector spaces produced by these models are based on co-occurrence statistics, and the models do not explicitly encode the fundamental semantic properties associated with semantic primitives. Do the vectors corresponding to semantic primitives emerge near mathematically special regions in the vector spaces of NLP models, despite their lack of explicit encoding in those places? In other words, are the primes close to SVD singular vectors, PCA components, or K-Means cluster centers?

• Pastorek, J., Sarto-Jackson, I. (2023). “Unraveling the Hidden Influence of Ernst Mach on the Foundations of Cognitive Science - Interdisciplinary Approach.” Kognícia a umelý život 2023 Conference. PDF · Poster cogsci complex ai

  Abstract

  Existing narratives often overlook the significant impact of Ernst Mach and the Vienna Circle on the foundations of cognitive science. In this study, we delve into the underexplored influence of Mach’s theories on the emergence of cognitive science, employing a unique interdisciplinary approach that blends rigorous argumentation with cutting-edge computational methods in network science and natural language processing. Our findings reveal multiple, previously unrecognized pathways of influence from Mach to pivotal figures in cognitive science, thereby showcasing the efficacy of our combined approach in illuminating the intricate web of intellectual connections. This innovative method offers valuable insights into tracing the potential influences of key thinkers, addressing a longstanding challenge in the history of science arising from the ever-growing corpus of academic literature. To our knowledge, this is one of the first papers to use both citation networks and natural language processing for the investigations of the history of cognitive science.

Software

• AutoGraphForge — automated conjecturing, refutation and Lean formalization for graph theory (ITAT 2026 paper) aimath graphs
• Parallel asymmetric-depth checker — computes asymmetric depth on the Clara high-performance cluster; used to identify the extremal conference graph on 37 vertices graphs
• Further repositories: github.com/JanPastorek