This thesis explores two infinite families of self-complementary arc-transitive graphs: the familiar Paley graphs and the newly discovered Peisert graphs. After studying both families, we examine a result of Peisert which proves the Paley and Peisert graphs are the only self-complementary arc transitive graphs other than one exceptional graph. Then we consider other families of graphs which share many properties with the Paley and Peisert graphs. In particular, we construct an infinite family of self-complementary strongly regular graphs from affine planes. We also investigate the pseudo-Paley graphs of Weng, Qiu, Wang, and Xiang. Finally, we prove a lower bound on the number of maximal cliques of certain pseudo-Paley graphs, thereby distinguishing them from Paley graphs of the same order.

We study techniques, approximation algorithms, structural properties and lower bounds related to applications of linear programs in combinatorial optimization. The following "Steiner tree problem" is central: given a graph with a distinguished subset of required vertices, and costs for each edge, find a minimum-cost subgraph that connects the required vertices. We also investigate the areas of network design, multicommodity flows, and packing/covering integer programs. All of these problems are NP-complete so it is natural to seek approximation algorithms with the best provable approximation ratio. Overall, we show some new techniques that enhance the already-substantial corpus of LP-based approximation methods, and we also look for limitations of these techniques. The first half of the thesis deals with linear programming relaxations for the Steiner tree problem. The crux of our work deals with hypergraphic relaxations obtained via the well-known full component decomposition of Steiner trees; explicitly, in this view the fundamental building blocks are not edges, but hyperedges containing two or more required vertices. We introduce a new hypergraphic LP based on partitions. We show the new LP has the same value as several previously-studied hypergraphic ones; when no Steiner nodes are adjacent, we show that the value of the well-known bidirected cut relaxation is also the same. A new partition uncrossing technique is used to demonstrate these equivalences, and to show that extreme points of the new LP are well-structured. We improve the best known integrality gap on these LPs in some special cases. We show that several approximation algorithms from the literature on Steiner trees can be re-interpreted through linear programs, in particular our hypergraphic relaxation yields a new view of the Robins-Zelikovsky 1.55-approximation algorithm for the Steiner tree problem. The second half of the thesis deals with a variety of fundamental problems in combinatorial optimization. We show how to apply the iterated LP relaxation framework to the problem of multicommodity integral flow in a tree, to get an approximation ratio that is asymptotically optimal in terms of the minimum capacity. Iterated relaxation gives an infeasible solution, so we need to finesse it back to feasibility without losing too much value. Iterated LP relaxation similarly gives an O(k^2)-approximation algorithm for packing integer programs with at most k occurrences of each variable; new LP rounding techniques give a k-approximation algorithm for covering integer programs with at most k variable per constraint. We study extreme points of the standard LP relaxation for the traveling salesperson problem and show that they can be much more complex than was previously known. The k-edge-connected spanning multi-subgraph problem has the same LP and we prove a lower bound and conjecture an upper bound on the approximability of variants of this problem. Finally, we show that for packing/covering integer programs with a bounded number of constraints, for any epsilon > 0, there is an LP with integrality gap at most 1 + epsilon.

The central topic of this thesis is Schnyder's Theorem. Schnyder's Theorem provides a characterization of planar graphs in terms of their poset dimension, as follows: a graph G is planar if and only if the dimension of the incidence poset of G is at most three. One of the implications of the theorem is proved by giving an explicit mapping of the vertices to R^2 that defines a straightline embedding of the graph. The other implication is proved by introducing the concept of normal labelling. Normal labellings of plane triangulations can be used to obtain a realizer of the incidence poset. We present an exposition of Schnyder’s theorem with his original proof, using normal labellings. An alternate proof of Schnyder’s Theorem is also presented. This alternate proof does not use normal labellings, instead we use some structural properties of a realizer of the incidence poset to deduce the result. Some applications and a generalization of one implication of Schnyder’s Theorem are also presented in this work. Normal labellings of plane triangulations can be used to obtain a barycentric embedding of a plane triangulation, and they also induce a partition of the edge set of a plane triangulation into edge disjoint trees. These two applications of Schnyder’s Theorem and a third one, relating realizers of the incidence poset and canonical orderings to obtain a compact drawing of a graph, are also presented. A generalization, to abstract simplicial complexes, of one of the implications of Schnyder’s Theorem was proved by Ossona de Mendez. This generalization is also presented in this work. The concept of order labelling is also introduced and we show some similarities of the order labelling and the normal labelling. Finally, we conclude this work by showing the source code of some implementations done in Sage.

Graph searching problems are described as games played on graphs, between a set of searchers and a fugitive. Variants of the game restrict the abilities of the searchers and the fugitive and the corresponding search number (the least number of searchers that have a winning strategy) is related to several well-known parameters in graph theory. One popular variant is called the Cops and Robber game, where the searchers (cops) and the fugitive (robber) move in rounds, and in each round they move to an adjacent vertex. This game, defined in late 1970's, has been studied intensively. The most famous open problem is Meyniel's conjecture, which states that the cop number (the minimum number of cops that can always capture the robber) of a connected graph on n vertices is O(sqrt n). We consider a version of the Cops and Robber game, where the robber is faster than the cops, but is not allowed to jump over the cops. This version was first studied in 2008. We show that when the robber has speed s, the cop number of a connected n-vertex graph can be as large as Omega(n^(s/s+1)). This improves the Omega(n^(s-3/s-2)) lower bound of Frieze, Krivelevich, and Loh (Variations on Cops and Robbers, J. Graph Theory, to appear). We also conjecture a general upper bound O(n^(s/s+1)) for the cop number, generalizing Meyniel's conjecture. Then we focus on the version where the robber is infinitely fast, but is again not allowed to jump over the cops. We give a mathematical characterization for graphs with cop number one. For a graph with treewidth tw and maximum degree Delta, we prove the cop number is between (tw+1)/(Delta+1) and tw+1. Using this we show that the cop number of the m-dimensional hypercube is between c1 n / m sqrt(m) and c2 n / m for some constants c1 and c2. If G is a connected interval graph on n vertices, then we give a polynomial time 3-approximation algorithm for finding the cop number of G, and prove that the cop number is O(sqrt(n)). We prove that given n, there exists a connected chordal graph on n vertices with cop number Omega(n/log n). We show a lower bound for the cop numbers of expander graphs, and use this to prove that the random G(n,p) that is not very sparse, asymptotically almost surely has cop number between d1 / p and d2 log (np) / p for suitable constants d1 and d2. Moreover, we prove that a fixed-degree regular random graph with n vertices asymptotically almost surely has cop number Theta(n).

