Neighborly and almost neighborly configurations, and their duals

dc.contributor
Universitat Politècnica de Catalunya. Departament de Matemàtica Aplicada II
dc.contributor.author
Padrol Sureda, Arnau
dc.date.accessioned
2013-06-27T08:28:26Z
dc.date.available
2013-06-27T08:28:26Z
dc.date.issued
2013-03-12
dc.identifier.uri
http://hdl.handle.net/10803/117065
dc.description.abstract
This thesis presents new applications of Gale duality to the study of polytopes with extremal combinatorial properties. It consists in two parts. The first one is devoted to the construction of neighborly polytopes and oriented matroids. The second part concerns the degree of point configurations, a combinatorial invariant closely related to neighborliness. A d-dimensional polytope P is called neighborly if every subset of at most d/2 vertices of P forms a face. In 1982, Ido Shemer presented a technique to construct neighborly polytopes, which he named the "Sewing construction". With it he could prove that the number of neighborly polytopes in dimension d with n vertices grows superexponentially with n. One of the contributions of this thesis is the analysis of the sewing construction from the point of view of lexicographic extensions. This allows us to present a technique that we call the "Extended Sewing construction", that generalizes it in several aspects and simplifies its proof. We also present a second generalization that we call the "Gale Sewing construction". This construction exploits Gale duality an is based on lexicographic extensions of the duals of neighborly polytopes and oriented matroids. Thanks to this technique we obtain one of the main results of this thesis: a lower bound of ((r+d)^(((r+d)/2)^2)/(r^((r/2)^2)d^((d/2)^2)e^(3rd/4)) for the number of combinatorial types of neighborly polytopes of even dimension d and r+d+1 vertices. This result not only improves Shemer's bound, but it also improves the current best bounds for the number of polytopes. The combination of both new techniques also allows us to construct many non-realizable neighborly oriented matroids. The degree of a point configuration is the maximal codimension of its interior faces. In particular, a simplicial polytope is neighborly if and only if the degree of its set of vertices is [(d+1)/2]. For this reason, d-dimensional configurations of degree k are also known as "(d-k)-almost neighborly". The second part of the thesis presents various results on the combinatorial structure of point configurations whose degree is small compared to their dimension; specifically, those whose degree is smaller than [(d+1)/2], the degree of neighborly polytopes. The study of this problem comes motivated by Ehrhart theory, where a notion equivalent to the degree - for lattice polytopes - has been widely studied during the last years. In addition, the study of the degree is also related to the "generalized lower bound theorem" for simplicial polytopes, with Cayley polytopes and with Tverberg theory. Among other results, we present a complete combinatorial classification for point configurations of degree 1. Moreover, we show combinatorial restrictions in terms of the novel concept of "weak Cayley configuration" for configurations whose degree is smaller than a third of the dimension. We also introduce the notion of "codegree decomposition" and conjecture that any configuration whose degree is smaller than half the dimension admits a non-trivial codegree decomposition. For this conjecture, we show various motivations and we prove some particular cases.
eng
dc.format.extent
193 p.
dc.format.mimetype
application/pdf
dc.language.iso
eng
dc.publisher
Universitat Politècnica de Catalunya
dc.rights.license
L'accés als continguts d'aquesta tesi queda condicionat a l'acceptació de les condicions d'ús establertes per la següent llicència Creative Commons: http://creativecommons.org/licenses/by-nc-nd/3.0/es/
dc.rights.uri
http://creativecommons.org/licenses/by-nc-nd/3.0/es/
*
dc.source
TDX (Tesis Doctorals en Xarxa)
dc.title
Neighborly and almost neighborly configurations, and their duals
dc.type
info:eu-repo/semantics/doctoralThesis
dc.type
info:eu-repo/semantics/publishedVersion
dc.subject.udc
004
cat
dc.subject.udc
514
cat
dc.contributor.director
Pfeifle, Julian
dc.embargo.terms
cap
dc.rights.accessLevel
info:eu-repo/semantics/openAccess
dc.identifier.dl
B. 18241-2013


Documents

TAPS1de1.pdf

1.595Mb PDF

This item appears in the following Collection(s)