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(√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 Θ(√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(√log n) pseudo-approximation for finding balanced vertex separators in general graphs. 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 √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.

In the second part of the thesis, I give a combinatorial generalisation of the classical Boson-Fermion correspondence. I show how properties of many families of symmetric functions arise from representations of Heisenberg algebras. The main properties I consider are a tableaux-like definition, a Pieri-style rule and a Cauchy-style identity. Families of symmetric functions which can be viewed in this manner include Schur functions, Hall-Littlewood functions, Macdonald polynomials and the ribbon functions. Using work of Kashiwara, Miwa, Petersen and Yung, I define and study ribbon functions for certain affine root systems Φ of classical type and using also the work of Takemura and Uglov, I define higher level ribbon functions.

In this thesis, we also study cross-monotone cost sharings and group-strategyproof mechanisms. We study the limitations imposed by the cross-monotonicity property on cost-sharing schemes for several combinatorial optimization games including set cover and metric facility location. We develop a novel technique based on the probabilistic method for proving upper bounds on the budget-balance factor of cross-monotonic cost sharing schemes, deriving tight or nearly-tight bounds for these games. Finally, we design localized, distributed, and centralized approximation algorithms for power optimization in wireless networks. In particular, we design fault-tolerant topology control algorithms for power optimization in wireless multi-hop networks. Our main result in this part, is an O(log⁴ n)-approximation algorithm for the minimum power k-connected subgraph problem.

I gave an application of these estimates for k-dilation to a purely topological problem, about the possible degrees of continuous maps between certain 3-manifolds.

Finally, we analyze the small codimension classes on the space of maps to arbitrary flag varieties. We obtain an explicit description of the Picard groups. We formulate a conjecture about relations between the tautological generators, which we check in low codimension.

We prove that any two connected, reduced pseudoholomorphic curves in B, with the same number of irreducible components, the same number of nodal points and at most one ordinary cusp point, both sufficiently close to C₀, are symplectic isotopic to each other.

Next, by choosing a canonical metric on the submanifold, we construct an initial Kähler metric on the quasi-projective manifold such that the unique solution of the Monge-Ampère equation belongs to the weighted -1 Cheng-Yau Hölder ring. Moreover, we generalize the Fefferman's operator to act on the volume forms and obtain an iteration formula. Finally, with the aid of the isomorphism theorems and the iteration formula we derive the desired asymptotics from the initial metric. Furthermore, we prove that the obtained asymptotics is canonical in the sense that it is independent of the extensions of the canonical metric on the submanifold.

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.

In this thesis, we prove that all the spaces V_C are irreducible in the case where X is a del Pezzo surface of degree at least two. If the degree of X is one, then we prove the same result only for a general X, with the exception of V_-KX, where K_X is the canonical divisor of X. It is well known that for a general del Pezzo surface of degree one, V_-KX consists of twelve points, and thus cannot be irreducible.

In the first part of my thesis I study the totally nonnegative part of the Grassmannian and prove an enumeration theorem for a natural cell decomposition of it. This result leads to a new q-analog of the Eulerian numbers, which interpolates between the binomial coefficients, the Eulerian numbers, and the Narayana numbers. In the second part of my thesis I introduce the totally positive part of a tropical variety, and study this object in the case of the Grassmannian. I conjecture a tight relation between positive tropical varieties and the cluster algebras of Fomin and Zelevinsky, proving the conjecture in the case of the Grassmannian. The third and fourth parts of my thesis explore a notion of total positivity for oriented matroids. Namely, I introduce the positive Bergman complex of an oriented matroid, which is a matroidal analogue of a positive tropical variety. I prove that this object is homeomorphic to a ball, and relate it to the Las Vergnas face lattice of an oriented matroid. When the matroid is the matroid of a Coxeter arrangement, I relate the positive Bergman complex and the Bergman complex to the corresponding graph associahedron and the nested set complex. Finally, if time permits, I will talk about the poset of cells associated to the totally nonnegative part of an arbitrary real flag variety; the combinatorics of these posets provides compelling evidence that these spaces should be regular CW complexes homeomorphic to balls.

We show that, after a natural change of basis, classical random matrices are finite difference approximations to stochastic differential operators. As the size of a random matrix approaches infinity, it looks more and more like either the Airy operator [ A = (d²/dx²)-x ] or one of the Bessel operators [ J_a = -2√x(d/dx) + a/√x ] plus noise. The ``natural change of basis'' mentioned above was introduced by Dumitriu and Edelman and transforms the random matrix into tridiagonal or bidiagonal form.

In the second part we study the algebraic properties of the five-parameter family H(t₁,t₂,t₃,t₄;q) of double affine Hecke algebras of type C^∨ C₁, which control Askey-Wilson polynomials. We show that if q=1, then the spectrum of the center of H is an affine cubic surface C, obtained from a projective one by removing a triangle consisting of smooth points. Moreover, any such surface is obtained as the spectrum of the center of H for some values of parameters. We prove that the only flat deformations of H come from variations of parameters. This explains from the point of view of noncommutative geometry why one cannot add more parameters into the theory of Askey-Wilson polynomials. We also prove several results on the universality of the five-parameter family H(t₁,t₂,t₃,t₄;q) of algebras.

We study an important class of online decision problems called "multi-armed bandit problems." In the past such problems have found applications in areas as diverse as statistics, computer science, economic theory, and medical decision-making. Most existing algorithms were efficient only in the case of a small (i.e. polynomial-sized) strategy set. We extend the theory by supplying non-trivial algorithms and lower bounds for cases in which the strategy set is much larger (exponential or infinite) and the cost function class is structured, e.g. by constraining the cost functions to be linear or convex. As applications, we consider adaptive routing in networks, adaptive pricing in electronic markets, and collaborative decision-making by untrusting peers in a dynamic environment.