Statistical analysis of network data is an active field of study, in which researchers inves- tigate graph-theoretic concepts and various probability models that explain the behaviour of real networks. This thesis attempts to combine two of these concepts: an exponential random graph and a centrality index. Exponential random graphs comprise the most useful class of probability models for network data. These models often require the assumption of a complex dependence structure, which creates certain difficulties in the estimation of unknown model parameters. However, in the context of dynamic networks the exponential random graph model provides the opportunity to incorporate a complex network structure such as centrality without the usual drawbacks associated with parameter estimation. The thesis employs this idea by proposing probability models that are equivalent to the logistic regression models and that can be used to explain behaviour of both static and dynamic networks.

The theories of causality put forward by Pearl and the Spirtes-Glymour-Scheines group have entered the mainstream of statistical thinking. These theories show that under ideal conditions, causal relationships can be inferred from purely statistical observational data. Nancy Cartwright advances certain arguments against these causal inference algorithms: the well-known factory example argument against the Causal Markov condition and an argument against faithfulness. We point to the dependence of the first argument on undefined categories external to the technical apparatus of causal inference algorithms. We acknowledge the possible practical implication of her second argument, yet we maintain, with respect to both arguments, that this variety of causal inference, if not universal, is nonetheless eminently useful. Cartwright argues against assumptions that are essential not only to causal inference algorithms but to causal inference generally, even if, as she contends, they are not without exception and that the same is true of other, likewise essential, assumptions. We indicate that causal inference is an iterative process and that causal inference algorithms assist, rather than replace, that process as performed by human beings.

We formulate a novel approach to infer conditional independence models or Markov structure of a multivariate distribution. Specifically, our objective is to place informative prior distributions over graphs (decomposable and unrestricted) and sample efficiently from the induced posterior distribution. We also explore the idea of factorizing according to complete sets of a graph; which implies working with a hypergraph that cannot be retrieved from the graph alone. The key idea we develop in this paper is a parametrization of hypergraphs using the geometry of points in $R^m$. This induces informative priors on graphs from specified priors on finite sets of points. Constructing hypergraphs from finite point sets has been well studied in the fields of computational topology and random geometric graphs. We develop the framework underlying this idea and illustrate its efficacy using simulations. / Dissertation

Recently there is a lot of interest in the study of Sturm-Liouville problems on graphs, called quantum graphs. However the study on cyclic quantum graphs are scarce. In this thesis, we shall rst consider a characteristic function approach to the spectral analysis for the Schrodinger operator H acting on graphene-like graphs|in nite periodic hexagonal graphs with 3 distinct adjacent edges and 3 distinct potentials de ned on them. We apply the Floquet-Bloch theory to derive a Floquet equation with parameters theta_1, theta_2, whose roots de ne all the spectral values of H. Then we show that the spectrum of this operator is continuous. Our results generalize those of Kuchment-Post and Korotyaev-Lobanov. Our method is also simpler and more direct. Next we solve two Ambarzumyan problems, one for graphene and another for a cyclic graph with two vertices and 3 edges. Finally we solve an Hochstadt-Lieberman type inverse spectral problem for the same cyclic graph with two vertices and 3 edges. Keywords : quantum graphs, graphene, spectrum, Ambarzumyan problem, inverse spectral problem.

A relatively new preconditioning technique called support graph preconditioning has many merits over the traditional incomplete factorization based methods. A major limitation of this technique is that it is applicable to symmetric diagonally dominant matrices only. This work presents a technique that can be used to transform the symmetric positive definite matrices arising from elliptic finite element problems into symmetric diagonally dominant M-matrices. The basic idea is to approximate the element gradient matrix by taking the gradients along chosen edges, whose unit vectors form a new coordinate system. For Lagrangian elements, the rows of the element gradient matrix in this new coordinate system are scaled edge vectors, thus a diagonally dominant symmetric semidefinite M-matrix can be generated to approximate the element stiffness matrix. Depending on the element type, one or more such coordinate systems are required to obtain a global nonsingular M-matrix. Since such approximation takes place at the element level, the degradation in the quality of the preconditioner is only a small constant factor independent of the size of the problem. This technique of element coordinate transformations applies to a variety of first order Lagrangian elements. Combination of this technique and other techniques enables us to construct an M-matrix preconditioner for a wide range of second order elliptic problems even with higher order elements. Another contribution of this work is the proposal of a new variant of Vaidya’s support graph preconditioning technique called modified domain partitioned support graph preconditioners. Numerical experiments are conducted for various second order elliptic finite element problems, along with performance comparison to the incomplete factorization based preconditioners. Results show that these support graph preconditioners are superior when solving ill-conditioned problems. In addition, the domain partition feature provides inherent parallelism, and initial experiments show a good potential of parallelization and scalability of these preconditioners.

No description available.