Reducing complexity in algebra, logic, combinatorics

project REDCOM funded by Fondazione Cariverona, program “Ricerca Scientifica di Eccellenza 2018”

Workshop - 29 January, 12 February 2021


Abstracts


Giulio Fellin
Modal Logic for Induction

We use modal logic to obtain syntactical, proof-theoretic versions of transfinite induction as axioms or rules within an appropriate labelled sequent calculus. While transfinite induction proper, also known as Noetherian induction, can be represented by a rule, the variant in which induction is done up to an arbitrary but fixed level happens to correspond to the Gödel–Löb axiom of provability logic. To verify the practicability of our approach in actual practice, we sketch a fairly universal pattern for proof transformation and test its use in several cases. Among other things, we give a direct and elementary syntactical proof of Segerberg’s theorem that the Gödel–Löb axiom characterises precisely the (converse) well-founded and transitive Kripke frames. This is joint work with Sara Negri and Peter Schuster.


Giovanna Le Gros
Enveloping and n-tilting classes over commutative rings

In this talk, we will discuss approximations by tilting classes over commutative rings, where tilting classes are generated by infinitely generated tilting modules. Recently, all the commutative rings over which 1-tilting classes are enveloping were classified. This used the classification of 1-tilting classes over commutative rings by faithful finitely generated Gabriel topologies proved by Hrbek. This classification was extended to the general tilting case by Hrbek-Stovicek, where instead the correspondence is with suitable finite sequences of Gabriel topologies. In this talk we will discuss some results toward the classification of tilting cotorsion pairs that provide approximations, using Hrbek and Stovicek's classification. In particular, we will discuss how considering an induced tilting class in suitable factor rings retains useful properties of the original tilting class and their approximations.
This talk is based on current work with Dolors Herbera.


Lorenzo Martini
Local Coherence of Hearts associated with Thomason Filtrations

Prompted by a recent paper of Saorin and Stovicek, in which it is proved that the heart of a compactly generated t-structure in a triangulated category with coproducts is a locally finitely presented Grothendieck category, and inspired by a work of Hrbek, we study the local coherence of hearts associated with Thomason filtrations of the prime spectrum of a commutative ring, achieving a useful characterisation in case of finite length filtrations. Moreover, low length values recover crucial examples of (locally finitely presented) abelian categories, e.g. certain torsion classes of modules and their Happel-Reiten-Smalo hearts.


Davide Mattiolo  Nowhere-zero flows in graphs

Given an integer k ≥ 2, a nowhere-zero k-flow, or k-NZF, in a graph G = (V,E) is a pair (D,f), where D is an orientation of G and f : E → {±1, . . . , ±(k − 1)} such that, at every vertex
v ∈ V , the sum of all incoming flow values equals the sum of all outgoing flow values in the chosen orientation D. It is well known that nowhere-zero flows generalize the concept of face-colorings of planar graphs, indeed, in 1954, Tutte observed that a planar graph has a face-k-coloring if and only if it has a k-NZF. He further conjectured that every bridgeless graph has a 5-NZF. This is one of the most outstanding open problems in Graph Theory, known as Tutte’s 5-flow Conjecture.
Tutte’s Conjecture is equivalent to its restriction to cubic graphs not having a 3-edge-coloring. In particular, a minimal counterexample, if any, must be found in the class of snarks which are cyclically 4- edge-connected, non-3-edge-colorable cubic graphs with girth at least 5.
In this talk we briefly introduce the theory of nowhere-zero flows in graphs and present some new results.


Francesco Sentieri
A brick version of Auslander's theorem

Given a finite dimensional algebra A, a classical result of Aulander shows that the set of indecomposable modules over A ( up to isomorphism ) is finite if and only if every indecomposable A-module is finite dimensional.  In this talk we discuss an analogous result, relating torsion classes in the category of finite dimensional A-modules with bricks,
that is modules whose endomorphism ring is a skew field. We obtain that the set of torsion classes is finite if and only if every brick over A is finite dimensional.


Daniel Wessel
Making the use of maximal ideals inductive

Krull’s maximal ideal theorem (MIT) is one of the most prominent incarnations of the axiom of choice (AC) in ring theory. For many a consequence of AC, constructive counterparts are well within reach, provided attention is turned to the syntactical underpinning of the problem at hand. In this vein, we attempt a new reading of MIT by relating the Jacobson radical to a certain inductively generated class of finite binary trees. Incidentally, this sheds new light on Yengui's backtracking technique.


Franziskus Wiesnet
Zariskis lemma and its computational content

This presentation is useful for everyone who is interested in using constructive proofs to generate algorithms. Zariski's lemma is a well-know statement in algebra and was used by Oskar Zariski to prove Hilbert's Nullstellensatz. But there may be related approaches in many other areas of constructive mathematics and the presentation only requires a basic knowledge of algebra. We discuss proof interpretation in algebra by the example of Zariski's lemma. Our approach is divided in to three steps. As a starting point we formulate a constructive proof of Zariski's lemma. As second step we formulate a computational interpretation of the statement and the used lemmas. Finally, we use the proof of the first step to establish an algorithm which realises the interpretation of the second step. In particular, we highlight on which objects the algorithm operates, which objects are needed for the whole computational interpretation, and how one can obtain this by using the constructive proof.
 

Jean Paul Zerafa
Perfect matchings in Modena

In this talk I will briefly go through the research I have done whilst being a PhD student in Modena (UNIMORE) under the supervision of Prof. Giuseppe Mazzuoccolo. My main area of research has been the behaviour of perfect matchings in graphs, in particular, (i) snarks and (ii) Hamiltonian graphs.
In the first part, we shall consider snarks, which are crucial when considering conjectures about bridgeless cubic graphs, mostly because if such statements are true for snarks, then they would be true for all bridgeless cubic graphs. One such conjecture which is known for its simple statement, but still indomitable after half a century, is the Berge–Fulkerson Conjecture. In this talk we shall have the opportunity to discuss this conjecture but also other related and well-known conjectures about the behaviour of perfect matchings in bridgeless cubic graphs, in particular, the Fan–Raspaud Conjecture (Fan and Raspaud, 1994) and the S4-Conjecture (Mazzuoccolo, 2013). Given the obstacles encountered when dealing with such problems, many have considered trying to bridge the gap between Class I (3-edge-colourable) and Class II (4- edge-colourable) bridgeless cubic graphs by looking at invariants that measure how far Class II bridgeless cubic graphs are from being Class I. In this spirit, we shall also discuss a parameter which gives the least number of perfect matchings (not necessarily distinct) needed to be added to a bridgeless cubic graph such that the resulting multigraph is Class I.
In the second part, we shall consider Hamiltonian graphs (admitting a perfect matching). If every perfect matching of such a graph can be extended to a Hamiltonian circuit, then the graph is said to have the Perfect-Matching-Hamiltonian property (for short, the PMH-property). This property was first studied in the 1970s by Las Vergnas and Häggkvist, and was generalised and recently brought to the limelight once again by Fink (2007). One of the main results in this second part contains some sufficient conditions for a graph to ensure that every perfect matching of its line graph can be extended to a Hamiltonian circuit. We also consider the above properties in relation to quartic graphs.