Showing 1–50 of 52 results for author: Paolini, G

Around first-order rigidity of Coxeter groups

Authors: Simon André, Gianluca Paolini

Abstract: By the work of Sela, for any free group $F$, the Coxeter group $W_ 3 = \mathbb{Z}/2\mathbb{Z} \ast \mathbb{Z}/2\mathbb{Z} \ast \mathbb{Z}/2\mathbb{Z}$ is elementarily equivalent to $W_3 \ast F$, and so Coxeter groups are not closed under elementary equivalence among finitely generated groups. In this paper we show that if we restrict to models which are generated by finitely many torsion elements… ▽ More By the work of Sela, for any free group $F$, the Coxeter group $W_ 3 = \mathbb{Z}/2\mathbb{Z} \ast \mathbb{Z}/2\mathbb{Z} \ast \mathbb{Z}/2\mathbb{Z}$ is elementarily equivalent to $W_3 \ast F$, and so Coxeter groups are not closed under elementary equivalence among finitely generated groups. In this paper we show that if we restrict to models which are generated by finitely many torsion elements (finitely torsion-generated), then we can recover striking rigidity results. Our main result is that if $(W, S)$ is a Coxeter system whose irreducible components are either spherical, or affine or (Gromov) hyperbolic, and $G$ is finitely torsion-generated and elementarily equivalent to $W$, then $G$ is itself a Coxeter group. This combines results of the second author et al. from [MPS22, PS23] with the following main hyperbolic result: if $W$ is a Coxeter hyperbolic group and $G$ is $\mathrm{AE}$-equivalent to $W$ and finitely torsion-generated, then $G$ belongs to a finite collection of Coxeter groups (modulo isomorphism). Furthermore, we show that there are two hyperbolic Coxeter groups $W$ and $W'$ which are non-isomorphic but $\mathrm{AE}$-equivalent. We also show that, on other hand, if we restrict to certain specific classes of Coxeter groups then we can recover the strongest possible form of first-order rigidity, which we call first-order torsion-rigidity, namely the Coxeter group $W$ is the only finitely torsion-generated model of its theory. Crucially, we show that this form of rigidity holds for the following classes of Coxeter groups: even hyperbolic Coxeter groups and free products of one-ended or finite hyperbolic Coxeter groups. We conjecture that the same kind of phenomena occur for the whole class of Coxeter groups. In this direction, we prove that if $W$ and $W'$ are even Coxeter groups which are elementarily equivalent, then they are isomorphic. △ Less

Submitted 1 July, 2024; originally announced July 2024.

MSC Class: 03C60; 20F55

Profinite rigidity of affine Coxeter groups

Authors: Gianluca Paolini, Rizos Sklinos

