The Time-Dependent Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem, where the cost for travel between two nodes is dependent on the nodes and their position in the tour. Inequalities for the Asymmetric TSP can be easily extended to the TDTSP, but the added time information can be used to strengthen these inequalities. We look at extending the Lifted Cycle Inequalities, a large family of inequalities for the ATSP. We define a new inequality, the Extended Cycle (X-cycle) Inequality, based on cycles in the graph. We extend the results of Balas and Fischetti for Lifted Cycle Inequalities to define Lifted X-cycle Inequalities. We show that the Lifted X-cycle Inequalities include some inequalities which define facets of the submissive of the TDTS Polytope.

An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous fastest algorithm known has a worst case running time which is exponential in the length of the input. In this thesis we solve this problem in subexponential time under reasonable heuristics. We give two versions of our algorithm, a slower version assuming GRH and a faster version assuming stronger heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.

The central theme of this thesis is to prove results about infinite mathematical objects by studying the behaviour of their finite substructures. In particular, we study B-matroids, which are an infinite generalization of matroids introduced by Higgs \cite{higgs}, and graph-like spaces, which are topological spaces resembling graphs, introduced by Thomassen and Vella \cite{thomassenvella}. Recall that the circuit matroid of a finite graph is a matroid defined on the edges of the graph, with a set of edges being independent if it contains no circuit. It turns out that graph-like continua and infinite graphs both have circuit B-matroids. The first main result of this thesis is a generalization of Whitney's Theorem that a graph has an abstract dual if and only if it is planar. We show that an infinite graph has an abstract dual (which is a graph-like continuum) if and only if it is planar, and also that a graph-like continuum has an abstract dual (which is an infinite graph) if and only if it is planar. This generalizes theorems of Thomassen (\cite{thomassendual}) and Bruhn and Diestel (\cite{bruhndiestel}). The difficult part of the proof is extending Tutte's characterization of graphic matroids (\cite{tutte2}) to finitary or co-finitary B-matroids. In order to prove this characterization, we introduce a technique for obtaining these B-matroids as the limit of a sequence of finite minors. In \cite{tutte}, Tutte proved important theorems about the peripheral (induced and non-separating) circuits of a $3$-connected graph. He showed that for any two edges of a $3$-connected graph there is a peripheral circuit containing one but not the other, and that the peripheral circuits of a $3$-connected graph generate its cycle space. These theorems were generalized to $3$-connected binary matroids by Bixby and Cunningham (\cite{bixbycunningham}). We generalize both of these theorems to $3$-connected binary co-finitary B-matroids. Richter, Rooney and Thomassen \cite{richterrooneythomassen} showed that a locally connected, compact metric space has an embedding in the sphere unless it contains a subspace homeomorphic to $K_5$ or $K_{3,3}$, or one of a small number of other obstructions. We are able to extend this result to an arbitrary surface $\Sigma$; a locally connected, compact metric space embeds in $\Sigma$ unless it contains a subspace homeomorphic to a finite graph which does not embed in $\Sigma$, or one of a small number of other obstructions.

In this thesis we consider two classes of binary matroids, even cycle matroids and even cut matroids. They are a generalization of graphic and cographic matroids respectively. We focus on two main problems for these classes of matroids. We first consider the Isomorphism Problem, that is the relation between two representations of the same matroid. A representation of an even cycle matroid is a pair formed by a graph together with a special set of edges of the graph. Such a pair is called a signed graph. A representation for an even cut matroid is a pair formed by a graph together with a special set of vertices of the graph. Such a pair is called a graft. We show that two signed graphs representing the same even cycle matroid relate to two grafts representing the same even cut matroid. We then present two classes of signed graphs and we solve the Isomorphism Problem for these two classes. We conjecture that any two representations of the same even cycle matroid are either in one of these two classes, or are related by a local modification of a known operation, or form a sporadic example. The second problem we consider is finding the excluded minors for these classes of matroids. A difficulty when looking for excluded minors for these classes arises from the fact that in general the matroids may have an arbitrarily large number of representations. We define degenerate even cycle and even cut matroids. We show that a 3-connected even cycle matroid containing a 3-connected non-degenerate minor has, up to a simple equivalence relation, at most twice as many representations as the minor. We strengthen this result for a particular class of non-degenerate even cycle matroids. We also prove analogous results for even cut matroids.

