CEU Electronic Theses and Dissertations, 2015
| Author | Mészáros, Tamás |
|---|---|
| Title | Algebraic Phenomena in Combinatorics: Shattering-Extremal Families and the Combinatorial Nullstellensatz |
| Summary | This PhD dissertation is based on a research that originates from extremal combinatorics. In the first part we consider the problem of characterizing shattering-extremal set systems and extremal vector systems. We propose two different approaches, an algebraic and a graph theoretical one, and prove several characterizations of these extremal structures. The algebraic approach uses the standard monomials and Gröbner bases of vanishing ideals of finite point sets, while the key elements of the graph theoretical approach are the inclusion graphs of set systems. The second part of the dissertation is devoted to Noga Alon's famous Combinatorial Nullstellesatz and Non-vanishing Theorem. We prove generalizations of these results in different directions. First we introduce a version for multisets, then we consider the problem over arbitrary commutative rings instead of fields. At the end we investigate the problem of determining which finite sets X, beside discrete boxes, admit a version of the Combinatorial Nullstellensatz and the Non-vanishing Theorem. |
| Supervisor | Rónyai, Lajos |
| Department | Mathematics PhD |
| Full text | https://www.etd.ceu.edu/2015/meszaros_tamas.pdf |
Visit the CEU Library.
© 2007-2021, Central European University