http://smartech.gatech.edu/handle/1853/6020 Original work by students in the School of Mathematics Search the Channel search http://smartech.gatech.edu/simple-search http://smartech.gatech.edu/handle/1853/22659 Title: Enumerative Combinatorics of Posets <br/> <br/>Authors: Carroll, Christina Conklin <br/> <br/>Abstract: This thesis contains several results concerning the combinatorics of partially ordered sets (posets) which are either of enumerative or extremal nature. <br><br> The first concerns conjectures of Friedland and Kahn, which state that the (extremal) d-regular graph on N vertices containing both the maximal number of matchings and independent sets of a fixed size is the graph consisting of disjoint union of appropriate number of complete bipartite d-regular graphs on 2d vertices. We show that the conjectures are true in an asymptotic sense, using entropy techniques. <br><br> As a second result, we give tight bounds on the size of the largest Boolean family which contains no three distinct subsets forming an "induced V" (i.e. if A,B,C are all in our family, if C is contained in the intersection of A B, A must be a subset of B). This result, though similar to known results, gives the first bound on a family defined by an induced property. <br><br> We pose both Dedekind-type questions concerning the number of antichains and a Stanley-type question concerning the number of linear extensions in generalized Boolean lattices; namely, products of chain posets and the poset of partially defined functions. We provide asymptotically tight bounds for these problems. <br><br> A Boolean function, f, is called cherry-free if for all triples x,y,z where z covers both x and y, f(z)=1 whenever both f(x)=1 and f(y)=1. We give bounds on the number of cherry-free functions on bipartite regular posets, with stronger results for bipartite posets under an additional co-degree hypotheses. We discuss applications of these functions to Boolean Horn functions and similar structures in ranked regular posets. http://smartech.gatech.edu/handle/1853/22583 Title: Tree-based decompositions of graphs on surfaces and applications to the Traveling Salesman Problem <br/> <br/>Authors: Inkmann, Torsten <br/> <br/>Abstract: The tree-width and branch-width of a graph are two well-studied examples of parameters that measure how well a given graph can be decomposed into a tree structure. In this thesis we give several results and applications concerning these concepts, in particular if the graph is embedded on a surface. In the first part of this thesis we develop a geometric description of tangles in graphs embedded on a fixed surface (tangles are the obstructions for low branch-width), generalizing a result of Robertson and Seymour. We use this result to establish a relationship between the branch-width of an embedded graph and the carving-width of an associated graph, generalizing a result for the plane of Seymour and Thomas. We also discuss how these results relate to the polynomial-time algorithm to determine the branch-width of planar graphs of Seymour and Thomas, and explain why their method does not generalize to surfaces other than the sphere. We also prove a result concerning the class C_2k of minor-minimal graphs of branch-width 2k in the plane, for an integer k at least 2. We show that applying a certain construction to a class of graphs in the projective plane yields a subclass of C_2k, but also show that not all members of C_2k arise in this way if k is at least 3. The last part of the thesis is concerned with applications of graphs of bounded tree-width to the Traveling Salesman Problem (TSP). We first show how one can solve the separation problem for comb inequalities (with an arbitrary number of teeth) in linear time if the tree-width is bounded. In the second part, we modify an algorithm of Letchford et al. using tree-decompositions to obtain a practical method for separating a different class of TSP inequalities, called simple DP constraints, and study their effectiveness for solving TSP instances. http://smartech.gatech.edu/handle/1853/19869 Title: An extension of KAM theory to quasi-periodic breather solutions in Hamiltonian lattice systems <br/> <br/>Authors: Viveros Rogel, Jorge <br/> <br/>Abstract: We prove the existence and linear stability of quasi-periodic breather solutions in a 1d Hamiltonian lattice of identical, weakly-coupled, anharmonic oscillators with general on-site potentials and under the effect of long-ranged interaction, via de KAM technique. We prove the persistence of finite-dimensional tori which correspond in the uncoupled limit to N arbitrary lattice sites initially excited. The frequencies of the invariant tori of the perturbed system are only slightly deformed from the frequencies of the unperturbed tori. http://smartech.gatech.edu/handle/1853/19861 Title: Validated Continuation for Infinite Dimensional Problems <br/> <br/>Authors: Lessard, Jean-Philippe <br/> <br/>Abstract: Studying the zeros of a parameter dependent operator F defined on a Hilbert space H is a fundamental problem in mathematics. When the Hilbert space is finite dimensional, continuation provides, via predictor-corrector algorithms, efficient techniques to numerically follow the zeros of F as we move the parameter. In the case of infinite dimensional Hilbert spaces, this procedure must be applied to some finite dimensional approximation which of course raises the question of validity of the output. We introduce a new technique that combines the information obtained from the predictor-corrector steps with ideas from rigorous computations and verifies that the numerically produced zero for the finite dimensional system can be used to explicitly define a set which contains a unique zero for the infinite dimensional problem F: HxR->Im(F). We use this new validated continuation to study equilibrium solutions of partial differential equations, to prove the existence of chaos in ordinary differential equations and to follow branches of periodic solutions of delay differential equations. In the context of partial differential equations, we show that the cost of validated continuation is less than twice the cost of the standard continuation method alone.