CEU Electronic Theses and Dissertations, 2012
| Author | Pongrácz, András |
|---|---|
| Title | Reducts of homogeneous relational structures |
| Summary | In this dissertation I summarize my work in counting numerical invariants of structures in model theory and general algebra. This involves the investigation of the generative spectra of monounary algebras and the free spectra of certain semigroups arising in automata theory. By counting the number of n-element monounary algebras in given varieties, we obtained an enumerative combinatorial result on the number of rooted trees of given depth. We determine, up to the equivalence of first-order interdefinability, all structures which are first-order definable in the random partial order. It turns out that these structures fall into precisely five equivalence classes. We achieve this result by showing that there exist exactly five closed permutation groups which contain the automorphism group of the random partial order, and thus expose all symmetries of this structure. The second major result is the characterization of the reducts of the structures obtained by adding a constant to the random K_n-free graph for any n>2, the so-called Henson graphs. Up to first-order interdefinability, there are 13 reducts if n = 3, and 16 reducts if n>3. In all these topics I have published, accepted or submitted papers in various mathematical journals. |
| Supervisor | Szabó, Csaba |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2012/pongracz_andras.pdf |
Visit the CEU Library.
© 2007-2021, Central European University