Abstract: We prove that the irreducible affine Coxeter groups are first-order rigid and deduce from this that they are profinitely rigid in the absolute sense. We then show that the first-order theory of any irreducible affine Coxeter group does not have a prime model. Finally, we prove that universal Coxeter groups of finite rank are homogeneous, and that the same applies to every hyperbolic (in the sense… ▽ More We prove that the irreducible affine Coxeter groups are first-order rigid and deduce from this that they are profinitely rigid in the absolute sense. We then show that the first-order theory of any irreducible affine Coxeter group does not have a prime model. Finally, we prove that universal Coxeter groups of finite rank are homogeneous, and that the same applies to every hyperbolic (in the sense of Gromov) one-ended right-angled Coxeter group. △ Less

Submitted 2 July, 2024; v1 submitted 1 July, 2024; originally announced July 2024.

MSC Class: 03C60; 20F55

The Isomorphism Problem for Oligomorphic Groups with Weak Elimination of Imaginaries

Authors: Gianluca Paolini

Abstract: In [21] it was asked if equality on the reals is sharp as a lower bound for the complexity of topological isomorphism between oligomorphic groups. We prove that under the assumption of weak elimination of imaginaries this is indeed the case. Our methods are model theoretic and they also have applications on the classical problem of reconstruction of isomorphisms of permutation groups from (topolog… ▽ More In [21] it was asked if equality on the reals is sharp as a lower bound for the complexity of topological isomorphism between oligomorphic groups. We prove that under the assumption of weak elimination of imaginaries this is indeed the case. Our methods are model theoretic and they also have applications on the classical problem of reconstruction of isomorphisms of permutation groups from (topological) isomorphisms of automorphisms groups. As a concrete application, we give an explicit description of $\mathrm{Aut}(\mathrm{GL}(V))$ for any vector space $V$ of dimension $\aleph_0$ over a finite field, in affinity with the classical description for finite dimensional spaces due to Schreier and van der Waerden. △ Less

Submitted 6 April, 2024; originally announced April 2024.

MSC Class: 03E15; 20B27; 22A05; 20F28

Computable Scott sentences and the weak Whitehead problem for finitely presented groups

Authors: Gianluca Paolini

Abstract: We prove that if $A$ is a computable Hopfian finitely presented structure, then $A$ has a computable $d$-$Σ_2$ Scott sentence if and only if the weak Whitehead problem for $A$ is decidable. We use this to infer that every hyperbolic group as well as any polycyclic-by-finite group has a computable $d$-$Σ_2$ Scott sentence, thus covering two main classes of finitely presented groups. Our proof also… ▽ More We prove that if $A$ is a computable Hopfian finitely presented structure, then $A$ has a computable $d$-$Σ_2$ Scott sentence if and only if the weak Whitehead problem for $A$ is decidable. We use this to infer that every hyperbolic group as well as any polycyclic-by-finite group has a computable $d$-$Σ_2$ Scott sentence, thus covering two main classes of finitely presented groups. Our proof also implies that every weakly Hopfian finitely presented group is strongly defined by its $\exists^+$-types, a question which arose in a different context. △ Less

Submitted 27 March, 2024; v1 submitted 29 December, 2023; originally announced January 2024.

MSC Class: 03C57; 20F10

Torsion-free abelian groups are faithfully Borel complete and pure embeddability is a complete analytic quasi-order

Authors: Gianluca Paolini, Saharon Shelah

Abstract: In [9] we proved that the space of countable torsion-free abelian groups is Borel complete. In this paper we show that our construction from [9] satisfies several additional properties of interest. We deduce from this that countable torsion-free abelian groups are faithfully Borel complete, in fact, more strongly, we can $\mathfrak{L}_{ω_1, ω}$-interpret countable graphs in them. Secondly, we show… ▽ More In [9] we proved that the space of countable torsion-free abelian groups is Borel complete. In this paper we show that our construction from [9] satisfies several additional properties of interest. We deduce from this that countable torsion-free abelian groups are faithfully Borel complete, in fact, more strongly, we can $\mathfrak{L}_{ω_1, ω}$-interpret countable graphs in them. Secondly, we show that the relation of pure embeddability (equiv., elementary embeddability) among countable models of $\mathrm{Th}(\mathbb{Z}^{(ω)})$ is a complete analytic quasi-order. △ Less

Submitted 7 December, 2023; originally announced December 2023.

MSC Class: 03E15; 20K20

Elementary Properties of Free Lattices

Authors: J. B. Nation, Gianluca Paolini

Abstract: We start a systematic analysis of the first-order model theory of free lattices. Firstly, we prove that the free lattices of finite rank are not positively indistinguishable, as there is a positive $\exists \forall$-sentence true in $\mathbf F_3$ and false in $\mathbf F_4$. Secondly, we show that every model of $\mathrm{Th}(\mathbf F_n)$ admits a canonical homomorphism into the profinite-bounded c… ▽ More We start a systematic analysis of the first-order model theory of free lattices. Firstly, we prove that the free lattices of finite rank are not positively indistinguishable, as there is a positive $\exists \forall$-sentence true in $\mathbf F_3$ and false in $\mathbf F_4$. Secondly, we show that every model of $\mathrm{Th}(\mathbf F_n)$ admits a canonical homomorphism into the profinite-bounded completion $\mathbf H_n$ of $\mathbf F_n$. Thirdly, we show that $\mathbf H_n$ is isomorphic to the Dedekind-MacNeille completion of $\mathbf F_n$, and that $\mathbf H_n$ is not positively elementarily equivalent to $\mathbf F_n$, as there is a positive $\forall\exists$-sentence true in $\mathbf H_n$ and false in $\mathbf F_n$. Finally, we show that $\mathrm{DM}(\mathbf F_n)$ is a retract of $\mathrm{Id}(\mathbf F_n)$ and that for any lattice $\mathbf K$ which satisfies Whitman's condition $\mathrm{(W)}$ and which is generated by join prime elements, the three lattices $\mathbf K$, $\mathrm{DM}(\mathbf K)$, and $\mathrm{Id}(\mathbf K)$ all share the same positive universal first-order theory. △ Less

Submitted 27 March, 2024; v1 submitted 5 October, 2023; originally announced October 2023.

Comments: 13 pages

MSC Class: 03C05; 03C64; 06B05

The construction principle and non homogeneity of uncountable relatively free groups

Authors: Davide Carolillo, Gianluca Paolini

Abstract: In [11] Sklinos proved that any uncountable free group is not $\aleph_1$-homogenenous. This was later generalized by Belegradek in [1] to torsion-free residually finite relatively free groups, leaving open whether the assumption of residual finiteness was necessary. In this paper we use methods arising from the classical analysis of relatively free groups in infinitary logic to answer Belegradek's… ▽ More In [11] Sklinos proved that any uncountable free group is not $\aleph_1$-homogenenous. This was later generalized by Belegradek in [1] to torsion-free residually finite relatively free groups, leaving open whether the assumption of residual finiteness was necessary. In this paper we use methods arising from the classical analysis of relatively free groups in infinitary logic to answer Belegradek's question in the negative. Our methods are general and they also applications in varieties with torsion, for example we show that if $V$ contains a non-solvable group, then any uncountable $V$-free group is not $\aleph_1$-homogenenous. △ Less

Submitted 22 April, 2024; v1 submitted 20 July, 2023; originally announced July 2023.

MSC Class: 20E10; 03C50

Anti-Classification Results for Rigidity Conditions in Abelian and Nilpotent Groups

Authors: Gianluca Paolini, Saharon Shelah

Abstract: Relying on the techniques and ideas from our recent paper [13], we prove several anti-classification results for various rigidity conditions in countable abelian and nilpotent groups. We prove three main theorems: (1) the rigid abelian groups are complete co-analytic in the space of countable torsion-free abelian groups ($\mathrm{TFAB}_ω$); (2) the Hopfian groups are complete co-analytic in… ▽ More Relying on the techniques and ideas from our recent paper [13], we prove several anti-classification results for various rigidity conditions in countable abelian and nilpotent groups. We prove three main theorems: (1) the rigid abelian groups are complete co-analytic in the space of countable torsion-free abelian groups ($\mathrm{TFAB}_ω$); (2) the Hopfian groups are complete co-analytic in $\mathrm{TFAB}_ω$; (3) the co-Hopfian groups are complete co-analytic in the space of countable $2$-nilpotent groups. In combination with our result from [13, S5], which shows that the endo-rigid abelian groups are complete co-analytic in $\mathrm{TFAB}_ω$, this shows that four major notions of rigidity from (abelian) group theory are as complex as possible as co-analytic problems. Further, the second and third theorem above solve two open questions of Thomas from [18], who asked this for the space of all countable groups. We leave open the question of whether the co-Hopfian mixed abelian groups are complete co-analytic in the space of countable abelian groups, but we reduce the problem to a concrete question on profinite groups, showing that if $G$ is a countable co-Hopfian abelian reduced group, then, for every prime number $p$, the torsion subgroup $\mathrm{Tor}_p(G)$ of $G$ is finite and $G$ embeds in the profinite group $ \prod_{p \in \mathbb{P}} \mathrm{Tor}_p(G)$. △ Less

Submitted 5 December, 2023; v1 submitted 7 March, 2023; originally announced March 2023.

MSC Class: 03E15; 20K20; 20K30

Dual structures on Coxeter and Artin groups of rank three

Authors: Emanuele Delucchi, Giovanni Paolini, Mario Salvetti

Abstract: We extend the theory of dual Coxeter and Artin groups to all rank-three Coxeter systems, beyond the previously studied spherical and affine cases. Using geometric, combinatorial, and topological techniques, we show that rank-three noncrossing partition posets are EL-shellable lattices and give rise to Garside groups isomorphic to the associated standard Artin groups. Within this framework, we prov… ▽ More We extend the theory of dual Coxeter and Artin groups to all rank-three Coxeter systems, beyond the previously studied spherical and affine cases. Using geometric, combinatorial, and topological techniques, we show that rank-three noncrossing partition posets are EL-shellable lattices and give rise to Garside groups isomorphic to the associated standard Artin groups. Within this framework, we prove the $K(π, 1)$ conjecture, the triviality of the center, and the solubility of the word problem for rank-three Artin groups. Some of our constructions apply to general Artin groups; we hope they will help develop complete solutions to the $K(π, 1)$ conjecture and other open problems in the area. △ Less

Submitted 29 June, 2022; originally announced June 2022.

Rectangular analogues of the square paths conjecture and the univariate Delta conjecture

Authors: Alessandro Iraci, Roberto Pagaria, Giovanni Paolini, Anna Vanden Wyngaerd

Abstract: In this paper, we extend the rectangular side of the shuffle conjecture by stating a rectangular analogue of the square paths conjecture. In addition, we describe a set of combinatorial objects and one statistic that are a first step towards a rectangular extension of (the rise version of) the Delta conjecture, and of (the rise version of) the Delta square conjecture, corresponding to the case… ▽ More In this paper, we extend the rectangular side of the shuffle conjecture by stating a rectangular analogue of the square paths conjecture. In addition, we describe a set of combinatorial objects and one statistic that are a first step towards a rectangular extension of (the rise version of) the Delta conjecture, and of (the rise version of) the Delta square conjecture, corresponding to the case $q=1$ of an expected general statement. We also prove our new rectangular paths conjecture in the special case when the sides of the rectangle are coprime. △ Less

Submitted 31 May, 2022; originally announced June 2022.

Comments: 20 pages, 9 figures

MSC Class: 05E05

Journal ref: Combinatorial Theory (2023), 3(2)

The dual approach to the $K(π, 1)$ conjecture

Authors: Giovanni Paolini

Abstract: Dual presentations of Coxeter groups have recently led to breakthroughs in our understanding of affine Artin groups. In particular, they led to the proof of the $K(π, 1)$ conjecture and to the solution of the word problem. Will the "dual approach" extend to more general classes of Coxeter and Artin groups? In this paper, we describe the techniques used to prove the $K(π, 1)$ conjecture for affine… ▽ More Dual presentations of Coxeter groups have recently led to breakthroughs in our understanding of affine Artin groups. In particular, they led to the proof of the $K(π, 1)$ conjecture and to the solution of the word problem. Will the "dual approach" extend to more general classes of Coxeter and Artin groups? In this paper, we describe the techniques used to prove the $K(π, 1)$ conjecture for affine Artin groups and we ask a series of questions that are mostly open beyond the spherical and affine cases. △ Less

Submitted 9 December, 2021; originally announced December 2021.

On the Existence of Uncountable Hopfian and co-Hopfian Abelian Groups

Authors: Gianluca Paolini, Saharon Shelah

Abstract: We deal with the problem of existence of uncountable co-Hopfian abelian groups and (absolute) Hopfian abelian groups. Firstly, we prove that there are no co-Hopfian reduced abelian groups $G$ of size $< \mathfrak{p}$ with infinite $\mathrm{Tor}_p(G)$, and that in particular there are no infinite reduced abelian $p$-groups of size $< \mathfrak{p}$. Secondly, we prove that if… ▽ More We deal with the problem of existence of uncountable co-Hopfian abelian groups and (absolute) Hopfian abelian groups. Firstly, we prove that there are no co-Hopfian reduced abelian groups $G$ of size $< \mathfrak{p}$ with infinite $\mathrm{Tor}_p(G)$, and that in particular there are no infinite reduced abelian $p$-groups of size $< \mathfrak{p}$. Secondly, we prove that if $2^{\aleph_0} < λ< λ^{\aleph_0}$, and $G$ is abelian of size $λ$, then $G$ is not co-Hopfian. Finally, we prove that for every cardinal $λ$ there is a torsion-free abelian group $G$ of size $λ$ which is absolutely Hopfian, i.e., $G$ is Hopfian and $G$ remains Hopfian in every forcing extensions of the universe. △ Less

Submitted 31 August, 2023; v1 submitted 23 July, 2021; originally announced July 2021.

MSC Class: 20K30; 03E75

Factoring isometries of quadratic spaces into reflections

Authors: Jon McCammond, Giovanni Paolini

Abstract: Let $V$ be a vector space endowed with a non-degenerate quadratic form $Q$. If the base field $\mathbb{F}$ is different from $\mathbb{F}_2$, it is known that every isometry can be written as a product of reflections. In this article, we detail the structure of the poset of all minimal length reflection factorizations of an isometry. If $\mathbb{F}$ is an ordered field, we also study factorizations… ▽ More Let $V$ be a vector space endowed with a non-degenerate quadratic form $Q$. If the base field $\mathbb{F}$ is different from $\mathbb{F}_2$, it is known that every isometry can be written as a product of reflections. In this article, we detail the structure of the poset of all minimal length reflection factorizations of an isometry. If $\mathbb{F}$ is an ordered field, we also study factorizations into positive reflections, i.e., reflections defined by vectors of positive norm. We characterize such factorizations, under the hypothesis that the squares of $\mathbb{F}$ are dense in the positive elements (this includes Archimedean and Euclidean fields). In particular, we show that an isometry is a product of positive reflections if and only if its spinor norm is positive. As a final application, we explicitly describe the poset of all factorizations of isometries of the hyperbolic space. △ Less

Submitted 3 March, 2021; originally announced March 2021.

Torsion-Free Abelian Groups are Borel Complete

Authors: Gianluca Paolini, Saharon Shelah

Abstract: We prove that the Borel space of torsion-free Abelian groups with domain $ω$ is Borel complete, i.e., the isomorphism relation on this Borel space is as complicated as possible, as an isomorphism relation. This solves a long-standing open problem in descriptive set theory, which dates back to the seminal paper on Borel reducibility of Friedman and Stanley from 1989. We prove that the Borel space of torsion-free Abelian groups with domain $ω$ is Borel complete, i.e., the isomorphism relation on this Borel space is as complicated as possible, as an isomorphism relation. This solves a long-standing open problem in descriptive set theory, which dates back to the seminal paper on Borel reducibility of Friedman and Stanley from 1989. △ Less

Submitted 21 February, 2023; v1 submitted 24 February, 2021; originally announced February 2021.

MSC Class: 03E15; 20K20; 20K30

Computable Scott Sentences for Quasi-Hopfian Finitely Presented Structures

Authors: Gianluca Paolini

Abstract: We prove that every quasi-Hopfian finitely presented structure $A$ has a $d$-$Σ_2$ Scott sentence, and that if in addition $A$ is computable and $Aut(A)$ satisfies a natural computable condition, then $A$ has a computable $d$-$Σ_2$ Scott sentence. This unifies several known results on Scott sentences of finitely presented structures and it is used to prove that other not previously considered alge… ▽ More We prove that every quasi-Hopfian finitely presented structure $A$ has a $d$-$Σ_2$ Scott sentence, and that if in addition $A$ is computable and $Aut(A)$ satisfies a natural computable condition, then $A$ has a computable $d$-$Σ_2$ Scott sentence. This unifies several known results on Scott sentences of finitely presented structures and it is used to prove that other not previously considered algebraic structures of interest have computable $d$-$Σ_2$ Scott sentences. In particular, we show that every right-angled Coxeter group of finite rank has a computable $d$-$Σ_2$ Scott sentence, as well as any strongly rigid Coxeter group of finite rank. Finally, we show that the free projective plane of rank $4$ has a computable $d$-$Σ_2$ Scott sentence, thus exhibiting a natural example where the assumption of quasi-Hopfianity is used (since this structure is not Hopfian). △ Less

Submitted 1 February, 2022; v1 submitted 25 October, 2020; originally announced October 2020.

Comments: 10 pages

MSC Class: 03C57; 03D45

First-Order Aspects of Coxeter Groups

Authors: Bernhard Muhlherr, Gianluca Paolini, Saharon Shelah

Abstract: We lay the foundations of the first-order model theory of Coxeter groups. Firstly, with the exception of the $2$-spherical non-affine case (which we leave open), we characterize the superstable Coxeter groups of finite rank, which we show to be essentially the Coxeter groups of affine type. Secondly, we characterize the Coxeter groups of finite rank which are domains, a central assumption in the t… ▽ More We lay the foundations of the first-order model theory of Coxeter groups. Firstly, with the exception of the $2$-spherical non-affine case (which we leave open), we characterize the superstable Coxeter groups of finite rank, which we show to be essentially the Coxeter groups of affine type. Secondly, we characterize the Coxeter groups of finite rank which are domains, a central assumption in the theory of algebraic geometry over groups, which in many respects (e.g. $λ$-stability) reduces the model theory of a given Coxeter system to the model theory of its associated irreducible components. In the second part of the paper we move to specific definability questions in right-angled Coxeter groups (RACGs) and $2$-spherical Coxeter groups. In this respect, firstly, we prove that RACGs of finite rank do not have proper elementary subgroups which are Coxeter groups, and prove further that reflection independent ones do not have proper elementary subgroups at all. Secondly, we prove that if the monoid $Sim(W, S)$ of $S$-self-similarities of $W$ is finitely generated, then $W$ is a prime model of its theory. Thirdly, we prove that in reflection independent RACGs of finite rank the Coxeter elements are type-determined. We then move to $2$-spherical Coxeter groups, proving that if $(W, S)$ is irreducible, $2$-spherical even and not affine, then $W$ is a prime model of its theory, and that if $W_Γ$ and $W_Θ$ are as in the previous sentence, then $W_Γ$ is elementary equivalent to $W_Θ$ if and only if $Γ\cong Θ$, thus solving the elementary equivalence problem for most of the $2$-spherical Coxeter groups. In the last part of the paper we focus on model theoretic applications of the notion of reflection length from Coxeter group theory, proving in particular that affine Coxeter groups are not connected. △ Less

Submitted 1 February, 2022; v1 submitted 25 October, 2020; originally announced October 2020.

Comments: 38 pages

MSC Class: 03C45; 03C68; 20F55; 51F15

A table of $n$-component handlebody links of genus $n+1$ up to six crossings

Authors: Giovanni Bellettini, Giovanni Paolini, Maurizio Paolini, Yi-Sheng Wang

Abstract: A handlebody link is a union of handlebodies of positive genus embedded in 3-space, which generalizes the notion of links in classical knot theory. In this paper, we consider handlebody links with one genus 2 handlebody and $n-1$ solid tori, $n>1$. Our main result is the complete classification of such handlebody links with six crossings or less, up to ambient isotopy. A handlebody link is a union of handlebodies of positive genus embedded in 3-space, which generalizes the notion of links in classical knot theory. In this paper, we consider handlebody links with one genus 2 handlebody and $n-1$ solid tori, $n>1$. Our main result is the complete classification of such handlebody links with six crossings or less, up to ambient isotopy. △ Less

Submitted 22 March, 2020; v1 submitted 8 March, 2020; originally announced March 2020.

Comments: 21 pages, 17 figures, 8 tables; title changed, typos corrected, added one reference

MSC Class: 57M25; 57M15; 57M27; 54C25

Representations of torsion-free arithmetic matroids

Authors: Roberto Pagaria, Giovanni Paolini

Abstract: We study the representability problem for torsion-free arithmetic matroids. By using a new operation called "reduction" and a "signed Hermite normal form", we provide and implement an algorithm to compute all the representations, up to equivalence. As an application, we disprove two conjectures about the poset of layers and the independence poset of a toric arrangement. We study the representability problem for torsion-free arithmetic matroids. By using a new operation called "reduction" and a "signed Hermite normal form", we provide and implement an algorithm to compute all the representations, up to equivalence. As an application, we disprove two conjectures about the poset of layers and the independence poset of a toric arrangement. △ Less

Submitted 12 August, 2019; originally announced August 2019.

Report number: 103272 MSC Class: 05B35; 14N20

Journal ref: European Journal of Combinatorics Volume 93, March 2021

Proof of the $K(π,1)$ conjecture for affine Artin groups

Authors: Giovanni Paolini, Mario Salvetti

Abstract: We prove the $K(π,1)$ conjecture for affine Artin groups: the complexified complement of an affine reflection arrangement is a classifying space. This is a long-standing problem, due to Arnol'd, Pham, and Thom. Our proof is based on recent advancements in the theory of dual Coxeter and Artin groups, as well as on several new results and constructions. In particular: we show that all affine noncros… ▽ More We prove the $K(π,1)$ conjecture for affine Artin groups: the complexified complement of an affine reflection arrangement is a classifying space. This is a long-standing problem, due to Arnol'd, Pham, and Thom. Our proof is based on recent advancements in the theory of dual Coxeter and Artin groups, as well as on several new results and constructions. In particular: we show that all affine noncrossing partition posets are EL-shellable; we use these posets to construct finite classifying spaces for dual affine Artin groups; we introduce new CW models for the orbit configuration spaces associated with arbitrary Coxeter groups; we construct finite classifying spaces for the braided crystallographic groups introduced by McCammond and Sulway. △ Less

Submitted 6 December, 2020; v1 submitted 26 July, 2019; originally announced July 2019.

MSC Class: 20F36; 20F55; 55P20

Journal ref: Inventiones mathematicae (2020)

Strongly Minimal Steiner Systems I: Existence

Authors: John Baldwin, Gianluca Paolini

Abstract: A linear space is a system of points and lines such that any two distinct points determine a unique line; a Steiner $k$-system (for $k \geq 2$) is a linear space such that each line has size exactly $k$. Clearly, as a two-sorted structure, no linear space can be strongly minimal. We formulate linear spaces in a (bi-interpretable) vocabulary $τ$ with a single ternary relation $R$. We prove that for… ▽ More A linear space is a system of points and lines such that any two distinct points determine a unique line; a Steiner $k$-system (for $k \geq 2$) is a linear space such that each line has size exactly $k$. Clearly, as a two-sorted structure, no linear space can be strongly minimal. We formulate linear spaces in a (bi-interpretable) vocabulary $τ$ with a single ternary relation $R$. We prove that for every integer $k$ there exist $2^{\aleph_0}$-many integer valued functions $μ$ such that each $μ$ determines a distinct strongly minimal Steiner $k$-system $\mathcal{G}_μ$, whose algebraic closure geometry has all the properties of the ab initio Hrushovski construction. Thus each is a counterexample to the Zilber Trichotomy Conjecture. △ Less

Submitted 21 January, 2020; v1 submitted 8 March, 2019; originally announced March 2019.

MSC Class: 03C45; 51E10

Shellability of generalized Dowling posets

Authors: Giovanni Paolini

Abstract: A generalization of Dowling lattices was recently introduced by Bibby and Gadish, in a work on orbit configuration spaces. The authors left open the question as to whether these posets are shellable. In this paper we prove EL-shellability and use it to determine the homotopy type. Our result generalizes shellability of Dowling lattices and of posets of layers of abelian arrangements defined by roo… ▽ More A generalization of Dowling lattices was recently introduced by Bibby and Gadish, in a work on orbit configuration spaces. The authors left open the question as to whether these posets are shellable. In this paper we prove EL-shellability and use it to determine the homotopy type. Our result generalizes shellability of Dowling lattices and of posets of layers of abelian arrangements defined by root systems. We also show that subposets corresponding to invariant subarrangements are not shellable in general. △ Less

Submitted 3 December, 2023; v1 submitted 20 November, 2018; originally announced November 2018.

Journal ref: Journal of Combinatorial Theory, Series A 171, 2020

First-Order Model Theory of Free Projective Planes

Authors: Tapani Hyttinen, Gianluca Paolini

Abstract: We prove that the theory of open projective planes is complete and strictly stable, and infer from this that Marshall Hall's free projective planes $(π^n : 4 \leq n \leq ω)$ are all elementary equivalent and that their common theory is strictly stable and decidable, being in fact the theory of open projective planes. We further characterize the elementary substructure relation in the class of open… ▽ More We prove that the theory of open projective planes is complete and strictly stable, and infer from this that Marshall Hall's free projective planes $(π^n : 4 \leq n \leq ω)$ are all elementary equivalent and that their common theory is strictly stable and decidable, being in fact the theory of open projective planes. We further characterize the elementary substructure relation in the class of open projective planes, and show in particular that $(π^n : 4 \leq n \leq ω)$ is an elementary chain. We then prove that the theory of open projective planes does not have a prime model, that it has elimination of quantifiers down to Boolean combinations of existential formulas, and that it is not model complete. Finally, we characterize the forking independence relation in models of the theory and prove that the $π^n$'s ($4 \leq n \leq ω)$ are strongly type-homogeneous. △ Less

Submitted 10 February, 2020; v1 submitted 8 November, 2018; originally announced November 2018.

Comments: New version, several open questions have been solved

MSC Class: 03C45; 51E15

Some Results on Polish Groups

Authors: Gianluca Paolini, Saharon Shelah

Abstract: We prove that no quantifier-free formula in the language of group theory can define the $\aleph_1$-half graph in a Polish group, thus generalising some results from [6]. We then pose some questions on the space of groups of automorphisms of a given Borel complete class, and observe that this space must contain at least one uncountable group. Finally, we prove some results on the structure of the g… ▽ More We prove that no quantifier-free formula in the language of group theory can define the $\aleph_1$-half graph in a Polish group, thus generalising some results from [6]. We then pose some questions on the space of groups of automorphisms of a given Borel complete class, and observe that this space must contain at least one uncountable group. Finally, we prove some results on the structure of the group of automorphisms of a locally finite group: firstly, we prove that it is not the case that every group of automorphisms of a graph of power $λ$ is the group of automorphism of a locally finite group of power $λ$; secondly, we conjecture that the group of automorphisms of a locally finite group of power $λ$ has a locally finite subgroup of power $λ$, and reduce the problem to a problem on $p$-groups, thus settling the conjecture in the case $λ= \aleph_0$. △ Less

Submitted 10 November, 2019; v1 submitted 30 October, 2018; originally announced October 2018.

MSC Class: 03E15; 20K30; 20B27

On a Cardinal Invariant Related to the Haar Measure Problem

Authors: Gianluca Paolini, Saharon Shelah

Abstract: In [6], given a metrizable profinite group $G$, a cardinal invariant of the continuum $\mathfrak{fm}(G)$ was introduced, and a positive solution to the Haar Measure Problem for $G$ was given under the assumption that $\mathrm{non}(\mathcal{N}) \leq \mathfrak{fm}(G)$. We prove here that it is consistent with ZFC that there is a metrizable profinite group $G_*$ such that… ▽ More In [6], given a metrizable profinite group $G$, a cardinal invariant of the continuum $\mathfrak{fm}(G)$ was introduced, and a positive solution to the Haar Measure Problem for $G$ was given under the assumption that $\mathrm{non}(\mathcal{N}) \leq \mathfrak{fm}(G)$. We prove here that it is consistent with ZFC that there is a metrizable profinite group $G_*$ such that $\mathrm{non}(\mathcal{N}) > \mathfrak{fm}(G_*)$, thus demonstrating that the strategy of [6] does not suffice for a general solution to the Haar Measure Problem. △ Less

Submitted 20 June, 2019; v1 submitted 27 September, 2018; originally announced September 2018.

MSC Class: 03E17; 22C05; 20E18; 20A15

Euclidean matchings and minimality of hyperplane arrangements

Authors: Davide Lofano, Giovanni Paolini

Abstract: We construct a new class of maximal acyclic matchings on the Salvetti complex of a locally finite hyperplane arrangement. Using discrete Morse theory, we then obtain an explicit proof of the minimality of the complement. Our construction provides interesting insights also in the well-studied case of finite arrangements, and gives a nice geometric description of the Betti numbers of the complement.… ▽ More We construct a new class of maximal acyclic matchings on the Salvetti complex of a locally finite hyperplane arrangement. Using discrete Morse theory, we then obtain an explicit proof of the minimality of the complement. Our construction provides interesting insights also in the well-studied case of finite arrangements, and gives a nice geometric description of the Betti numbers of the complement. In particular, we solve a conjecture of Drton and Klivans on the characteristic polynomial of finite reflection arrangements. The minimal complex is compatible with restrictions, and this allows us to prove the isomorphism of Brieskorn's Lemma by a simple bijection of the critical cells. Finally, in the case of line arrangements, we describe the algebraic Morse complex which computes the homology with coefficients in an abelian local system. △ Less

Submitted 11 December, 2020; v1 submitted 7 September, 2018; originally announced September 2018.

Journal ref: Discrete Mathematics 344 (3), 2021

Invariant universality for projective planes

Authors: Filippo Calderoni, Gianluca Paolini

Abstract: We continue the work of [1, 2, 3] by analyzing the equivalence relation of bi-embeddability on various classes of countable planes, most notably the class of countable non-Desarguesian projective planes. We use constructions of the second author to show that these equivalence relations are invariantly universal, in the sense of [3], and thus in particular complete analytic. We also introduce a new… ▽ More We continue the work of [1, 2, 3] by analyzing the equivalence relation of bi-embeddability on various classes of countable planes, most notably the class of countable non-Desarguesian projective planes. We use constructions of the second author to show that these equivalence relations are invariantly universal, in the sense of [3], and thus in particular complete analytic. We also introduce a new kind of Borel reducibility relation for standard Borel G-spaces, which requires the preservation of stabilizers, and explain its connection with the notion of full embeddings commonly considered in category theory. △ Less

Submitted 14 October, 2020; v1 submitted 30 January, 2018; originally announced January 2018.

Comments: Unpublished notes, 10 pages

Automorphism Groups of Countable Stable Structures

Authors: Gianluca Paolini, Saharon Shelah

Abstract: For every countable structure $M$ we construct an $\aleph_0$-stable countable structure $N$ such that $Aut(M)$ and $Aut(N)$ are topologically isomorphic. This shows that it is impossible to detect any form of stability of a countable structure $M$ from the topological properties of the Polish group $Aut(M)$. For every countable structure $M$ we construct an $\aleph_0$-stable countable structure $N$ such that $Aut(M)$ and $Aut(N)$ are topologically isomorphic. This shows that it is impossible to detect any form of stability of a countable structure $M$ from the topological properties of the Polish group $Aut(M)$. △ Less

Submitted 19 November, 2018; v1 submitted 7 December, 2017; originally announced December 2017.

MSC Class: 03C45; 03E15; 22F50

The Class of Countable Projective Planes is Borel Complete

Authors: Gianluca Paolini

Abstract: We observe that Hall's free projective extension $P \mapsto F(P)$ of partial planes is a Borel map, and use a modification of the construction introduced in [9] to conclude that the class of countable non-Desarguesian projective planes is Borel complete. In the process, we also rediscover the main result of [7] on the realizability of every group as the group of collineations of some projective pl… ▽ More We observe that Hall's free projective extension $P \mapsto F(P)$ of partial planes is a Borel map, and use a modification of the construction introduced in [9] to conclude that the class of countable non-Desarguesian projective planes is Borel complete. In the process, we also rediscover the main result of [7] on the realizability of every group as the group of collineations of some projective plane. Finally, we use classical results of projective geometry to prove that the class of countable Pappian projective planes is Borel complete. △ Less

Submitted 14 November, 2018; v1 submitted 16 November, 2017; originally announced November 2017.

Comments: This paper has been merged with arXiv:1707.00294

MSC Class: 51A35; 03E15; 54H05; 05B35; 22F50

Polish Topologies for Graph Products of Groups

Authors: Gianluca Paolini, Saharon Shelah

Abstract: We give strong necessary conditions on the admissibility of a Polish group topology for an arbitrary graph product of groups $G(Γ, G_a)$, and use them to give a characterization modulo a finite set of nodes. As a corollary, we give a complete characterization in case all the factor groups $G_a$ are countable. We give strong necessary conditions on the admissibility of a Polish group topology for an arbitrary graph product of groups $G(Γ, G_a)$, and use them to give a characterization modulo a finite set of nodes. As a corollary, we give a complete characterization in case all the factor groups $G_a$ are countable. △ Less

Submitted 25 September, 2018; v1 submitted 16 November, 2017; originally announced November 2017.

MSC Class: 03E15; 20F65; 20B27

A New $ω$-Stable Plane

Authors: Gianluca Paolini

Abstract: We use a variation on Mason's $α$-function as a pre-dimension function to construct a not one-based $ω$-stable plane $P$ (i.e. a simple rank $3$ matroid) which does not admit an algebraic representation (in the sense of matroid theory) over any field. Furthermore, we characterize forking in $Th(P)$, we prove that algebraic closure and intrinsic closure coincide in $Th(P)$, and we show that… ▽ More We use a variation on Mason's $α$-function as a pre-dimension function to construct a not one-based $ω$-stable plane $P$ (i.e. a simple rank $3$ matroid) which does not admit an algebraic representation (in the sense of matroid theory) over any field. Furthermore, we characterize forking in $Th(P)$, we prove that algebraic closure and intrinsic closure coincide in $Th(P)$, and we show that $Th(P)$ fails weak elimination of imaginaries, and has Morley rank $ω$. △ Less

Submitted 10 January, 2020; v1 submitted 20 September, 2017; originally announced September 2017.

MSC Class: 03C45; 05B35

On the local homology of Artin groups of finite and affine type

Authors: Giovanni Paolini

Abstract: We study the local homology of Artin groups using weighted discrete Morse theory. In all finite and affine cases, we are able to construct Morse matchings of a special type (we call them "precise matchings"). The existence of precise matchings implies that the homology has a square-free torsion. This property was known for Artin groups of finite type, but not in general for Artin groups of affine… ▽ More We study the local homology of Artin groups using weighted discrete Morse theory. In all finite and affine cases, we are able to construct Morse matchings of a special type (we call them "precise matchings"). The existence of precise matchings implies that the homology has a square-free torsion. This property was known for Artin groups of finite type, but not in general for Artin groups of affine type. We also use the constructed matchings to compute the local homology in all exceptional cases, correcting some results in the literature. △ Less

Submitted 30 June, 2018; v1 submitted 5 September, 2017; originally announced September 2017.

Journal ref: Algebr. Geom. Topol. 19 (2019) 3615-3639

A Universal Homogeneous Simple Matroid of Rank $3$

Authors: Gianluca Paolini

Abstract: We construct a $\wedge$-homogeneous universal simple matroid of rank $3$, i.e. a countable simple rank~$3$ matroid $M_*$ which $\wedge$-embeds every finite simple rank $3$ matroid, and such that every isomorphism between finite $\wedge$-subgeometries of $M_*$ extends to an automorphism of $M_*$. We also construct a $\wedge$-homogeneous matroid $M_*(P)$ which is universal for the class of finite si… ▽ More We construct a $\wedge$-homogeneous universal simple matroid of rank $3$, i.e. a countable simple rank~$3$ matroid $M_*$ which $\wedge$-embeds every finite simple rank $3$ matroid, and such that every isomorphism between finite $\wedge$-subgeometries of $M_*$ extends to an automorphism of $M_*$. We also construct a $\wedge$-homogeneous matroid $M_*(P)$ which is universal for the class of finite simple rank $3$ matroids omitting a given finite projective plane $P$. We then prove that these structures are not $\aleph_0$-categorical, they have the independence property, they admit a stationary independence relation, and that their automorphism group embeds the symmetric group $Sym(ω)$. Finally, we use the free projective extension $F(M_*)$ of $M_*$ to conclude the existence of a countable projective plane embedding all the finite simple matroids of rank $3$ and whose automorphism group contains $Sym(ω)$, in fact we show that $Aut(F(M_*)) \cong Aut(M_*)$. △ Less

Submitted 3 October, 2018; v1 submitted 17 July, 2017; originally announced July 2017.

MSC Class: 03E15; 54H05; 05B35; 22F50

The Class of Non-Desarguesian Projective Planes is Borel Complete

Authors: Gianluca Paolini

Abstract: For every infinite graph $Γ$ we construct a non-Desarguesian projective plane $P^*_Γ$ of the same size as $Γ$ such that $Aut(Γ) \cong Aut(P^*_Γ)$ and $Γ_1 \cong Γ_2$ iff $P^*_{Γ_1} \cong P^*_{Γ_2}$. Furthermore, restricted to structures with domain $ω$, the map $Γ\mapsto P^*_Γ$ is Borel. On one side, this shows that the class of countable non-Desarguesian projective planes is Borel complete, and t… ▽ More For every infinite graph $Γ$ we construct a non-Desarguesian projective plane $P^*_Γ$ of the same size as $Γ$ such that $Aut(Γ) \cong Aut(P^*_Γ)$ and $Γ_1 \cong Γ_2$ iff $P^*_{Γ_1} \cong P^*_{Γ_2}$. Furthermore, restricted to structures with domain $ω$, the map $Γ\mapsto P^*_Γ$ is Borel. On one side, this shows that the class of countable non-Desarguesian projective planes is Borel complete, and thus not admitting a Ulm type system of invariants. On the other side, we rediscover the main result of [15] on the realizability of every group as the group of collineations of some projective plane. Finally, we use classical results of projective geometry to prove that the class of countable Pappian projective planes is Borel complete. △ Less

Submitted 13 September, 2018; v1 submitted 2 July, 2017; originally announced July 2017.

MSC Class: 51A35; 03E15; 54H05; 05B35; 22F50

Shellability of posets of labeled partitions and arrangements defined by root systems

Authors: Emanuele Delucchi, Noriane Girard, Giovanni Paolini

Abstract: We prove that the posets of connected components of intersections of toric and elliptic arrangements defined by root systems are EL-shellable and we compute their homotopy type. Our method rests on Bibby's description of such posets by means of "labeled partitions": after giving an EL-labeling and counting homology chains for general posets of labeled partitions, we obtain the stated results by co… ▽ More We prove that the posets of connected components of intersections of toric and elliptic arrangements defined by root systems are EL-shellable and we compute their homotopy type. Our method rests on Bibby's description of such posets by means of "labeled partitions": after giving an EL-labeling and counting homology chains for general posets of labeled partitions, we obtain the stated results by considering the appropriate subposets. △ Less

Submitted 20 June, 2017; originally announced June 2017.

Group Metrics for Graph Products of Cyclic Groups

Authors: Gianluca Paolini, Saharon Shelah

Abstract: We complement the characterization of the graph products of cyclic groups $G(Γ, \mathfrak{p})$ admitting a Polish group topology of [9] with the following result. Let $G = G(Γ, \mathfrak{p})$, then the following are equivalent: (i) there is a metric on $Γ$ which induces a separable topology in which $E_Γ$ is closed; (ii) $G(Γ, \mathfrak{p})$ is embeddable into a Polish group; (iii)… ▽ More We complement the characterization of the graph products of cyclic groups $G(Γ, \mathfrak{p})$ admitting a Polish group topology of [9] with the following result. Let $G = G(Γ, \mathfrak{p})$, then the following are equivalent: (i) there is a metric on $Γ$ which induces a separable topology in which $E_Γ$ is closed; (ii) $G(Γ, \mathfrak{p})$ is embeddable into a Polish group; (iii) $G(Γ, \mathfrak{p})$ is embeddable into a non-Archimedean Polish group. We also construct left-invariant separable group ultrametrics for $G = G(Γ, \mathfrak{p})$ and $Γ$ a closed graph on the Baire space, which is of independent interest. △ Less

Submitted 20 September, 2017; v1 submitted 7 May, 2017; originally announced May 2017.

MSC Class: 03E15; 20F65; 20B27

Polish Topologies for Graph Products of Cyclic Groups

Authors: Gianluca Paolini, Saharon Shelah

Abstract: We give a complete characterization of the graph products of cyclic groups admitting a Polish group topology, and show that they are all realizable as the group of automorphisms of a countable structure. In particular, we characterize the right-angled Coxeter groups (resp. Artin groups) admitting a Polish group topology. This generalizes results from [5], [7] and [4]. We give a complete characterization of the graph products of cyclic groups admitting a Polish group topology, and show that they are all realizable as the group of automorphisms of a countable structure. In particular, we characterize the right-angled Coxeter groups (resp. Artin groups) admitting a Polish group topology. This generalizes results from [5], [7] and [4]. △ Less

Submitted 8 January, 2018; v1 submitted 4 May, 2017; originally announced May 2017.

MSC Class: 03E15; 20F65; 20B27

The Automorphism Group of Hall's Universal Group

Authors: Gianluca Paolini, Saharon Shelah

Abstract: We study the automorphism group of Hall's universal locally finite group $H$. We show that in $Aut(H)$ every subgroup of index $< 2^ω$ lies between the pointwise and the setwise stabilizer of a unique finite subgroup $A$ of $H$, and use this to prove that $Aut(H)$ is complete. We further show that $Inn(H)$ is the largest locally finite normal subgroup of $Aut(H)$. Finally, we observe that from the… ▽ More We study the automorphism group of Hall's universal locally finite group $H$. We show that in $Aut(H)$ every subgroup of index $< 2^ω$ lies between the pointwise and the setwise stabilizer of a unique finite subgroup $A$ of $H$, and use this to prove that $Aut(H)$ is complete. We further show that $Inn(H)$ is the largest locally finite normal subgroup of $Aut(H)$. Finally, we observe that from the work of [Sh:312] it follows that for every countable locally finite $G$ there exists $G \cong G' \leq H$ such that every $f \in Aut(G')$ extends to an $\hat{f} \in Aut(H)$ in such a way that $f \mapsto \hat{f}$ embeds $Aut(G')$ into $Aut(H)$. In particular, we solve the three open questions of Hickin on $Aut(H)$ from [3], and give a partial answer to Question VI.5 of Kegel and Wehrfritz from [6]. △ Less

Submitted 22 May, 2017; v1 submitted 30 March, 2017; originally announced March 2017.

MSC Class: 20B27; 20F50

The Strong Small Index Property for Free Homogeneous Structures

Authors: Gianluca Paolini, Saharon Shelah

Abstract: We show that in algebraically locally finite countable homogeneous structures with a free stationary independence relation the small index property implies the strong small index property. We use this and the main result of [15] to deduce that countable free homogeneous structures in a locally finite relational language have the strong small index property. We also exhibit new continuum sized clas… ▽ More We show that in algebraically locally finite countable homogeneous structures with a free stationary independence relation the small index property implies the strong small index property. We use this and the main result of [15] to deduce that countable free homogeneous structures in a locally finite relational language have the strong small index property. We also exhibit new continuum sized classes of $\aleph_0$-categorical structures with the strong small index property whose automorphism groups are pairwise non-isomorphic. △ Less

Submitted 4 October, 2018; v1 submitted 30 March, 2017; originally announced March 2017.

MSC Class: 20B27; 03C15

Reconstructing Structures with the Strong Small Index Property up to Bi-Definability

Authors: Gianluca Paolini, Saharon Shelah

Abstract: Let $\mathbf{K}$ be the class of countable structures $M$ with the strong small index property and locally finite algebraicity, and $\mathbf{K}_*$ the class of $M \in \mathbf{K}$ such that $acl_M(\{ a \}) = \{ a \}$ for every $a \in M$. For homogeneous $M \in \mathbf{K}$, we introduce what we call the expanded group of automorphisms of $M$, and show that it is second-order definable in $Aut(M)$. W… ▽ More Let $\mathbf{K}$ be the class of countable structures $M$ with the strong small index property and locally finite algebraicity, and $\mathbf{K}_*$ the class of $M \in \mathbf{K}$ such that $acl_M(\{ a \}) = \{ a \}$ for every $a \in M$. For homogeneous $M \in \mathbf{K}$, we introduce what we call the expanded group of automorphisms of $M$, and show that it is second-order definable in $Aut(M)$. We use this to prove that for $M, N \in \mathbf{K}_*$, $Aut(M)$ and $Aut(N)$ are isomorphic as abstract groups if and only if $(Aut(M), M)$ and $(Aut(N), N)$ are isomorphic as permutation groups. In particular, we deduce that for $\aleph_0$-categorical structures the combination of strong small index property and no algebraicity implies reconstruction up to bi-definability, in analogy with Rubin's well-known $\forall \exists$-interpretation technique of [7]. Finally, we show that every finite group can be realized as the outer automorphism group of $Aut(M)$ for some countable $\aleph_0$-categorical homogeneous structure $M$ with the strong small index property and no algebraicity. △ Less

Submitted 30 August, 2018; v1 submitted 30 March, 2017; originally announced March 2017.

MSC Class: 20B27; 03C35; 03C15

Collapsibility to a subcomplex of a given dimension is NP-complete

Authors: Giovanni Paolini

Abstract: In this paper we extend the works of Tancer and of Malgouyres and Francés, showing that $(d,k)$-collapsibility is NP-complete for $d\geq k+2$ except $(2,0)$. By $(d,k)$-collapsibility we mean the following problem: determine whether a given $d$-dimensional simplicial complex can be collapsed to some $k$-dimensional subcomplex. The question of establishing the complexity status of $(d,k)$-collapsib… ▽ More In this paper we extend the works of Tancer and of Malgouyres and Francés, showing that $(d,k)$-collapsibility is NP-complete for $d\geq k+2$ except $(2,0)$. By $(d,k)$-collapsibility we mean the following problem: determine whether a given $d$-dimensional simplicial complex can be collapsed to some $k$-dimensional subcomplex. The question of establishing the complexity status of $(d,k)$-collapsibility was asked by Tancer, who proved NP-completeness of $(d,0)$ and $(d,1)$-collapsibility (for $d\geq 3$). Our extended result, together with the known polynomial-time algorithms for $(2,0)$ and $d=k+1$, answers the question completely. △ Less

Submitted 5 April, 2019; v1 submitted 20 March, 2017; originally announced March 2017.

Journal ref: Discrete & Computational Geometry 59 (1), pp. 246-251 (2018)

Weighted sheaves and homology of Artin groups

Authors: Giovanni Paolini, Mario Salvetti

Abstract: In this paper we expand the theory of weighted sheaves over posets, and use it to study the local homology of Artin groups. First, we use such theory to relate the homology of classical braid groups with the homology of certain independence complexes of graphs. Then, in the context of discrete Morse theory on weighted sheaves, we introduce a particular class of acyclic matchings. Explicit formulas… ▽ More In this paper we expand the theory of weighted sheaves over posets, and use it to study the local homology of Artin groups. First, we use such theory to relate the homology of classical braid groups with the homology of certain independence complexes of graphs. Then, in the context of discrete Morse theory on weighted sheaves, we introduce a particular class of acyclic matchings. Explicit formulas for the homology of the corresponding Morse complexes are given, in terms of the ranks of the associated incidence matrices. We use such method to perform explicit computations for the new affine case $\tilde C_n$, as well as for the cases $A_n$, $B_n$ and $\tilde{A}_n$ (which were already done before by different methods). △ Less

Submitted 6 December, 2020; v1 submitted 7 March, 2017; originally announced March 2017.

MSC Class: 05E45; 20F36; 52C35

Journal ref: Algebr. Geom. Topol. 18 (2018) 3943-4000

No Uncountable Polish Group Can be a Right-Angled Artin Group

Authors: Gianluca Paolini, Saharon Shelah

Abstract: We prove that no uncountable Polish group can admit a system of generators whose associated length function satisfies the following conditions: (i) if $0 < k < ω$, then $lg(x) \leq lg(x^k)$; (ii) if $lg(y) < k < ω$ and $x^k = y$, then $x = e$. In particular, the automorphism group of a countable structure cannot be an uncountable right-angled Artin group. This generalizes results from [3] and [5],… ▽ More We prove that no uncountable Polish group can admit a system of generators whose associated length function satisfies the following conditions: (i) if $0 < k < ω$, then $lg(x) \leq lg(x^k)$; (ii) if $lg(y) < k < ω$ and $x^k = y$, then $x = e$. In particular, the automorphism group of a countable structure cannot be an uncountable right-angled Artin group. This generalizes results from [3] and [5], where this is proved for free and free Abelian uncountable groups. △ Less

Submitted 2 April, 2017; v1 submitted 8 January, 2017; originally announced January 2017.

MSC Class: 20B27; 03E15; 03C60

Coxeter Groups and Abstract Elementary Classes: The Right-Angled Case

Authors: Tapani Hyttinen, Gianluca Paolini

Abstract: We study classes of right-angled Coxeter groups with respect to the strong submodel relation of parabolic subgroup. We show that the class of all right-angled Coxeter group is not smooth, and establish some general combinatorial criteria for such classes to be abstract elementary classes, for them to be finitary, and for them to be tame. We further prove two combinatorial conditions ensuring the s… ▽ More We study classes of right-angled Coxeter groups with respect to the strong submodel relation of parabolic subgroup. We show that the class of all right-angled Coxeter group is not smooth, and establish some general combinatorial criteria for such classes to be abstract elementary classes, for them to be finitary, and for them to be tame. We further prove two combinatorial conditions ensuring the strong rigidity of a right-angled Coxeter group of arbitrary rank. The combination of these results translate into a machinery to build concrete examples of $\mathrm{AECs}$ satisfying given model-theoretic properties. We exhibit the power of our method constructing three concrete examples of finitary classes. We show that the first and third class are non-homogeneous, and that the last two are tame, uncountably categorical and axiomatizable by a single $L_{ω_{1}, ω}$-sentence. We also observe that the isomorphism relation of any countable complete first-order theory is $κ$-Borel reducible (in the sense of generalized descriptive set theory) to the isomorphism relation of the theory of right-angled Coxeter groups whose Coxeter graph is an infinite random graph. △ Less

Submitted 16 April, 2018; v1 submitted 19 May, 2016; originally announced May 2016.

MSC Class: 03C48; 05E15

Journal ref: Notre Dame J. Formal Logic 60, no. 4 (2019), 707-731

A Finite Axiomatization of G-Dependence

Authors: Gianluca Paolini

Abstract: We show that a form of dependence known as G-dependence (originally introduced by Grelling) admits a very natural finite axiomatization, as well as Armstrong relations. We also give an explicit translation between functional dependence and G-dependence. We show that a form of dependence known as G-dependence (originally introduced by Grelling) admits a very natural finite axiomatization, as well as Armstrong relations. We also give an explicit translation between functional dependence and G-dependence. △ Less

Submitted 17 February, 2018; v1 submitted 15 December, 2015; originally announced December 2015.

MSC Class: 03B70; 03B99

Beyond Abstract Elementary Classes: On The Model Theory of Geometric Lattices

Authors: Tapani Hyttinen, Gianluca Paolini

Abstract: Based on Crapo's theory of one point extensions of combinatorial geometries, we find various classes of geometric lattices that behave very well from the point of view of stability theory. One of them, $(\mathbf{K}^3, \preccurlyeq)$, is $ω$-stable, it has a monster model and an independence calculus that satisfies all the usual properties of non-forking. On the other hand, these classes are rather… ▽ More Based on Crapo's theory of one point extensions of combinatorial geometries, we find various classes of geometric lattices that behave very well from the point of view of stability theory. One of them, $(\mathbf{K}^3, \preccurlyeq)$, is $ω$-stable, it has a monster model and an independence calculus that satisfies all the usual properties of non-forking. On the other hand, these classes are rather unusual, e.g. in $(\mathbf{K}^3, \preccurlyeq)$ the Smoothness Axiom fails, and so $(\mathbf{K}^3, \preccurlyeq)$ is not an $\mathrm{AEC}$. △ Less

Submitted 9 October, 2017; v1 submitted 4 December, 2015; originally announced December 2015.

MSC Class: 03C48; 03C45; 06B99; 05E99

On the classifying space of Artin monoids

Authors: Giovanni Paolini

Abstract: A theorem proved by Dobrinskaya in 2006 shows that there is a strong connection between the $K(π,1)$ conjecture for Artin groups and the classifying space of Artin monoids. More recently Ozornova obtained a different proof of Dobrinskaya's theorem based on the application of discrete Morse theory to the standard CW model of the classifying space of an Artin monoid. In Ozornova's work there are hin… ▽ More A theorem proved by Dobrinskaya in 2006 shows that there is a strong connection between the $K(π,1)$ conjecture for Artin groups and the classifying space of Artin monoids. More recently Ozornova obtained a different proof of Dobrinskaya's theorem based on the application of discrete Morse theory to the standard CW model of the classifying space of an Artin monoid. In Ozornova's work there are hints at some deeper connections between the above-mentioned CW model and the Salvetti complex, a CW complex which arises in the combinatorial study of Artin groups. In this work we show that such connections actually exist, and as a consequence we derive yet another proof of Dobrinskaya's theorem. △ Less

Submitted 10 May, 2018; v1 submitted 6 November, 2015; originally announced November 2015.

MSC Class: 20F36 (Primary) 55R35; 55U10; 52C35 (Secondary)

Journal ref: Communications in Algebra 45 (11), pp. 4740-4757 (2017)

A Logic for Arguing About Probabilities in Measure Teams

Authors: Tapani Hyttinen, Gianluca Paolini, Jouko Väänänen

Abstract: We use sets of assignments, a.k.a. teams, and measures on them to define probabilities of first-order formulas in given data. We then axiomatise first-order properties of such probabilities and prove a completeness theorem for our axiomatisation. We use the Hardy-Weinberg Principle of biology and the Bell's Inequalities of quantum physics as examples. We use sets of assignments, a.k.a. teams, and measures on them to define probabilities of first-order formulas in given data. We then axiomatise first-order properties of such probabilities and prove a completeness theorem for our axiomatisation. We use the Hardy-Weinberg Principle of biology and the Bell's Inequalities of quantum physics as examples. △ Less

Submitted 8 September, 2016; v1 submitted 6 September, 2015; originally announced September 2015.

MSC Class: 03B48

Quantum Team Logic and Bell's Inequalities

Authors: Tapani Hyttinen, Gianluca Paolini, Jouko Väänänen

Abstract: A logical approach to Bell's Inequalities of quantum mechanics has been introduced by Abramsky and Hardy [2]. We point out that the logical Bell's Inequalities of [2] are provable in the probability logic of Fagin, Halpern and Megiddo [4]. Since it is now considered empirically established that quantum mechanics violates Bell's Inequalities, we introduce a modified probability logic, that we call… ▽ More A logical approach to Bell's Inequalities of quantum mechanics has been introduced by Abramsky and Hardy [2]. We point out that the logical Bell's Inequalities of [2] are provable in the probability logic of Fagin, Halpern and Megiddo [4]. Since it is now considered empirically established that quantum mechanics violates Bell's Inequalities, we introduce a modified probability logic, that we call quantum team logic, in which Bell's Inequalities are not provable, and prove a Completeness Theorem for this logic. For this end we generalise the team semantics of dependence logic [7] first to probabilistic team semantics, and then to what we call quantum team semantics. △ Less

Submitted 9 March, 2016; v1 submitted 19 September, 2014; originally announced September 2014.

MSC Class: 03B48; 81P10

Journal ref: Review of Symbolic Logic 8 (2015) 722-742

Reduction of Database Independence to Dividing in Atomless Boolean Algebras

Authors: Tapani Hyttinen, Gianluca Paolini

Abstract: We prove that the form of conditional independence at play in database theory and independence logic is reducible to the first-order dividing calculus in the theory of atomless Boolean algebras. This establishes interesting connections between independence in database theory and stochastic independence. As indeed, in light of the aforementioned reduction and recent work of Ben-Yaacov [4], the form… ▽ More We prove that the form of conditional independence at play in database theory and independence logic is reducible to the first-order dividing calculus in the theory of atomless Boolean algebras. This establishes interesting connections between independence in database theory and stochastic independence. As indeed, in light of the aforementioned reduction and recent work of Ben-Yaacov [4], the former case of independence can be seen as the discrete version of the latter. △ Less

Submitted 7 December, 2017; v1 submitted 5 September, 2014; originally announced September 2014.

MSC Class: 03C45; 06E05; 68P15; 03C80

An algorithm for canonical forms of finite subsets of $\mathbb{Z}^d$ up to affinities

Authors: Giovanni Paolini

Abstract: In this paper we describe an algorithm for the computation of canonical forms of finite subsets of $\mathbb{Z}^d$, up to affinities over $\mathbb{Z}$. For fixed dimension $d$, this algorithm has worst-case asymptotic complexity $O(n \log^2 n \, s\,μ(s))$, where $n$ is the number of points in the given subset, $s$ is an upper bound to the size of the binary representation of any of the $n$ points,… ▽ More In this paper we describe an algorithm for the computation of canonical forms of finite subsets of $\mathbb{Z}^d$, up to affinities over $\mathbb{Z}$. For fixed dimension $d$, this algorithm has worst-case asymptotic complexity $O(n \log^2 n \, s\,μ(s))$, where $n$ is the number of points in the given subset, $s$ is an upper bound to the size of the binary representation of any of the $n$ points, and $μ(s)$ is an upper bound to the number of operations required to multiply two $s$-bit numbers. In particular, the problem is fixed-parameter tractable with respect to the dimension $d$. This problem arises e.g. in the context of computation of invariants of finitely presented groups with abelianized group isomorphic to $\mathbb{Z}^d$. In that context one needs to decide whether two Laurent polynomials in $d$ indeterminates, considered as elements of the group ring over the abelianized group, are equivalent with respect to a change of basis. △ Less

Submitted 27 September, 2018; v1 submitted 14 August, 2014; originally announced August 2014.

MSC Class: 52C07

Journal ref: Discrete & Computational Geometry 58 (2), pp. 293-312 (2017)