Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1999. / Includes bibliographical references (p. 109-112). / by Mats S. Nigam. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. / Includes bibliographical references (p. 201-219). / Our newly developing theory of bidimensional graph problems provides general techniques for designing efficient fixed-parameter algorithms and approximation algorithms for NP- hard graph problems in broad classes of graphs. This theory applies to graph problems that are bidimensional in the sense that (1) the solution value for the k x k grid graph (and similar graphs) grows with k, typically as Q(k²), and (2) the solution value goes down when contracting edges and optionally when deleting edges. Examples of such problems include feedback vertex set, vertex cover, minimum maximal matching, face cover, a series of vertex- removal parameters, dominating set, edge dominating set, r-dominating set, connected dominating set, connected edge dominating set, connected r-dominating set, and unweighted TSP tour (a walk in the graph visiting all vertices). Bidimensional problems have many structural properties; for example, any graph embeddable in a surface of bounded genus has treewidth bounded above by the square root of the problem's solution value. These properties lead to efficient-often subexponential-fixed-parameter algorithms, as well as polynomial-time approximation schemes, for many minor-closed graph classes. One type of minor-closed graph class of particular relevance has bounded local treewidth, in the sense that the treewidth of a graph is bounded above in terms of the diameter; indeed, we show that such a bound is always at most linear. The bidimensionality theory unifies and improves several previous results. / (cont.) The theory is based on algorithmic and combinatorial extensions to parts of the Robertson-Seymour Graph Minor Theory, in particular initiating a parallel theory of graph contractions. The foundation of this work is the topological theory of drawings of graphs on surfaces and our results regarding the relation (the linearity) of the size of the largest grid minor in terms of treewidth in bounded-genus graphs and more generally in graphs excluding a fixed graph H as a minor. In this thesis, we also develop the algorithmic theory of vertex separators, and its relation to the embeddings of certain metric spaces. Unlike in the edge case, we show that embeddings into L₁ (and even Euclidean embeddings) are insufficient, but that the additional structure provided by many embedding theorems does suffice for our purposes. We obtain an O[sq. root( log n)] approximation for min-ratio vertex cuts in general graphs, based on a new semidefinite relaxation of the problem, and a tight analysis of the integrality gap which is shown to be [theta][sq. root(log n)]. We also prove various approximate max-flow/min-vertex- cut theorems, which in particular give a constant-factor approximation for min-ratio vertex cuts in any excluded-minor family of graphs. Previously, this was known only for planar graphs, and for general excluded-minor families the best-known ratio was O(log n). These results have a number of applications. We exhibit an O[sq. root (log n)] pseudo-approximation for finding balanced vertex separators in general graphs. / (cont.) Furthermore, we obtain improved approximation ratios for treewidth: In any graph of treewidth k, we show how to find a tree decomposition of width at most O(k[sq. root(log k)]), whereas previous algorithms yielded O(k log k). For graphs excluding a fixed graph as a minor, we give a constant-factor approximation for the treewidth; this via the bidimensionality theory can be used to obtain the first polynomial-time approximation schemes for problems like minimum feedback vertex set and minimum connected dominating set in such graphs. / by MohammadTaghi Hajiaghayi. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2005. / Includes bibliographical references (p. 81-83). / In this thesis, we present bijections proving partitions identities. In the first part, we generalize Dyson's definition of rank to partitions with successive Durfee squares. We then present two symmetries for this new rank which we prove using bijections generalizing conjugation and Dyson's map. Using these two symmetries we derive a version of Schur's identity for partitions with successive Durfee squares and Andrews' generalization of the Rogers-Ramanujan identities. This gives a new combinatorial proof of the first Rogers-Ramanujan identity. We also relate this work to Garvan's generalization of rank. In the second part, we prove a family of four-parameter partition identities which generalize Andrews' product formula for the generating function for partitions with respect number of odd parts and number of odd parts of the conjugate. The parameters which we use are related to Stanley's work on the sign-balance of a partition. / by Cilanne Emily Boulet. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2006. / This electronic version was submitted by the student author. The certified thesis is available in the Institute Archives and Special Collections. / Includes bibliographical references (p. 253-257). / In this thesis, we study degenerate Monge-Ampere equations over projective manifolds. The main degeneration is on the cohomology class which is Kähler in classic cases. Our main results concern the case when this class is semi-ample and big with certain generalization to more general cases. Two kinds of arguments are applied to study this problem. One is maximum principle type of argument. The other one makes use of pluripotential theory. So this article mainly consists of three parts. In the first two parts, we apply these two kinds of arguments separately and get some results. In the last part, we try to combine the results and arguments to achieve better understanding about interesting geometric objects. Some interesting problems are also mentioned in the last part for future consideration. The generalization of classic pluripotential theory in the second part may be of some interest by itself. / by Zhou Zhang. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1995. / Includes bibliographical references (p. 67-69). / by Weiqiang Wang. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 115-118). / In this thesis, I construct and investigate the properties of a Floer theoretic invariant called relative symplectic cohomology. The construction is based on Hamiltonian Floer theory. It assigns a module over the Novikov ring to compact subsets of closed symplectic manifolds. I show the existence of restriction maps, and prove that they satisfy the Hamiltonian isotropy invariance property, discuss a Kunneth formula, and do some example computations. Relative symplectic cohomology is then used to establish a general criterion for displaceability of subsets. Finally, moving on to the main contribution of my thesis, I identify a natural geometric situation in which relative symplectic cohomology of two subsets satisfy the Mayer-Vietoris property. This is tailored to work under certain integrability assumptions, the weakest of which introduces a new geometric object called a barrier - roughly, a one parameter family of rank 2 co isotropic submanifolds. The proof uses a deformation argument in which the topological energy zero (i.e. constant) Floer solutions are the main actors. / by Umut Varolgunes. / Ph. D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2013. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 69-70). / We studies two examples of polytope slices, hypersimplices as slices of hypercubes and edge polytopes. For hypersimplices, the main result is a proof of a conjecture by R. Stanley which gives an interpretation of the Ehrhart h*-vector in terms of descents and excedances. Our proof is geometric using a careful book-keeping of a shelling of a unimodular triangulation. We generalize this result to other closely related polytopes. We next study slices of edge polytopes. Let G be a finite connected simple graph with d vertices and let PG C Rd be the edge polytope of G. We call PG decomposable if PG decomposes into integral polytopes PG+ and PG- via a hyperplane, and we give an algorithm which determines the decomposability of an edge polytope. Based on a sequence of papers by Ohsugi and Hibi, we prove that when PG is decomposable, PG is normal if and only if both PG+ and PG- are normal. We also study toric ideals of PG, PG+ and PG-. This part is joint work with Hibi and Zhang. / by Nan Li. / Ph.D.