The crossing number of a graph is the minimum number of pairwise crossings of edges among all planar drawings of the graph. A graph G is k-crossing critical if it has crossing number k and any proper subgraph of G has a crossing number less than k. The set of 1-crossing critical graphs is is determined by Kuratowski’s Theorem to be {K5, K3,3}. Work has been done to approach the problem of classifying all 2-crossing critical graphs. The graph V2n is a cycle on 2n vertices with n intersecting chords. The only remaining graphs to find in the classification of 2-crossing critical graphs are those that are 3-connected with a V8 minor but no V10 minor. This paper seeks to fill some of this gap by defining and completely describing a class of graphs called fully covered. In addition, we examine other ways in which graphs may be 2-crossing critical. This discussion classifies all known examples of 3-connected, 2-crossing critical graphs with a V8 minor but no V10 minor.

The capacitated facility location problem is a well known problem in combinatorial optimization and operations research. In it, we are given a set of clients and a set of possible facility locations. Each client has a certain demand that needs to be satisfied from open facilities, without exceeding their capacity. Whenever we open a facility we incur in a corresponding opening cost. Whenever demand is served, we incur in an assignment cost; depending on the distance the demand travels. The goal is to open a set of facilities that satisfy all demands while minimizing the total opening and assignment costs. In this thesis, we present two novel LP-based approximation algorithms for the capacitated facility location problem. The first algorithm is based on LP-rounding techniques, and is designed for the special case of the capacitated facility location problem where capacities are uniform and assignment costs are given by a tree metric. The second algorithm follows a primal-dual approach, and works for the general case. For both algorithms, we obtain an approximation guarantee that is linear on the size of the problem. To the best of our knowledge, there are no LP-based algorithms known, for the type of instances that we focus on, that achieve a better performance.

Cyclic sieving phenomenon (CSP) is a generalization by Reiner, Stanton, White of Stembridge's q=-1 phenomenon. When CSP is exhibited, orbits of a cyclic action on combinatorial objects show a nice structure and their sizes can be encoded by one polynomial. In this thesis we study various proofs of a very interesting cyclic sieving phenomenon, that jeu-de-taquin promotion on rectangular Young tableaux exhibits CSP. The first proof was obtained by Rhoades, who used Kazhdan-Lusztig representation. Purbhoo's proof uses Wronski map to equate tableaux with points in the fibre of the map. Finally, we consider Petersen, Pylyavskyy, Rhoades's proof on 2 and 3 row tableaux by bijecting the promotion of tableaux to rotation of webs. This thesis also propose a combinatorial approach to prove the CSP for square tableaux. A variation of jeu-de-taquin move yields a way to count square tableaux which has minimal orbit under promotion. These tableaux are then in bijection to permutations. We consider how this can be generalized.

The Time-Dependent Traveling Salesman Problem is a generalization of the well-known Traveling Salesman Problem, where the cost for travel between two nodes is dependent on the nodes and their position in the tour. Inequalities for the Asymmetric TSP can be easily extended to the TDTSP, but the added time information can be used to strengthen these inequalities. We look at extending the Lifted Cycle Inequalities, a large family of inequalities for the ATSP. We define a new inequality, the Extended Cycle (X-cycle) Inequality, based on cycles in the graph. We extend the results of Balas and Fischetti for Lifted Cycle Inequalities to define Lifted X-cycle Inequalities. We show that the Lifted X-cycle Inequalities include some inequalities which define facets of the submissive of the TDTS Polytope.

An isogeny between elliptic curves is an algebraic morphism which is a group homomorphism. Many applications in cryptography require evaluating large degree isogenies between elliptic curves efficiently. For ordinary curves of the same endomorphism ring, the previous fastest algorithm known has a worst case running time which is exponential in the length of the input. In this thesis we solve this problem in subexponential time under reasonable heuristics. We give two versions of our algorithm, a slower version assuming GRH and a faster version assuming stronger heuristics. Our approach is based on factoring the ideal corresponding to the kernel of the isogeny, modulo principal ideals, into a product of smaller prime ideals for which the isogenies can be computed directly. Combined with previous work of Bostan et al., our algorithm yields equations for large degree isogenies in quasi-optimal time given only the starting curve and the kernel.

