Algebra colloquium

It takes place on Tuesdays 15:40 at K1. We start on October 10! 

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.

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 :-)