Thesis (M.S.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1997. / Includes bibliographical references (leaves 22-23). / by Gustavo Granja. / M.S.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2006. / Includes bibliographical references (p. 89-91). / In this thesis, we study the Ehrhart polynomials of different polytopes. In the 1960's Eugene Ehrhart discovered that for any rational d-polytope P, the number of lattice points, i(P,m), in the mth dilated polytope mP is always a quasi-polynomial of degree d in m, whose period divides the least common multiple of the denominators of the coordinates of the vertices of P. In particular, if P is an integral polytope, i(P, m) is a polynomial. Thus, we call i(P, m) the Ehrhart (quasi-)polynomial of P. In the first part of my thesis, motivated by a conjecture given by De Loera, which gives a simple formula of the Ehrhart polynomial of an integral cyclic polytope, we define a more general family of polytopes, lattice-face polytopes, and show that these polytopes have the same simple form of Ehrhart polynomials. we also give a conjecture which connects our theorem to a well-known fact that the constant term of the Ehrhart polynomial of an integral polytope is 1. In the second part (joint work with Brian Osserman), we use Mochizuki's work in algebraic geometry to obtain identities for the number of lattice points in different polytopes. We also prove that Mochizuki's objects are counted by polynomials in the characteristic of the base field. / by Fu Liu. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1969. / Vita. / Bibliography: leaf 74. / by James D. Fabrey. / Ph.D.