The Lovasz theta function and the associated convex sets known as theta bodies are fundamental objects in combinatorial and semidefinite optimization. They are accompanied by a rich duality theory and deep connections to the geometric concept of orthonormal representations of graphs. In this thesis, we investigate several ramifications of the theory underlying these objects, including those arising from the illuminating viewpoint of duality. We study some optimization problems over unit-distance representations of graphs, which are intimately related to the Lovasz theta function and orthonormal representations. We also strengthen some known results about dual descriptions of theta bodies and their variants. Our main goal throughout the thesis is to lay some of the foundations for using semidefinite optimization and convex analysis in a way analogous to how polyhedral combinatorics has been using linear optimization to prove min-max theorems. A unit-distance representation of a graph $G$ maps its nodes to some Euclidean space so that adjacent nodes are sent to pairs of points at distance one. The hypersphere number of $G$, denoted by $t(G)$, is the (square of the) minimum radius of a hypersphere that contains a unit-distance representation of $G$. Lovasz proved a min-max relation describing $t(G)$ as a function of $\vartheta(\overline{G})$, the theta number of the complement of $G$. This relation provides a dictionary between unit-distance representations in hyperspheres and orthonormal representations, which we exploit in a number of ways: we develop a weighted generalization of $t(G)$, parallel to the weighted version of $\vartheta$; we prove that $t(G)$ is equal to the (square of the) minimum radius of an Euclidean ball that contains a unit-distance representation of $G$; we abstract some properties of $\vartheta$ that yield the famous Sandwich Theorem and use them to define another weighted generalization of $t(G)$, called ellipsoidal number of $G$, where the unit-distance representation of $G$ is required to be in an ellipsoid of a given shape with minimum volume. We determine an analytic formula for the ellipsoidal number of the complete graph on $n$ nodes whenever there exists a Hadamard matrix of order $n$. We then study several duality aspects of the description of the theta body $\operatorname{TH}(G)$. For a graph $G$, the convex corner $\operatorname{TH}(G)$ is known to be the projection of a certain convex set, denoted by $\widehat{\operatorname{TH}}(G)$, which lies in a much higher-dimensional matrix space. We prove that the vertices of $\widehat{\operatorname{TH}}(G)$ are precisely the symmetric tensors of incidence vectors of stable sets in $G$, thus broadly generalizing previous results about vertices of the elliptope due to Laurent and Poljak from 1995. Along the way, we also identify all the vertices of several variants of $\widehat{\operatorname{TH}}(G)$ and of the elliptope. Next we introduce an axiomatic framework for studying generalized theta bodies, based on the concept of diagonally scaling invariant cones, which allows us to prove in a unified way several characterizations of $\vartheta$ and the variants $\vartheta'$ and $\vartheta^+$, introduced independently by Schrijver, and by McEliece, Rodemich, and Rumsey in the late 1970's, and by Szegedy in 1994. The beautiful duality equation which states that the antiblocker of $\operatorname{TH}(G)$ is $\operatorname{TH}(\overline{G})$ is extended to this setting. The framework allows us to treat the stable set polytope and its classical polyhedral relaxations as generalized theta bodies, using the completely positive cone and its dual, and it allows us to derive a (weighted generalization of a) copositive formulation for the fractional chromatic number due to Dukanovic and Rendl in 2010 from a completely positive formulation for the stability number due to de Klerk and Pasechnik in 2002. Finally, we study a non-convex constraint for semidefinite programs (SDPs) that may be regarded as analogous to the usual integrality constraint for linear programs. When applied to certain classical SDPs, it specializes to the standard rank-one constraint. More importantly, the non-convex constraint also applies to the dual SDP, and for a certain SDP formulation of $\vartheta$, the modified dual yields precisely the clique covering number. This opens the way to study some exactness properties of SDP relaxations for combinatorial optimization problems akin to the corresponding classical notions from polyhedral combinatorics, as well as approximation algorithms based on SDP relaxations.