Algebra colloquium

It takes place on Tuesdays 15:40 at K1.

Information

Algebra colloquia are designed for master's and doctoral students, and the faculty. The aim is to offer a platform for researchers to present their own results or current trends in their area of interest in a way that is easy to understand for non-experts.

Colloquia talks will have 45 minutes and will be followed by questions and informal discussions (and cookies :) ). Everyone is most welcome to attend, including people from other departments. The colloquium is co-organized by Zuzka and Michael. If you want to give a talk, please, let one of us know.

Please note that a colloquium talk should be much more accessible than a usual seminar talk. If we asked you to give a talk, please at least read the brief information given here (of course, their specific local information, e.g. about talk length, doesn't apply :)). If you want, a little longer guide to read is here. We do try to keep our colloquia accessible to students, so feel free to discuss your plans for the talk with us in advance, we're happy to help you gauge the correct level for the talk. But also, please don't be surprised or offended if we ask you to make changes to your abstract after you send it to us.

Location: lecture room K1 (2nd floor), Sokolovská 49/83, Praha

Spring semester 2025

25. 02. Libor Barto: Clones, Constraints, and Minions
Abstract: More than 100 years ago, Emil Post characterized the expressive power of sets of Boolean logical connectives; as we say nowadays, he described all Boolean clones. Almost 50 years ago, Thomas Schaefer characterized the computational complexity of deciding primitive positive sentences over Boolean relational structures, the Boolean constraint satisfaction problems. 25 years ago, a tight connection between these two results was discovered and later further links found: to the first preservation theorem in logic, Birkhoff's HSP theorem, and more recently to finitary endofunctors of the category of sets, the minions. I will talk about parts of this story and a recent joint work with Z. Brady, F. Jankovec, A. Vucaj, and D. Zhuk on expressive power of three-valued logics. Slides
04. 03. Amnon Neeman (University of Milan): Vanishing negative K-theory and bounded t-structures
Abstract: We will begin with a reminder of algebraic K-theory, and a few classical, vanishing results for negative K-theory. The talk will then focus on a striking 2019 article by Antieau, Gepner and Heller – it turns out that there are K-theoretic obstructions to the existence of bounded t-structures. The result suggests many questions. A few have already been answered, but many remain open. We will concentrate on the many possible directions for future research. Slides
11. 03. David Chodounský (Academy of Sciences): Games and chromatic numbers of definable graphs
Abstract: A graph has a countable chromatic number if the vertices can be labeled by natural numbers so that no edge has the same label on both ends. Verifying this property for a given graph can be somewhat difficult; consider e.g. the graph of points in the Euclidean space Rⁿ connected with an edge iff their distance is a rational number. The countable chromatic number of this graph is an easy observation for n=1, but a nontrivial result for n>1 (Komjath, Schmerl). I will introduce an infinite determined game which provides a simple criterion for a definable (analytic on a Polish space) graph to be countably chromatic; it is sufficient to verify that the second player has a winning strategy. Using this criterion we can e.g. easily resolve the example of Rⁿ, as well as deduce interesting consequences on the structure of uncountably chromatic definable graphs. The talk is based on the paper Chodounsky, Zapletal: Two graph games (2024).
18. 03. Martin Čech: Primes, the Riemann zeta function and random matrices
Abstract: Thanks to the work started by Euler, Dirichlet and Riemann, we know that the distribution of prime numbers is related to analytic properties of complex functions, such as the Riemann zeta function or more general L-functions. During the talk, we will discuss this connection, review the known properties of the Riemann zeta function and touch on the modern theory, which is mysteriously connected with the theory of random matrices.
25. 03. Kristina Asimi (Durham University): Promise Model Checking Problems
Abstract:The fixed-template constraint satisfaction problem (CSP) can be seen as the problem of deciding whether a given primitive positive first-order sentence, i.e. a sentence only using existential quantifiers ∃ and conjunctions ∧ is true in a fixed structure (also called model).
In this talk, I will present joint work in which we study a class of problems that generalises the CSP simultaneously in two directions: we fix a set L of quantifiers and Boolean connectives, and we specify two versions of each constraint, one strong and one weak. Given a sentence which only uses symbols from L, the task is to distinguish whether the sentence is true in the strong sense, or it is false even in the weak sense. We call such a problem a Promise Model Checking Problem. We classify the computational complexity of these problems for the existential positive equality-free fragment of first-order logic, i.e., L = {∃,∧,∨} and we prove some upper and lower bounds for the positive equality-free fragment L = {∃,∀,∧,∨}.
In the final part of the talk, I will introduce recent work on Model Checking Problem over the positive equality-free fragment, which also provides the complexity of a specific Promise Model Checking Problem not covered in our paper.
01. 04. Chris Lambie-Hanson (Academy of Sciences): Derived functors, set theory, and the continuum problem
Abstract: Both set theory and homological algebra are centrally concerned with general questions of compactness, i.e., the extent to which a structure's global properties are determined by its local properties. With this in mind, it is perhaps unsurprising that there have been a number of prominent applications of set-theoretic techniques to resolve questions about derived functors in homological algebra. In this talk, we will present some applications of set theory to the study of the derived functors of the inverse limit functor. In the process, we will uncover a striking connection between the vanishing of certain derived limits and the determination of the cardinality of the continuum.
08. 04. Alexander Clifton (FIT ČVUT): Covering Points with Affine Hyperplanes
Abstract: Covering all points of the d-dimensional hypercube {0,1}^d with affine hyperplanes requires just two hyperplanes, but a result of Alon and Füredi shows that covering all but one point requires d hyperplanes. We extend this question to ask for the minimum number of affine hyperplanes needed to cover each point of {0,1}^d∖{0} at least k times while leaving the origin uncovered. We also consider a k-covering problem where the set to be covered is the triangular grid T_d(n):={(x₁,…,x_d) ∊ ℤ^d_≧0 ∣ x₁+…+x_d ≤ n-1}.
In the process, we make use of Combinatorial Nullstellensatz, linear programming, and various combinatorial arguments. Based on joint works with Hao Huang and with Abdul Basit and Paul Horn. Slides
15. 04. Chiara Meroni (ETH Zurich): Slices of hypercubes
Abstract: In the last few decades, the Bourgain slicing conjecture (now a theorem as of December) has inspired significant research into slices of convex bodies and their volumes. In this talk, I will guide you through some of the fascinating problems we have tackled, focusing on counting and optimization questions related to slices. In ongoing work with Marie-Charlotte Brandenburg, we study the combinatorics of slices of hypercubes, breaking through previously intractable dimensions. Our approach combines combinatorial methods with numerical algebraic geometry to enhance algorithmic efficiency. While our focus is on cubes, the techniques extend to arbitrary polytopes in any dimension. Slides
22. 04. Peter Zeman: NPA Hierarchy for Quantum Isomorphism and Homomorphism Indistinguishability
Abstract: In this talk we will present a surprising connection between combinatorics and quantum information theory. A classical theorem of Lovász (1967) states that two graphs are isomorphic if and only if they have the same homomorphism counts from all graphs. If we replace ``all graphs'' with some restricted class of graphs F, we arrive to the notion of homomorphism indistinguishability over the class of graphs F. Mančinska and Roberson (2020) proved that homomorphism indistinguishability over planar graphs is equivalent to quantum isomorphism of graphs, which is a notion coming from quantum information theory. NPA hierarchy gives a sequence of semidefinite programming (SDP) relaxations of quantum isomorphism. We show that each level of the NPA hierarchy for quantum isomorphism of graphs is equivalent to homomorphism indistinguishability over an appropriate subclass of planar graphs. Using the convergence of the NPA hierarchy and with the fact that the union these subclasses are all planar graphs we recover the theorem of Mančinska and Roberson. Moreover, despite quantum isomorphism being undecidable, our homomorphism indistinguishability allows a randomized polynomial-time algorithm deciding exact feasibility of each fixed level of the NPA hierarchy of SDP relaxations for quantum isomorphism. Slides
06. 05. Marek Filakovský (MUNI): Curves on the torus with prescribed intersections
Abstract: The study of families of simple closed non-homotopy-equivalent curves on a compact surface such that any two have at most k intersections as stared in the 90's with the work of Juvan, Malnič and Mohar and it has picked up further interest in recent years. Despite its fundamental and elementary nature, determining the maximum size of such families has remained an open problem, even in the case of a torus. I will describe a recent result, joint with Balla, Kiełak, Kráľ and Schlomberg, where we determine the maximum size of the family on the torus for every k. Surprisingly, the proof only utilizes widely known tools from combinatorics, discrete optimization, and geometry, together with simple number-theoretic observations. Slides

Fall semester 2024

08. 10. Hans Raj Tiwary: Limitations of Linear Programming
Abstract: Linear Programming is a pervasive tool in algorithm design for optimization problems. Linear Programs (LPs) are known to be able to effectively model any problem that can be efficiently solved on a computer. But are they also able to efficiently model NP-hard problems? An affirmative answer to this question will settle the P vs. NP problem affirmatively, and so it is no surprise that the answer is no. However, attempts to prove such limits on the power of LPs lead us to explore interesting connections to communication complexity. In this talk, I will explore such a connection that resulted in a proof that the Traveling Salesman Problem cannot be solved well using LPs.
I will first discuss the subtleties involved in making the above claim precise. Then I will describe the result, its connection to communication complexity, and various generalizations to the quantum setting and beyond. The talk is based on joint work with Samuel Fiorini, Serge Massar, Sebastian Pokutta, and Ronald de Wolf. Slides
15. 10. Albert Vucaj: The pp-constructability poset: recent results and the missing pieces
Abstract: One of the main goals in universal algebra is to develop a thorough understanding of finite algebraic structures. Since many of their properties are already determined by their term clone, i.e. the set of their term operations, this motivates the systematic study of clones on finite sets. A first breakthrough in this area was Post's classification of the clones on a two-element set: ordered by inclusion they form a countably infinite lattice, also known as Post's Lattice. However, already on a three-element set, the lattice of clones is uncountable and describing it turns into an extremely challenging project.
Motivated by the study of the complexity of constraint satisfaction problems (CSPs), we have initiated a systematic investigation of clones on finite sets, ordered by a relation that is coarser than inclusion, pp-constructability. In this talk, I will present our findings and discuss the new framework for classifying clones in this context. Slides
22. 10. Subham Roy: Mahler measure: A journey from Mersenne primes to special values of L-functions
Abstract: Mersenne primes are primes that appear in the sequence 2n − 1 (for n=1,2,…). With 282589933 − 1 they provide the largest known prime number to this day. More generally, in the early 1900s, Pierce and Lehmer proposed to find large primes among the factors of certain integer sequences {Δ(n, P): n = 1, 2, …} that depend on the the roots of an univariate polynomial P. As Δ(n, x-2) = 2n − 1, this in particular includes all Mersenne primes.
Lehmer suggested that this approach works well, if the sequence Δ(n, P) grows very slowly. He further linked the growth rate of Δ(n, P) to some other interesting number-theoretic properties. A few decades later, Mahler became interested in a specific height function of polynomials (the Mahler measure), its representations, and applications in number theory. „Coincidentally“ this measure aligned with the growth function considered by Lehmer. Over time, the scope of Mahler measure expanded significantly, especially after the discovery of its relations to algebraic geometry and K-theory.
The focus of this talk is on understanding the Mahler measure and its applications – from heights of algebraic numbers to special values of L-functions and beyond – alongside recent developments in the field. Slides
29. 10. Igor Khavkine (Academy of Sciences): A glimpse at Type Theory and a glance at the Lean Proof Assistant
Abstract: A Proof Assistant is a software environment that allows the composition of formalized mathematical theorems and proofs in a format that makes the proofs mechanically verifiable. Some recent circumstances have shone a spotlight on the Lean Proof Assistant and its project Mathlib, aiming to build a unified library of formalized mathematics at the level of current research. I will give a quick introduction to Lean’s formal language (Dependent Type Theory) and how it encodes logical statements/proofs, followed by a brief practical demonstration. Along the way, I will try to highlight the opportunities and challenges that formalized proofs offer to mathematicians today. Slides

05. 11. no colloquium – sports day
12. 11. Giovanna Le Gros: An introduction to homological dimensions over commutative noetherian rings
Abstract: The classical Auslander-Buchsbaum formula is one of the major achievements of homological algebra, linking the projective dimension of a finitely generated module to its depth over a commutative local noetherian ring. In particular it provides an example of a parallel between homological properties of the module category over a ring and ring-theoretic properties of the ring itself. The aim of this talk will be to give a gentle introduction to results of this type. In particular, we will be interested in the modules of finite projective dimension, as well as the spectrum of the commutative noetherian ring we are considering, all of which will be introduced during the talk.

19. 11. Matěj Konečný (TU Dresden): Extending partial automorphisms
Abstract: A partial automorphism of a structure is an isomorphism between its substructures. If B is a finite structure and A its substructure, we say that B is an EPPA-witness for A if every partial automorphism of A extends to an automorphism of B. We say that a class of finite structures has EPPA if it contains an EPPA-witness for each its member. In 1992, Hrushovski proved that the class of all finite graphs has EPPA, a crucial ingredient to a subsequent paper of Hodges, Hodkinson, Lascar, and Shelah about topological properties of a certain infinite group. Since then, many classes have been proved to have EPPA, and several other connections to seemingly distant areas of Mathematics have been identified.
I hope to give an introduction to this area with an emphasis on the combinatorics of EPPA. Slides

26. 11. Robin Visser: The Effective Shafarevich Conjecture
Abstract: One of the oldest problems in mathematics is understanding rational solutions to a polynomial equation f(x₁, x₂, …, x_n) = 0. When n = 2, these equations define curves in the plane. In 1922, Louis Mordell conjectured that any smooth curve over the rationals with genus at least 2 will have only finitely many rational points. Later, in the 1960s, Igor Shafarevich proved that this problem would be resolved by showing that there are only finitely many abelian varieties (certain geometric objects with a suitable group structure) of fixed dimension d, defined over a number field K, with good reduction at all primes outside a fixed finite set of primes S. The Shafarevich conjecture (and hence the Mordell conjecture) was eventually proven by Gerd Faltings in 1983, considered one of the crowning achievements of 20th century arithmetic geometry.
Whilst Faltings' proof laid the Mordell conjecture to rest, it remains an open problem to find an effectively computable algorithm which can explicitly compute all rational points on any given curve of genus at least 2. Such an algorithm would follow by exhibiting an effectively computable algorithm which can explicitly compute all dimension d abelian varieties A/K with good reduction outside S; this is known as the effective Shafarevich problem. Whilst several effective algorithms have been developed to explicitly classify elliptic curves with good reduction outside a finite set of primes, effectively solving this problem in higher dimensions remains a challenge. In this talk, I will give a brief survey on some known methods for classifying abelian varieties, and will present some work in progress on classifying abelian surfaces (dimension 2 abelian varieties) over Q with good reduction away from 2. Slides
03. 12. Petr Vojtěchovský (University of Denver): Minimal representatives and the isomorphism problem for graph-like objects
Abstract: Minimal or canonical representatives can be used to organize databases of mathematical objects and to solve the isomorphism problem. Although computing canonical representatives is at least as hard as computing isomorphisms (and likely harder), several state-of-the-art packages for graph isomorphisms rely on canonical representatives and typically run in polynomial time. Many other isomorphism problems can be reduced to a graph isomorphism problem. After a brief overview, we will show how to efficiently find minimal representatives of endofunctions (= labeled functional digraphs). This is joint work with James Mitchell and Sujoy Mukherjee. Slides
10. 12. Daniel Gromada (FEL ČVUT): A brief introduction to quantum symmetries
Abstract: In this talk, I would like to explain the concept of a quantum symmetry. We will focus on symmetries of simple combinatorial objects like finite sets and graphs. This can be approached either from the viewpoint of quantum groups or via diagrammatic categories. I will try to explain how drawing simple string diagrams can reveal interesting findings about quantum symmetries of certain objects.
17. 12. Peter Bürgisser (TU Berlin): Probabilistic intersection rings of homogeneous spaces
Abstract: Suppose X₁, …,X_s are submanifolds of a compact homogeneous space M, in general position, with finite intersection. We may think of M as a real or complex projective space, or a Grassmann manifold. The signed count of intersection points can be described in terms of the real cohomology algebra of M: intersection corresponds to multiplication. Integral geometry provides methods to compute the expectation of the total number of intersection points when the X_i are moved at random with respect to the Haar measure.
We motivate and outline the functorial construction of a probabilistic algebra, whose multiplication mirrors the intersection of randomly moved submanifolds. The goal is to understand the expected total number of intersection points. The elements of this algebra are classes of zonoids (certain convex bodies) in the exterior algebra, and their multiplication is induced by the wedge product. This algebra contains the cohomology algebra as a direct summand. There is an intimate relationship with Alesker’s multiplication of valuations of convex bodies.

Spring semester 2024

05. 03. Michael Pinsker (TU Wien): Constraint Satisfaction Problems: distinguishing the easy from the hard
Abstract: I will give a gentle introduction to current algebraic and model-theoretic methods in the computational complexity of Constraint Satisfaction Problems (CSPs).
A CSP is a computational problem where we are given variables and constraints about them; the question is whether the variables can be assigned values such that all constraints are satisfied. Numerous natural computational problems, such as satisfiability of a given system of equations over a field, are CSPs; in fact, any computational problem is Turing-equivalent to a CSP.
Any CSP can be modeled by a relational structure, and conversely every relational structure naturally defines a CSP. In view of humanity's continuing quest to distinguish easy from hard problems in general, and the class P (polynomial-time solvable problems, e.g. satisfiability of linear equations over a field) from the class NP (polynomial-time verifiable problems, e.g. satisfiability of a propositional formula) in particular, the question arises which mathematical properties of a relational structure make the corresponding CSP easy and which make it hard. It turns out that particular algebraic invariants of the structure often determine the borderline between different complexity classes. Hence algebraic methods, combined with concepts from model theory as well as from Ramsey theory in the case of infinite structures, yield appropriate tools to determine the computational complexity of CSPs. Slides
12. 03. Stanislav Nagy: Halfspace depth: Geometry of multivariate quantiles
Abstract: Statistical depth is a non-parametric tool applicable to multivariate and non-Euclidean data, whose goal is a reasonable generalisation of quantiles to multivariate and more exotic datasets. We discuss the halfspace depth, arguably the most crucial depth in statistics. J. W. Tukey proposed that depth in 1975; its rigorous investigation started in the 1990s, and still, an abundance of open problems stimulates research in the area.
We present surprising links of the halfspace depth with well-studied concepts from convex geometry. Using these relations, we partially resolve several open problems concerning depth. In particular, we resolve the 30-year-old characterisation conjecture, asking whether two different measures can correspond to the same halfspace depth. Slides
19. 03. Víťa Kala: Arithmetic in infinite extensions + music party afterwards
Abstract: A complex number is called algebraic if it is the root of some polynomial with integer coefficients. Starting with efforts to solve Diophantine equations, extensions of the rational numbers by several algebraic numbers (ie, smallest fields that contain all of them) have been widely studied throughout algebra and number theory. I will focus on the more mysterious case of extensions by infinitely many numbers. Specifically, I will discuss
- how to measure the size of an algebraic number,
- how many „small“ algebraic numbers does a given extension have, and
- the connections to logic and number theory (including a recent joint result with Nicolas Daans and Siu Hang Man).
26. 03. Michael Zieve (University of Michigan): Classification of non-random rational functions
Abstract: Many properties of a rational function f(x) over a field K of characteristic zero are determined by the monodromy group of f(x), which is the Galois group of the Galois closure of the field extension K(x)/K(f(x)). In particular, in many respects, every degree-n rational function with monodromy group A_n or S_n behaves like a „random“ degree-n rational function. I will describe all degree-n rational functions whose monodromy group is not A_n or S_n for all n and K. Intuitively, this amounts to describing all obstructions which can cause a degree-n rational function to have non-random behavior. I will also present several applications, and mention analogous results in positive characteristic.I hope to convey the classical way in which topology and analysis provide valuable algebraic information, and also the more modern ways in which powerful results from group theory can be applied to a wide range of topics.
02. 04. Sam Braunfeld: Orbit-counting for groups acting on countable sets
Abstract: Beginning in the 1970s, Peter Cameron generalized the classical problem of counting the orbits of a finite group action by considering actions on a countable set X. By counting orbits of the natural action on Xⁿ for each n, we obtain infinite sequences of integers, including many classical sequences. The asymptotic behavior of these sequences was conjectured to be tightly constrained, falling into narrow bands with large gaps. We will indicate the proofs of these conjectures and their fundamental connection to model theory. Slides
09. 04. Tomáš Jakl (Academy of Sciences): From vector spaces and bilinear maps to monads, game comonads and Feferman-Vaught-Mostowski theorems
Abstract: Bilinear maps and their classifying tensor products are well-known in the theory of linear algebra, and their generalization to algebras of commutative monads is a classical result of monad theory. We generalize the notion of bimorphism much further and hint at its applications in the setting of game comonads. These results allow us to prove famous Feferman-Vaught-Mostowski theorems in logic, such as the result that the first-order theory of a product of two structures is determined by theories of its two components.
16. 04. Michael Kompatscher: Interpolation over finite algebraic structures
Abstract: In interpolation, we are given a finite set of data points P, and the goal is to find a suitable interpolation function, i.e. a function satisfying f(x) = y, for all (x,y) in P. A well-known example is polynomial interpolation: For data points P over a field F we can always efficiently construct an interpolation polynomial over F, unless this is not possible for trivial reasons (i.e. P not being a partial function). In fact, this is still the case for higher dimensional data, which can be interpolated by multivariate polynomials.
But what happens, if we want our interpolation function to be a term operation of an algebraic structure A other than a field? As it is quite rare that then every P can be interpolated, we need to investigate two questions: Can a given partial operation Aⁿ → A be interpolated by a term operation of A? And, if so, how can we construct an interpolation term? In this talk, I am going to discuss the computational complexity of both these problems for finite algebraic structures. While they can be computationally hard (EXPTIME-complete) for some A, they are conjectured to be solvable in polynomial time for so-called Mal'tsev algebras, a big class of algebras that includes all rings, groups, quasigroups, Boolean algebras, and many more.
23. 04. Gábor Péter Nagy (University of Szeged): On the algebraic structure of midpoint operations in C*-algebras
Abstract: The Kubo-Ando mean and the Wasserstein mean are examples of larger classes of means that play an important role in the theory of C*-algebras, but also in quantum information theory and the theory of optimal transports. These operations are local quasigroups, and in some cases, they have an interesting algebraic structure, which is related to the Jordan algebra and the Lie triple system associated with the C*-algebra. However, Jordan algebras and Lie triple systems can be defined more generally. These generalizations may be interesting on their own, but they may give new insights into the structure of C*-algebras, as well. Slides
30. 04. Jan Vybíral (FJFI ČVUT): Dispersion of a point set – lower and upper bounds
Abstract: Given a point cloud in the unit cube of a d-dimensional Euclidean space, its dispersion is defined as the volume of the largest axis-parallel box, which does not intersect this cloud. For a fixed integer n, we try to minimize the dispersion among the point sets of cardinality n. We review recent upper and lower bounds of this quantity, which turned to be connected to discrete geometry, probability, combinatorics, and analysis. Especially, we discuss a new lower bound obtained by a reduction to a certain combinatorial problem solved previously by Ruszinkó, Alon, and Asodi. This is a joint work with M. Ulrich (Linz) and M. Trodler and J. Volec (both CTU Prague).
07. 05. Karim Adiprasito (CNRS Paris): Stars and fins: on a conjecture of Oda and Alexander
Abstract: One of the key results in PL topology is that, given two PL homeomorphic manifolds, one can transform one into the other by a sequence of simple combinatorial moves, called stellar refinements and their inverses.A conjecture of Alexander was that one could put all the refinements first, and then apply their inverses, reshuffling these moves. I will present a solution to this conjecture, and a related conjecture of Oda concerning birational varieties. Joint work with Igor Pak.
14. 05. Gil Solanes (UAB Barcelona): Algebraic Integral Geometry
Abstract: The kinematic formula in integral geometry measures the set of euclidean motions that bring a convex body to intersect another one. The result is expressed in terms of the so-called intrinsic volumes of the bodies, which belong to a class of functionals called valuations. Similar formulas exist for other groups of motions and other ambient spaces. The explicit determination of these more general kinematic formulas was a difficult problem until the discovery by Alesker and Fu of a closely related product structure on the space of valuations. In the talk we will describe some recent advances in integral geometry allowed by this new algebraic viewpoint.
21. 05. Petr Lisoněk (Simon Fraser University): On a certain class of Hadamard matrices
Abstract: Hadamard matrices are classical objects studied in algebra, discrete mathematics, information theory, engineering and in many other areas. A complex Hadamard matrix is a square matrix characterized by two conditions: Each entry is a complex number with absolute value 1, and any two distinct rows are orthogonal. Hadamard matrices with entries 1 and –1 were initially studied by Sylvester, Hadamard and Paley (among others), with the generalization to unimodular complex entries being a more recent development. In this talk, after surveying some background information, we will focus on a special class of matrices called S-Hadamard, which are complex Hadamard matrices satisfying the additional condition that the elementwise product of the matrix with itself (Schur product) is also a complex Hadamard matrix. We will discuss algebraic and computational constructions of such matrices, existence results, and some applications in quantum information theory.

Fall semester 2023

10. 10. Honza Kratochvíl: Graph covers: A journey from topology via computational complexity to generalized snarks
Abstract: Graph covers, aka locally bijective homomorphisms of graphs, stem from topological motivation, are frequently used in algebraic graph theory and found applications in computer science as a model of local computation. Though the question of characterizing the computational complexity of covering a fixed target graph was raised by Abello, Fellows and Stilwel already in 1991, only partial results are known.
We will discuss several results in this direction, including a connection to CSP, a generalization to colored mixed multigraphs with semi-edges (a concept becoming recently popular in topological graph theory and mathematical physics) and a recently encountered notion of generalized snarks.
Based on joint work with Jan Bok, Jiri Fiala, Petr Hlineny, Nikola Jedlickova, Roman Nedela, Michaela Seifrtova and Pawel Rzazewski.
Slides
17. 10. Alexey Barsukov: Homogeneous graphs: construction, examples, and applications
Abstract: A homogeneous graph is a graph in which every isomorphism between finite (induced) subgraphs extends to an automorphism. In this talk, I first present some well-known examples of homogeneous graphs. Then I will prove Fraissé's theorem that shows how one can construct a universal homogeneous graph for a given countably infinite class of finite graphs. Finally, I will explain why homogeneous structures are relevant to my research by describing their relation with omega-categorical constraint satisfaction problems.
Slides
24. 10. Thibault Gauthier (ČVUT): Program Synthesis for the OEIS
Abstract: We introduce a self-learning algorithm for synthesizing programs for sequences from the OEIS (On-Line Encyclopedia of Integer Sequences). The algorithm starts from scratch initially generating programs at random. Then it runs many iterations of a self-learning loop that interleaves (i) training neural machine translation to learn the correspondence between sequences and the programs discovered so far, and (ii) proposing many new programs for each OEIS sequence by the trained neural machine translator. The algorithm discovers on its own programs for more than 100,000 OEIS sequences.
Slides
31. 10. no colloquium – department party
07. 11. Lazar Radicevic (Besançon, France): Ring parametrizations and counting number fields
Abstract: The absolute discriminant of a number field is a numerical invariant that encodes important arithmetic information about the field. It can be defined in terms of the covolume of a lattice associated to the integers of the field. Roughly, the larger the discriminant is, the more complicated the number field is.
A folklore conjecture, sometimes attributed to Linnik, states that asymptotically there are c_n*X degree n number fields of absolute discriminant less than X. This conjecture is a theorem when n = 2, 3, 4 or 5, by the work of Davenport-Heilbronn and Bhargava. I will give an overview of the proof of this theorem in these cases, which consists of finding an appropriate parametrization of all rings of rank n and then employing methods from geometry of numbers to count these rings. If time permits I will present a result from a joint work with Tom Fisher, which gives a unified point of view on these ring parametrizations and a way to construct more of them.
Slides
14. 11. Faruk Göloglu: Projective polynomials in cryptography and algebra: nonlinear functions and finite semifields
Abstract: In this talk we will talk about projective polynomials and their applications in cryptography (e.g., nonlinear functions and discrete logarithm problem), and in algebra (e.g., finite semifields). The focus will be on the construction techniques of finite semifields and particularly, a recent construction that gives an exponential number of pairwise non-isotopic finite commutative semifields.
Slides
21. 11. Jun Maillard: Modular representation theory of finite groups
Abstract: Representations of finite groups are a way to introduce tools of linear algebra in the theory of groups. Over an algebraically closed base field of characteristic 0, the representations of a given group are classified by their characters. However, when the characteristic of the field divides the order of the group, this is not true anymore and different tools should be used to study them. We will introduce the notions of sources and vertices, and show that they lead to one of the first major results of modular representation theory: the Green correspondence.
28. 11. Piotr Kawałek (TU Wien): An etude on polynomials over finite rings in Computational Complexity Theory
Abstract: In this talk, we examine how s-sparse polynomials over finite (commutative) rings naturally appear in various areas of mathematics and computer science. We explore the unsolved problem of establishing lower bounds for the degree/size of a polynomial that weakly represents conjunctions, along with the implications of such lower bounds. Additionally, we demonstrate surprising connections between this mathematical problem and significant questions in computational complexity. These include the construction of efficient error-correcting codes and informational retrieval schemes if upper bounds exist, or the development of algorithms for solving equations in finite structures and addressing Constraint Satisfaction Problems (CSPs) with global modular constraints if lower bounds can be established.
Slides
05. 12. Jan Kotrbatý: An algebraic perspective on inequalities in convex geometry
Abstract: The isoperimetric inequality characterizes the circle as having the least perimeter among all plane figures of fixed area. In our talk, we will discuss, in the language of convex geometry, a broad generalization of this classical result. Namely, we will show that it appears as a special case of the Hodge-Riemann relations in the algebra of smooth valuations on convex bodies.
12. 12. Standa Hencl: Models of nonlinear elasticity: Questions and progress
Abstract: In this talks we study mappings that could serve as defomations in models on Nonlinear Elasticity. We have a body Omega in Rⁿ and we have a mapping f from Omega to Rⁿ that describes the deformation of this body.
Natural questions considered are when the mapping is continuous (the material does not break during the deformation), when is it invertible (no „interpenetration of matter“ happens) or when does it map sets of zero volume to sets of zero volume (no material is created or lost during our deformation). In particular we will study when the deformation does not change orientation (you cannot map your right hand to your left hand) or when can we approximate injective mappings by piecewise linear (or smooth) injective mappings.
Slides
19. 12. Kristóf Huszár (TU Graz): 3-Manifolds: Triangulations, Algorithms and Topological Obstructions
Abstract: There exist several computationally hard problems about triangulated 3-dimensional manifolds that can be solved efficiently, provided the input triangulation is sufficiently „thin“, as measured by a certain width parameter from graph theory. Therefore it is desirable to exhibit 3-manifolds via triangulations as thin as possible, however, this can be limited by topological properties of the underlying manifold.
In this talk I give an overview of several quantitative results that link the key combinatorial parameter in the above context – the treewidth of the dual graph of the input triangulation – to topological invariants of the underlying 3-manifold. Using these results, we exhibit infinite families of 3-manifolds which do not have „thin“ triangulations.
Joint work with Jonathan Spreer and Uli Wagner.
Slides

Spring semester 2023

28. 02. Jaroslav Nešetřil: Ramsey Theory, Sparsity and Limits
Abstract: We survey three areas of seemingly unrelated problems which were investigated recently and which are profiting from an algebraic setting: Ramsey theory, sparsity of graphs and limits of sequences of structures. These are diverse areas but share some properties where the connection to model theory is non-trivial and interesting. It also presents several open problems of a general interest.
07. 03. Siu Hang Man: The partition function and Ramanujan’s congruences
Abstract: The partition function p(n) counts the number of ways to write n as the sum of positive integers, ignoring order. Behind the seeming simple definition hides deep theory interlinking combinatorics, analysis, and algebra. Ramanujan discovered that the partition function satisfies some interesting congruence relations. In this talk we discuss classical Ramanujan’s congruences as well as recent developments in this direction.
14. 03. Manuel Bodirsky (TU Dresden): Valued Constraint Satisfaction Problems and Resilience in Database Theory
Abstract: The computational complexity of resilience of queries is a recent research topic in database theory. For a fixed conjunctive query q (or even a disjunction of conjunctive queries), one would like to compute the number of tuples that needs to be removed from a given database so that it does not satisfy q. In this talk I will explain how such computational problems can be viewed as valued constraint satisfaction problems (VCSPs). I some cases, the VCSPs are over a finite domain, in which case a complete complexity classification is known. In some cases, the VCSPs must have an infinite domain; however, the respective valued structure can be chosen to have an oligomorphic automorphism group. We give some general powerful hardness and tractability conditions and formulate a tractability conjecture for all resilience problems for unions of conjunctive queries. Joint work with Carsten Lutz and Žaneta Semanišinová.
21. 03. David Cerna (Academy of Sciences): Anti-unification: Recent Results and How is it Used
Abstract: Unification is a process by which two symbolic expressions may be identified through variable replacement. Anti-unification (generalization), on the other hand, is a process that derives from a set of symbolic expressions a new symbolic expression possessing certain commonalities shared between its members. In this talk we will discuss the basics of anti-unification, applications of the concept and some results concerning anti-unification over equational theories, over the simply-typed lambda calculus, and in other settings.
28. 03. Nicolas Daans: Hilbert's 10th Problem and decidability in number theory
Abstract: In 1900, David Hilbert posed a question at an international mathematics conference in Paris: Is there an algorithm that can determine whether a given polynomial equation with integer coefficients has an integer solution? The question became known as Hilbert's 10th Problem. Several decades later, it became increasingly clear that such an algorithm may never exist. This marked the start of a research area on the intersection of logic, algebra, and number theory: to determine which classes of problems from number theory and algebra are decidable (i.e. solvable by an algorithm) and which are undecidable. During this talk, I will discuss the history of Hilbert's 10th Problem and highlight some recent developments. The focus of the talk will be on how questions surrounding Hilbert's 10th Problem give rise to interesting problems in number theory, and conversely, how classical theorems from algebra, number theory, and quadratic form theory have been used to investigate questions surrounding decidability in number theory.
04. 04. Štěpán Holub: What is it like to code mathematics (in Isabelle/HOL)
Abstract: The ultimate goal of proof assistants in mathematics is to enable mathematicians to formulate their results in a way that is as close as possible to a human (or “paper”) mathematical language, but can at the same time be formally verified. In this way, the general idea that mathematics can be decomposed and verified all the way down to axioms becomes a practical reality. I will show how this looks like with a basic overview of a particular proof assistant Isabelle/HOL that I use to formulate and verify results in combinatorics on words, including concrete examples.
11. 04. Michal Hrbek (Academy of sciences): A simple introduction to contramodules
Abstract: The notions of comodules and contramodules over a coalgebra were both introduced in the classical AMS Memoir of Eilenberg and Moore in 1965. While the first notion saw a lot of action in various applications in geometry and topology, the second was nearly forgotten for almost 40 years, until revived by Leonid Positselski. In the modern viewpoint, contramodules can be seen as the correct notion of a ``topological module'' over a complete and separated topological associative ring, the usual modules being the special case when the topology is trivial. My aim is to give a basic introduction to contramodules, avoiding category theory and focusing on specific examples.
18. 04. Stefano Pozza: Matrix decay phenomenon and its applications
Abstract: In matrix computation, it is common to divide matrices into dense and sparse categories. Even though such categories are not precisely defined, we can think of a sparse matrix as one whose number of zero elements is large enough to be conveniently exploitable and a dense one as a matrix that is not sparse. It is important to note that the notion of sparsity does not consider the magnitude of the nonzero elements. This can be an issue since, in many applications, one has to deal with dense matrices in which most elements are so close to zero to being negligible. These matrices are close to being sparse in the sense that they are sparse upon truncation. Moreover, the nonnegligible elements are usually localized in some part of the matrix, and the magnitude of the other elements tends to decay to zero as we move away from them. As a simple example, consider the inverse of a tridiagonal matrix. Such an inverse is usually dense; however, under some conditions, the magnitude of its elements quickly decays to zero as we move away from the diagonal. Therefore, the inverse can be considered banded upon truncation. We will introduce the basics of the decay phenomenon in the matrix function case. Then we will show how to predict the decay phenomenon and exploit it in matrix computation applications.
25. 04. Ian Wanless (Monash university, Australia): Quadratic Latin squares and quasigroups
Abstract: A Latin square is a square matrix in which each row and column is a permutation of the same set of symbols. Examples include Cayley tables of finite groups and completed sudoku puzzles. A quadratic Latin square is defined using the quadratic residues in a finite field. In this talk I will give a high level overview of two recent applications of quadratic Latin squares in combinatorics and to the algebra of quasigroups.
02. 05. Honza Hladký (Academy of sciences): Invitation to graphons
Abstract: The first course in graph theory usually covers concepts such as matchings, independent sets, colourings, and forbidden subgraphs. Around 2004, Borgs, Chayes, Lovász, Sós, Szegedy, and Vestergombi introduced a very fruitful limit perspective on graphs. The central objects of this theory, so-called graphons, are suitable measurable counterparts to graphs.
In the talk, I will outline the syllabus of a hypothetical first course in graphon theory, in particular introducing versions of all the aforementioned concepts in the graphon setting. Based on work with Doležal, Hu, Máthé, Piguet, Rocha.
09. 05. Isaac Bird: An introduction to pure injective modules and their spectrum
Abstract: Understanding solution sets to matrices is a fundamental problem in linear algebra, while understanding the Zariski spectrum of a commutative ring is a fundamental problem in algebraic geometry. While these two problems may not seem to be related, I will show how, through pure injective modules, it is possible to consider both simultaneously. I will introduce pure injective modules and describe some of their properties, ultimately showing how one can recover the Zariski spectrum of a ring from them. Throughout, I will illustrate what is going on by showing how everything works over the integers.

Fall semester 2022

04. 10. Libor Barto: The number of homomorphisms into finite algebras
Abstract: In a recent joint work with William DeMeo and Antoine Mottet, we have characterized finite algebras A such that the number of homomorphism from any finite algebra X into A is bounded by a polynomial in the size of X. I will talk about this result, discuss its motivation and background, give examples, and mention open problems.
11. 10. Fabien Pazuki (University of Copenhagen): Elliptic curves and cryptography
Abstract: There are essentially two ways of using elliptic curves in modern cryptography. The first idea is to exploit their group structure and build protocols of RSA types. The second idea is to use maps between elliptic curves and construct graphs based on their properties. The goal of the talk is to describe these curves and some of their basic properties, and to discuss a bit of cryptography, notably international post-quantum challenges, high hopes and very recent disappointments! The main focus of the talk will be the underlying mathematics. No previous knowledge of elliptic curves is required.
18. 10. Michal Pavelka: Geometric mechanics, algebra, and machine learning
Abstract: Geometric mechanics is a general framework describing mechanical systems like particles, solid bodies, or fluids. And algebra plays a crucial role in geometric mechanics because the motion often takes place on a Lie algebra dual attached to a Lie group. In this talk, we shall see some fundamental concepts of geometric mechanics in connection with algebra, as well as an application in machine learning (for automatic recognition of mechanical systems).
25. 10. Claire Burrin (University of Zurich): Some insights from the geometry of numbers
Abstract: I will discuss some ideas from the geometry of numbers to study the shapes of random lattices or discrete lattice orbits at the hand of both classical and recent results.

08. 11. Jens Zumbrägel (University of Passau): Computation of a 30750 bit discrete logarithm
Abstract: The difficulty of the discrete logarithm problem is a cornerstone of modern public-key cryptography. Recently, a discrete logarithm has been computed in a huge binary field of 30750 bits, breaking by a large margin the previous record in a 9234-bit field. This was the first large-scale computation to demonstrate the potential of the elimination step of the quasi-polynomial algorithm due to Granger, Kleinjung and Zumbrägel, and it required the equivalent of about 2900 core years. In this presentation I will provide an overview of the mathematical and algorithmic ideas, which make such large-scale computations feasible, and discuss their practical implications. This talk is based on joint work with Robert Granger, Thorsten Kleinjung, Arjen K. Lenstra and Benjamin Wesolowski.
15. 11. Jan Volec (FJFI ČVUT): The Flag Algebra Method
Abstract: Flag algebras, a tool developed by Razborov in 2007, allows relaxing extremal combinatorics questions to semidefinite programming problems. Such a relaxation proven to be very successful in resolving various long-standing conjectures in the area including the question of Erdős concerned with the maximum number of pentagons in triangle-free graphs. In this talk, we will first describe the general method and the key principles behind it, and then present a few applications of the method to various problems in discrete mathematics.
22. 11. Aniket Shah: Brion's identity and beyond
Abstract: Let P be a polytope with integer vertices in Rⁿ. The lattice point generating function of P is defined as the sum over lattice points v in P of monomials x^v. Since P is compact, the number of lattice points in P is finite and the lattice point generating function is a Laurent polynomial. Via the geometry of toric varieties, Brion proved a surprising identity realizing the lattice point generating function of P as a sum of analytic continuations of lattice point generating series for noncompact polyhedral subsets of Rⁿ corresponding to each vertex of P. This identity has notable applications, including its use in the first polynomial time algorithm for counting the lattice points in a polytope of fixed dimension d, due to Barvinok. We'll discuss the theorem, a new q-analogue, and if time allows, see some ingredients in the proof of the identity and the design of Barvinok's algorithm.
29. 11. Jan Šťovíček: Combinatorial and homological structures on categories of representations
Abstract: I will discuss means of classifying representations of (aka modules over) finite dimensional algebras using homological and combinatorial methods. After explaining how to depict categories of representations in pictures (in terms of so-called Auslander-Reiten quivers), I will aim at the lattice of torsion pairs and mutations of torsion pairs.
06. 12. Dan Kráľ (Masaryk University): Ramsey Multiplicity of Graphs
Abstract: Ramsey's Theorem guarantees for every graph H that any 2-edge-coloring of a sufficiently large complete graph contains a monochromatic copy of H. We study the quantitative version of this result: how many monochromatic copies of H do necessarily exist in any 2-edge-coloring of the complete graph with N vertices? In 1962, Erdős conjectured that the random 2-edge-coloring asymptotically minimizes the number of monochromatic copies when H is a complete graph, and the conjecture was later extended to all graphs by Burr and Rosta. In the late 1980s, the two conjectures were disproved by Thomason and Sidorenko, respectively.
A classification of graphs whose number of monochromatic copies is minimized by the random 2-edge-coloring, which are referred to as common graphs, remains a challenging open problem. While examples of 3-chromatic common graphs were known for a long time, the existence of a 4-chromatic common graph was open until 2012. As discussed e.g. in the survey on recent developments in Ramsey theory by Conlon, Fox and Sudakov [London Math. Soc. Lecture Note Ser. 424 (2015), 49–118, Problem 2.28], the existence of a common graph with larger chromatic number has been a well-known open problem in the area. Using spectral arguments in the setting of graph limits, we establish the existence of connected common graphs with an arbitrarily large chromatic number.
The talk is based on joint work with Jan Volec and Fan Wei and will be self-contained, assuming no prior advanced knowledge of graph theory or theory of graph limits.
13. 12. Lenka Slavíková: A brief excursion into Fourier analysis
Abstract: The idea of representing functions as an infinite sum of trigonometric polynomials originated about two centuries ago in the work of Joseph Fourier. It is however quite a delicate problem to determine in what sense this can actually be done. In this talk, we will first review a few classical results on the convergence of Fourier series/ Fourier integrals. We will then focus on the question whether certain nice properties of a function are preserved if we alter its Fourier coefficients/ Fourier transform a little bit. This question can be formalized using the notion of Fourier multipliers, and we will present some classical as well as some more recent results on this topic.

Spring semester 2022

01. 03. David Stanovský: A combinatorial approach to knot recognition
Abstract: The fundamental problem of knot theory asks the following: Given two knots (or knot diagrams), can one smoothly transform one into the other? Is it possible to unknot a given knot diagram? I will present the method of arc coloring, which provides a large class of invariants of various strengths. For example, SL(2,p)-coloring can be used to obtain a certificate of unknottedness which can be verified in polynomial time. In the end, I will mention the underlying algebraic structures, called quandles, and their relation to the theory of permutation groups.
08. 03. Matteo Bordignon: Primes in arithmetic progressions and zeroes of Dirichlet L-functions
Abstract: Dirichlet theorem states that for any two positive coprime integers a and d, there are infinitely many primes of the form a + nd. To obtain this result Dirichlet introduced a set of specific complex functions, that are now called the Dirichlet L-functions, and linked the distribution of primes in arithmetic progressions to the position of the zeroes of these functions in the complex plane. The best possible result is that all the zeroes have real part equal to 1/2, this is the famous Generalized Riemann Hypothesis. In this talk we will give an overview on the properties and present the best known bound, obtained by Siegel, on these zeroes. At last, we will highlight the hurdles we encounter trying to make this bound explicit, and we will show what can be done to partially circumvent them.
15. 03. Dmitriy Zhuk: The complexity of the Constraint Satisfaction Problem and its variations
Abstract: Many combinatorial problems, such as graph coloring and solving linear equations, can be expressed as the constraint satisfaction problem for some constraint language. In 2017 the complexity of the constraint satisfaction problem was described for any constraint language on a finite set, but there are many other variants of this problem whose complexity is still not known. For instance, we could allow to use both universal and existentialquantifiers, or require the solution to be surjective or balanced. Another variant is to require the input to satisfy an additional condition. As an example we could consider the problem of coloring a graph in 100 colors if we know that the graph is colorable in 3 colors. In the talk we discuss the complexity of these and other variants of the constraint satisfaction problem.
22. 03. Marek Filakovský: Graph drawings and their higher-dimensional analogues: an overview
Abstract: A classical question in graph theory is whether a graph can be drawn into a plane without self-intersection. From an algorithmic perspective, we ask for an algorithm that decides existence of such drawing. Analogously, in higher dimensions, we consider a k-dimensional analogue of a graph called simplicial complex and ask whether it can be embedded in a d-dimensional Euclidean space. We will summarize (and try to explain) known results, discuss related problems such as extending embeddings (or extending drawings) and consider some open questions.
29. 03. Karel Tůma: Mathematical description of shape memory alloys
Abstract: Shape memory alloys are very cool materials because of two interesting properties – shape-memory effect and superelasticity – that are caused by the changes on the microscopic level. Specifically, during the macroscopic deformation, the material undergoes a phase transformation that is accompanied with the formation and evolution of complex microstructure. We present a mathematical model capable of describing this process and show the results of numerical simulations that can capture the detailed microstructure, see the figure.
19. 04. Olin Slávik: Monads: From Algebra to Topology (and many other places)
Abstract: As everything in category theory, monad is a concept encompassing a wide range of constructions in mathematics. We will go through many examples of monads and observe some typical situations in which one may meet them, journeying through parts of algebra, topology, set theory and more.Note: This talk should be mostly accessible to people with zero knowledge of category theory. It has also some overlap with my talk at the Fall School of the Department of Algebra, but the emphasis will be put elsewhere.
26. 04. Sebastian Opper: Homological mirror symmetry: a bridge between two branches of geometry
Abstract: During his ICM address in 1994, Kontsevich proposed a highly influential conjecture which relates two vastly different areas of mathematics: symplectic geometry and algebraic geometry. The former is concerned with certain types of manifolds such as the surface of a donut or a cylinder. The latter studies zero sets of equations, for example the circle or the union of the two coordinate axes in the plane. The conjecture relates the two areas through the language of categories in a fascinating way making problems in one area approachable to the machinery (and big theorems) of the other area. I will give a basic overview about what the conjecture says and illustrate everything through accessible examples.
03. 05. Pavlo Yatsyna: You crossed the line too many times…
Abstract: Unlike the lyrics of pop songs, we shall describe rigorously what it means to cross the line, how can we account for it and how many times is too many. It will be a gentle introduction to the topic utilising ideas and tools from combinatorics, discrete geometry, and number theory.
10. 05. Piotr Miska (Kraków): Gosper's algorithm and multidimensional continued fractions
Abstract: Gosper's algorithm allows us to compute the coefficients of continued fraction expansion of e.g. linear combinations, products and quotients of two real numbers if we have their continued fraction expansions as the input. The aim of the talk is to present Gosper's algorithm and the proposition of its generalisation for multidimensional continued fractions.

Fall semester 2021

07. 10. Víťa Kala: Integers represented by ternary quadratic forms
Abstract: The study of integers represented by quadratic forms (such as sums of squares x² + y², x² + y² + z², …) has rich history that goes back at least to ancient Babylonia and that features impressive works by giants such as Gauss, or Bhargava (2014 Fields medalist). In the talk, I'll focus primarily on quadratic forms in 3 variables — I'll review some elementary results, as well as connections to modular forms. If time permits, I hope to finish with a surprising conjecture that came up in my recent paper with Tomas Hejda.
14. 10. Francesco Genovese: Linearized scaffolds of spaces: an invitation to homological algebra
Abstract: It is common to treat complicated mathematical objects by reducing them to something which is „linear“ so that one can use the powerful tools of linear algebra — think of differentials of functions, for example. In this talk I will show you that even topological spaces can be in a certain way „linearized“ and reduced to nice algebraic gadgets called chain complexes, which we can conveniently manipulate to extract a useful invariant, namely, homology. Chain complexes (and homology) can be manipulated abstractly, and this is essentially what homological algebra is about. I will show you a few basics of the subject and then give a glance at some more advanced tools I use in my daily life as a researcher.
21. 10. Michael Kompatscher: Solving equations: a computational perspective
Abstract: In this talk I would like to discuss the computational complexity of solving polynomial equations t(x₁,…,x_n) = s(x₁,…,x_n) over a fixed algebra A. For infinite algebras this equation solvability problem can be arbitrarily hard and even undecidable, as the MRDP theorem famously showed for (Z, +, 0, –, •) (settling Hilbert's tenth problem). However, over finite algebras, equations can always be decided by „guessing" solutions; in other words, solving equations is in NP. It is then of major interest to distinguish algebras for which the equation solvability problem has an efficient algorithm (P), is hard (NP-complete), or possibly of some NP-intermediate complexity. I am going to discuss some known results (and pitfalls) when classifying the equation solvability problem for finite rings and groups. If the time permits, I will also present some generalization to algebras with a Maltsev term.
28. 10. no colloquium — Independent Czechoslovak State Day
04. 11. no colloquium — Fall school
11. 11. Kristóf Huszár (INRIA): Topology from the Computational Viewpoint
Abstract: Ever since its early developments, topology has been interspersed with combinatorial ideas, and thus it is not surprising that many of its fundamental problems call for an algorithmic solution. Indeed, for over a century a great deal of research in topology has been driven by the Homeomorphism Problem (the problem of deciding whether two triangulated manifolds are homeomorphic) and special cases thereof, such as the problems of Sphere Recognition or Unknot Recognition. This talk aims to give a glimpse into some of the computational aspects of topology, in particular in low dimensions. After discussing Markov's classical result on the undecidability of the Homeomorphism Problem in dimensions four or above, we shift our focus on 3-dimensional manifolds, where, even though problems are often decidable, there are many challenges to be resolved.
Slides
18. 11. Eric Nathan Stucky: Algebra of Parking Functions
Abstract: Originally considered in the 1960s by computer scientists, parking functions have risen to be a central object of study in combinatorial theory. In this talk we will define what these objects are and discuss some of their algebraic aspects, with an eye toward the parking space conjectures of Armstrong, Reiner, and Rhodes.
25. 11. Liran Shaul: The Cohen-Macaulay property, its applications and generalizations
Abstract: In linear algebra, we learn that the maximal number of independent linear equations we can impose on Rⁿ is equal to n. Generalizing this simple fact to commutative algebra and algebraic geometry leads to the notions of Cohen-Macaulay rings and Cohen-Macaulay varieties. In this talk we explain this notion, discuss its algebraic and geometric meaning, and demonstrate its various applications in algebra, geometry and combinatorics. Finally, if time permits, we discuss a recent generalization of this notion.
09. 12. Jordan Williamson: Local cohomology and classification theorems
Abstract: Local cohomology was introduced by Grothendieck in the 1960s and has since become an indispensable tool in commutative algebra. In this talk I will focus on introducing some more modern applications of local cohomology to the field of tensor-triangulated geometry where it can be used to define support theories and classify certain kind of classes.
16. 12. Gábina Těthalová: From Polyphony to Painting via Möbius stripe.. and back
Abstract: We will introduce selected principles that can serve as inspiration in art work and illustrate them on concrete examples. A joint feature of these points of inspiration — both counterpoint in polyphony music and the Möbius strip — is their existence in the language of mathematics. Also repeated picture patterns and work with visual language and its structure can act similarly. To what extent one actually uses these rules or, conversely, in artistic rendering breaks them, or if it is simply a subjective interpretation — each listener will have to form their own opinion on this :-)