First, we study extremal questions in geometric graph theory. We investigate the existence of collections of edges with a specified crossing pattern in drawings of graphs in the plane with sufficiently many edges. Among other results, we prove that any drawing of a graph on n vertices and Cn edges, where C is a sufficiently large constant, contains each of the following crossing patterns: (1) three pairwise crossing edges, (2) two edges that cross and are crossed by k other edges, (3) an edge crossed by four other edges. In the latter, we show that C = 5.5 is the best possible constant, which, through Székely's method, gives the best known value for a constant in the well known "Crossing Lemma" due to Ajtai, Chvátal, Leighton, Newborn and Szemerédi. After relaxing graph planarity in several ways, we proceed to study ex_cr (n, C₄), the maximum number of edges in a drawing of a graph on n vertices without self-crossing copy of C₄. We prove that ex_cr(n, C₄) = O(n^8/5). The importance of this and the above mentioned results comes from numerous applications of "Crossing Lemma" and the bounds on ex_cr (n, C₄) in discrete and computational geometry (incidence and Gallai-Sylvester type problems, k-set problems, the distinct distances and the unit distance problems of Erdös, problems on arrangements of circles and pseudo-parabolas, questions on parametric and kinetic minimum spanning trees), number theory, and the VLSI design.

       Next, we initiate a new trend in Ramsey theory, which can be categorized as the rainbow Ramsey theory. Drawing a parallel with Motzkin's statement that "complete disorder is impossible", we prove the existence of rainbow/hetero-chromatic structures in a colored universe, under certain density conditions on the coloring. For example, we prove that every 3-coloring of the set of positive integers, such that each color class has the upper density >1/6, contains a rainbow 3-term arithmetic progression; this statement being a clear rainbow analogue of van der Waerden's theorem. We also consider rainbow counterparts of other classical theorems in Ramsey theory, such as Rado's and Hales-Jewett theorem. Additionally, we refute one geometric strengthening of van der Waerden's theorem, answering an open problem of Pach.

       We continue with improvements and contributions to two classical problems in Euclidean Ramsey theory: (1) Hadwiger-Nelson problem on the chromatic number of ^d and (2) the empty convex hexagon question of Erdös.

       We then turn to some Ramsey-type geometric questions and prove that there exists a positive constant such that every family of n semi-algebraic sets in ^d has two subfamilies ₁, ₂ with at least n members such that every member of ₁ intersects all members of ₂ or no member of ₁ intersects any member of ₂. This result generalizes and extends previous work of Pach and Solymosi, and solves some open problems of Erdös, Hajnal and Pach. We combine our novel approach with Szemerédi's regularity lemma to solve a longstanding open problem of Erdös on the least diameter of an n-point separated set in ³ with many nearly equal distances.

       We also provide improvements for several problems on arrangements of lines in the plane, as well as make some contributions towards resolving a well known conjecture of Lovász in graph theory.

       As an easy consequence of this work, one obtains simple proofs of the fact the Kostka numbers K_{N N} and Littlewood-Richardson numbers c_{N N}^N are given by polynomial functions in the nonnegative integer variable N. Both these results were known previously but have non-elementary proofs involving fermionic formulas for Kostka-Foulkes polynomials and semi-invariants of quivers.

       Also investigated is a new q-analogue of the Kostant partition function, a specialization of which was used by Victor Guillemin, Shlomo Sternberg and Jonathan Weitsman to give a formula for the twisted signatures of coadjoint orbits. This q-analogue is shown to be given by polynomial functions over the relative interiors of the cells of a complex of cones. For type A, the twisted signature is also given by a specialization of the Hall-Littlewood symmetric polynomials.

       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 × n.

       For the nondegenerate case, the kernel associated with the Witten Laplacian has an expression via the Malliavin calculus. The first step is the analysis of this heat kernel at a point away the critical set. Using Markov property, an iteration procedure and estimates on exit times from balls, everything is reduced to the estimation of a solution to a parabolic initial-boundary problem on a ball in the Euclidean space which is handled by an explicit construction of a supersolution. For the closed to the critical set case, based on the same line of ideas one can reduce the computation to a harmonic oscilator problem.

       The case of the degenerate Bott-Morse function requires a bit more work due to the fact that the geometry near the critical submanifolds is in general not trivial. After some standard constructions, we have two choices of the connection around critical submanifolds. One is the Levi-Civita and the other is the Bismut's connection. The main step in this analysis is to prove that the heat kernels of certain operators with respect to Levi-Civita connection and the Bismut connection stay bounded when the parameters involved become large. This is achieved by a fiberwise version of the argument given in the nondegenerate case. Using the boundedness, one can prove the basic comparison between the heat kernels of various operators. Finally one can reduce the problem to a fiberwise harmonic oscilator.

       Our first result is that the joint distribution of the pair of statistics `number of fixed points' and `number of excedances' is the same in 321-avoiding as in 132-avoiding permutations. This generalizes a recent result of Robertson, Saracino and Zeilberger, for which we also give another, more direct proof. The key ideas are to introduce a new class of statistics on Dyck paths, based on what we call a tunnel, and to use a new technique involving diagonals of non-rational generating functions.

       Next we present a new statistic-preserving family of bijections from the set of Dyck paths to itself. They map statistics that appear in the study of pattern-avoiding permutations into classical statistics on Dyck paths, whose distribution is easy to obtain. In particular, this gives a simple bijective proof of the equidistribution of fixed points in the above two sets of restricted permutations.

       Then we introduce a bijection between 321- and 132-avoiding permutations that preserves the number of fixed points and the number of excedances. A part of our bijection is based on the Robinson-Schensted-Knuth correspondence. We also show that our bijection preserves additional parameters.

       Next, motivated by these results, we study the distribution of fixed points and excedances in permutations avoiding subsets of patterns of length 3. We solve all the cases of simultaneous avoidance of more than one pattern, giving generating functions which enumerate them. Some cases are generalized to patterns of arbitrary length. For avoidance of one single pattern we give partial results. We also describe the distribution of these statistics in involutions avoiding any subset of patterns of length 3. The main technique consists in using bijections between pattern-avoiding permutations and certain kinds of Dyck paths, in such a way that the statistics in permutations that we consider correspond to statistics on Dyck paths which are easier to enumerate.

       Finally, we study another kind of restricted permutations, counted by the Motzkin numbers. By constructing a bijection into Motzkin paths, we enumerate them with respect to some parameters, including the length of the longest increasing and decreasing subsequences and the number of ascents.

       The goal of this thesis is to develop new and better techniques for approximating facility location problems and studying them in a game-theoretic setting. In our main result, we introduce a novel technique and apply it to the uncapacitated facility location problem, achieving the best known approximation factor for this problem. We demonstrate the general applicability of this technique by applying it to several unrelated problems. Finally, we consider the facility location problem in a game-theoretic setting and prove tight bounds on schemes for dividing up the cost of a solution among players. More specifically,

