Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2004. / Includes bibliographical references (leaves 69-72). / The Greene-Kleitman theorem says that the lengths of chains and antichains in any poset are intimately related via an integer partition, but very little is known about the partition [lambda](P) for most posets P. Our first goal is to develop a method for calculating values of [lambda]k(P) for certain posets. We find the size of the largest union of two or three chains in the lattice of partitions of n under dominance order, and in the Tamari lattice. Similar techniques are then applied to the k-equal partition lattice. We also present some partial results and conjectures on chains and antichains in these lattices. We give an elementary proof of the rank-unimodality of L(2, n, m), and find a symmetric chain decomposition of L(2, 2, m). We also present some partial results and conjectures about related posets, including a theorem on the size of the largest union of k chains in these posets and a bijective proof of the symmetry of the H-vector for 2 x n. We answer a question of Knuth about the existence of a Gray path for binary partitions, and generalize to b-ary partitions when b is even. We also discuss structural properties of the posets Rb(n), and compute some chain and antichain lengths in the subposet of join-irreducibles. / by Edward Fielding Early. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1996. / Includes bibliographical references (leaves 52-55). / by Christopher Thomas Woodward. / Ph.D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2013. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 131-133). / The overall goal of this thesis is to apply the theory of Goodwillie calculus to the category Algo of algebras over a spectral operad. Its first part generalizes many of the original results of Goodwillie in [14] so that they apply to a larger class of model categories and hence be applicable to Algo. The second part then applies that generalized theory to the Algo categories. The main results here are: an understanding of finitary homogeneous between such categories; identifying the Taylor tower of the identity in those categories; showing that finitary n-excisive functors can not distinguish between Algo and Algo,, the category of algebras over the truncated operad O<; and a weak form of the chain rule between the algebra categories, analogous to the one found in [1]. / by Luis Alexandre Meira Fernandes Alves Pereira. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2015. / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 63-66). / Extremal functions of forbidden sequences and 0 - 1 matrices have applications to many problems in discrete geometry and enumerative combinatorics. We present a new computational method for deriving upper bounds on extremal functions of forbidden sequences. Then we use this method to prove tight bounds on the extremal functions of sequences of the form (12 ... 1)t for 1 >/= 2 and t >/= 1, abc(acb)t for t >/= 0, and avav'a, such that a is a letter, v is a nonempty sequence excluding a with no repeated letters and v' is obtained from v by only moving the first letter of v to another place in v. We also prove the existence of infinitely many forbidden 0 - 1 matrices P with non-linear extremal functions for which every strict submatrix of P has a linear extremal function. Then we show that for every d-dimensional permutation matrix P with k ones, the maximum number of ones in a d-dimensional matrix of sidelength n that avoids P is 20(k) nd-1 / by Jesse Geneson. / Ph. D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2018. / In title on title page, "[beta]" appears as the lower case Greek letter. Cataloged from PDF version of thesis. / Includes bibliographical references (pages 137-142). / In this thesis, we investigate the local and global properties of the eigenvalues of [beta]-ensembles. A lot of attention has been drawn recently on the universal properties of [beta]-ensembles, and how their local statistics relate to those of Gaussian ensembles. We use transport methods to prove universality of the eigenvalue gaps in the bulk and at the edge, in the single cut and multicut regimes. In a different direction, we also prove Central Limit Theorems for the linear statistics of [beta]-ensembles at the macroscopic and mesoscopic scales. / by Florent Bekerman. / Ph. D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 1989. / Includes bibliographical references (leaves 127-134). / by David A. Meyer. / Ph.D.

Thesis: Ph. D., Massachusetts Institute of Technology, Department of Mathematics, 2014. / 35 / Cataloged from PDF version of thesis. / Includes bibliographical references (pages 51-54). / A Heegaard splitting of a 3-manifold gives rise to a natural set of sweepouts which by the Almgren-Pitts and Simon-Smith min-max theory generates a min-max sequence converging as varifolds to a smooth minimal surface (possibly disconnected, and with multiplicities). We prove a conjecture of Pitts-Rubinstein about how such a min-max sequence can degenerate; namely we show that after doing finitely many disk surgeries and isotopies on the sequence, and discarding some components, the remaining components are each isotopic to one component (or a double cover of one component) of the min-max limit. This convergence immediately gives rise to new genus bounds for min-max limits. Our results can be thought of as a min-max analog to the theorem of Meeks-Simon-Yau on convergence of a minimizing sequence of surfaces in an isotopy class. / by Daniel Ketover. / Ph. D.

Thesis (Ph. D.)--Massachusetts Institute of Technology, Dept. of Mathematics, 2002. / Includes bibliographical references (p. 239-240). / Enumerative geometry of algebraic varieties is a fascinating field of mathematics that dates back to the nineteenth century. We introduce new computational tools into this field that are motivated by recent progress in symplectic topology and its influence on enumerative geometry. The most straightforward applications of the methods developed are to enumeration of rational curves with a cusp of specified nature in projective spaces. A general approach for counting positive-genus curves with a fixed complex structure is also presented. The applications described include enumeration of rational curves with a (3,4)-cusp, genus-two and genus-three curves with a fixed complex structure in the two-dimensional complex projective space, and genus-two curves with a fixed complex structure in the three-dimensional complex projective space. Our constructions may be applicable to problems in symplectic topology as well. / by Aleksey Zinger. / Ph.D.

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.