# 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.

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

## 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 An or Sn behaves like a „random“ degree-n rational function. I will describe all degree-n rational functions whose monodromy group is not An or Sn 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 Xn 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 An → 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 cn*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 Rn and we have a mapping f from Omega to Rn 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.
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 Rn. The lattice point generating function of P is defined as the sum over lattice points v in P of monomials xv. 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 Rn 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 x2 + y2, x2 + y2 + z2, …) 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(x1,…,xn) = s(x1,…,xn) 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 Rn 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 :-)