• We design several approximation algorithms for the uncapacitated facility location problem, one of which achieves an approximation factor of 1.52 in quasi-linear time. This is the best known approximation factor for this problem, and is very close to the hardness lower bound for the problem. To design and analyze the approximation factor of our algorithms, we introduce a variation of the primal-dual method, which we call dual fitting, in combination with a factor-revealing LP.
• We apply our algorithms on several variants of the problem, including k-facility location (a common generalization of k-median and facility location), uniform fault-tolerant facility location, facility location with penalties, and robust facility location, improving the best previously-known approximation algorithms for these problems. We show how our algorithms combined with the notion of bifactor approximate reductions can lead to a 2-approximation algorithm for the soft-capacitated facility location problem, achieving the integrality gap of the natural LP relaxation of the problem. We also define a problem called universal facility location, which generalizes several variants of the facility location problem, and give the first constant-factor approximation algorithm for this problem using local search. Finally, we apply the standard primal-dual scheme to two other variants of the facility location problem, namely priority facility location and stochastic facility location, to obtain improved approximation factors.
• We show the versatility of our techniques by applying them to the analysis of other algorithms. In particular, we analyze the approximation factor of algorithms for the cycle cover problem with short cycles (a.k.a. the lane covering problem) and the Steiner packing problem (a.k.a. the maximum capacity multicast problem), and the competitive ratio of an online buffer management algorithm using factor-revealing LPs.
• We consider the facility location problem in a game-theoretic setting, and prove lower bounds on schemes for dividing up the cost of a solution among the clients. Our result combined with the scheme recently proposed by Pal and Tardos shows that 1/3 is the best possible approximation factor for any facility location cost-sharing algorithm satisfying the cross-monotonicity property. Our proof is based on a novel technique that we develop and apply on several other optimization problems such as vertex cover, set cover, matching, and maximum flows to derive tight lower bounds.

       Given a set of tiles T and a finite set L of local replacement moves, we say that a region Γ has local connectivity with respect to T and L if it is possible to convert any tiling of Γ into any other by means of these moves. If R is a set of regions (such as the set of all simply connected regions), then we say there is a local move property for T and R if there exists a finite set of moves L such that every Γ in R has local connectivity with respect to T and L. We use height function techniques to prove local move properties for several new tile sets. In addition, we provide explicit counterexamples to show the absence of a local move property for a number of tile sets where local move properties were conjectured to hold.

       We also provide several new results concerning tile invariants. If we let a_i(τ) denote the number of occurrences of the tile t_i in a tiling τ of a region Γ, then a tile invariant is a linear combination of the a_i's whose value depends only on Γ and not on τ. We modify the boundary-word technique of Conway and Lagarias to prove tile invariants for several new sets of tiles and provide specific examples to show that the invariants we obtain are the best possible.

       In addition, we prove some new enumerative results, relating certain tiling problems to Baxter permutations, the Tutte polynomial, and alternating-sign matrices.

Classifying the irreducible unitary representations of a real reductive group is equivalent to the algebraic problem of classifying the Harish-Chandra modules admitting a positive definite invariant Hermitian form. Finding a formula for the signature of the Shapovalov form is a related problem that may be a necessary first step in such a classification.