Chamber kompleks üzeri̇ne bi̇r çalişma
A study on the chamber complex
Yazar: BÜŞRA SERT
Danışman: PROF. DR. SEFA FEZA ARSLAN
Mimar Sinan Güzel Sanatlar Üniversitesi / Fen Bilimleri Enstitüsü / Matematik Ana Bilim Dalı
Derece: Yüksek Lisans, 2019
Konu: Matematik = Mathematics

Özet:
Bu tezde, verilen bir A matrisi için matrisin satırlarının vermiş olduğu dış normal vektörlerin tanımladığı yarı düzlemleri oynatarak
elde edebileceğimiz chamberlerin bir koleksiyonu olan chamber kompleksi tanıtıp onu hesaplamak için McMullen, Beck, Sturmfels, Henk et. al., Emiris et. al. ve diğerleri tarafından 
yapılan önceki çalışmalardan esinlenerek elde ettiğimiz
bir algoritma sunmaktayız. Sunduğumuz algoritma rankı iki olan matrisler için hızlı çalışmak ile birlikte, rankı üç olan matrislerin chamber kompleksini hesaplamada çok yavaştır.

Ayrıca bu tezde, algoritmaya ek olarak, algoritmayı geliştirmek adına ve chamber kompleksin yapısını daha iyi anlayabilmek için torik varyete perspektifini kullanarak chamber kompleksin kendisinin ve chamberleri
ile eşleşen normal fanların torik varyetelerini inceleyerek, bir chamber kompleksdeki komşu chamberlerin torik varyetelerindeki değişimi gözlemleyerek elde ettiğimiz bazı teoremleri ve ispatını
sunmaktayız.

Bir politopun chamber'i ilk olarak McMullen'ın $1973$'de yayımladığı makalede, tanımlandı ve verilen bir politopun ayrıştırılabilir olup olmadığı sorusunu cevaplamak için kullanıldı.
İlerleyen yıllarda 
chamber'in kombinatorik ve integral programlama alanlarında uygulamaları yapıldı. Özellikle, verilen bir politopun latis noktalarının sayısını veren 
vektör ayırma fonksiyonu üzerindeki çalışmalarda chamber yapısı kullanılmaktadır. 

Verilen bir matris için o matrisin chamber kompleksini bulmak demek, verilen bir yarı düzlemler kümesinin elemanlarını kullanarak elde edebileceğimiz 
tüm kombinatorik sınıfları bulmak demektir öyle ki elde edilebilecek her kombinatorik sınıf için chamber komplekste o sınıfa iliştirilmiş bir chamber vardır. Burada kombinatorik 
sınıf ile, eşitlik sisteminin çözüm kümesi olarak elde edebileceğimiz politopların kombinatorik
sınıfı kastedilmektedir.
Eğer matrisin chamber kompleksinde sadece bir tane en büyük boyutlu chamber bulunuyorsa, önceki çalışmaların verdiği algoritmalar kullanılarak chamber kompleks elde edilebilir. 
Ancak çalışmalarımız sırasında, üç boyutta, chamber komplekste birden fazla en büyük boyutlu chamberin bulunabileceğini gözlemlemiş bulunmaktayız.
Bu tezde, chamber kompleksi
bulmadan önce komplekste kaç tane en büyük boyutlu chamberin bulunabileceği sorusunu cevaplayabilmek için chamber kompleksin chamberlerine iliştirilen normal fanların torik 
varyetelerini ve chamber kompleksi bir fan olarak görüp onun torik varyetesini incelemekte ve gözlemlerimizi sunmaktayız.

Abstract:
In this thesis, we define the chamber complex of a given matrix A that is the collection of the chambers we could obtain by moving the halfspaces whose outer normal vectors 
are given by the rows of A. Moreover we present an algorithm inspired by the previous works of McMullen, Sturmfels, Henk et. al., Emiris et. al., Beck and the others on the chamber 
of a polytope and the vector partition function. The algorithm works fast for the matrices that have rank two, but it is too slow for the matrices of rank three. In order to have a fist step
that could help for the future work on improving the algorithm, we consider the chamber complex and its chambers with toric variety aspect, and for a given chamber complex, we examine
the toric variety of the normal fan associated to each chamber and also the toric variety of the chamber complex. In this thesis we present the observations we obtain during our studies via 
theorems we have.
A polytope P could be expressed as the intersection of halfspaces whose outer normal vectors are given by a matrix A and their positions are given by a vector b.
The chamber (or type cone, or Minkowski cone) of a given polytope P was first defined by McMullen in the paper he published in 1973 presenting a way to 
answer the question 
asking, for a given d-dimensional polytope P, whether there exist two polytopes R,S (called summands), that are not obtained by dilating or 
shrinking or translating P, and whose Minkowski sum R+S gives P. If such polytopes exist, then P is called decomposable, if not, P is called 
indecomposable. The chamber of the polytope is the cone of all vectors for which polytopes we obtain by the intersection of halfspaces that are located by the vectors are strongly 
combinatorially equivalent to P, i.e.,  they have the same normal fan (collection of the cones generated by the normal vectors of the faces). 
McMullen stated that a polytope P is indecomposable if and only if the chamber of P is one dimensional. Moreover, the generating rays of the chamber
give information about the indecomposable summands of P, i.e., for a point d, taken from one of the generating rays of the chamber of P,  the polytope given by
the  same half spaces as P, but with different positioning given by the point d, is an indecomposable summand of $P$. Since then, Emiris et. al., Henk et. al., Brion et. al.,
Beck and others worked on the chamber and its applications to integer programming and combinatorics. Sturmfels in 1994 proved 
that for each chamber, there exists a vector partition function that gives the number of lattice points of the polytope P whose halfspaces are located by any point c taken
from the chamber of P. The vector partition function became a very useful tool in Ehrhart theory as the vector partition function of a chamber is indeed an 
Ehrhart polynomial. 


A given matrix A of rank d corresponds to the set of outer normal vectors of the defining half spaces.
 changing the vector b that changes the positions of the halfspaces given by A with another 
vector c corresponds to moving the halfspaces along the directions given by A. Each such replacement gives another polytope that may have
different combinatorial type, i.e., they have different relations between their faces. Being given a polytope indeed corresponds to
having a fixed matrix A and a right hand side vector b that fixes the polytope P, i.e., the combinatorial type. 
The chamber of P is the cone of those vectors b, such that the movement of hyperplanes preserves the combinatorial type. 

The chamber complex of a given matrix A is the collection of all chambers we could obtain by moving the halfspaces whose outer normal vectors are defined by A. When 
the chamber complex of a given matrix A has only one top-dimensional cone, the chamber complex of A coincides with the closure of the chamber of the polytope P whose chamber
is the top-dimensional cone in the chamber complex. However, we observed that for some matrices A, there can be more than one top-dimensional chambers 
in the chamber complex of A (We present an example of this case in the thesis). 
 There are some cases for which the algorithm we present is too slow, although the algorithm from previous works would be fast for some of them.
We also know that the algorithm from previous works is not enough to get the chamber complex when it has more than one top dimensional chambers as
we cannot realize the chamber complex as the closure of the chamber of a polytope.

In order to understand the structure of the chamber complex, we follow the following algebraic geometric aspect.

 One of the classical objects of algebraic geometry is toric varieties. We mentioned above that for each chamber in the chamber complex,
there is one associated combinatorial type. Moreover, we have that for each chamber $C$, there is one associated normal fan such that all polytopes
P defined by b taken from the chamber, have the same normal fan. Let us consider the toric varieties of the normal fans associated to the chambers.
When we move in the chamber complex from one chamber to another, the toric varieties of the associated normal fans change and when two chambers have a 
common face, the toric varieties have a common sub-variety. In the chapter on the chamber complex and toric varieties,  we focus on the change on of the toric varieties
associated to the chambers of a given chamber complex and provide theorems on our observations on the change.



As each chamber itself is a strictly convex rational polyhedral cone, we can also consider the toric variety of the chamber complex. Moreover, every toric variety $X_{\Sigma}$ 
has a natural torus action on it, and the number of fixed points is the number of top dimensional cones of a given fan .
this yields us to have the observation that the number of top dimensional chambers of the chamber complex of a given matrix A is the number 
of the fixed points of the torus action on the toric variety of the chamber complex of A.