This thesis is devoted to the analysis of a class of iterative probabilistic algorithms in regular graphs, called locally greedy algorithms, which will provide bounds for graph functions in regular graphs with large girth. This class is useful because, by conveniently setting the parameters associated with it, we may derive algorithms for some well-known graph problems, such as algorithms to find a large independent set, a large induced forest, or even a small dominating set in an input graph G. The name ``locally greedy" comes from the fact that, in an algorithm of this class, the probability associated with the random selection of a vertex v is determined by the current state of the vertices within some fixed distance of v. Given r > 2 and an r-regular graph G, we determine the expected performance of a locally greedy algorithm in G, depending on the girth g of the input and on the degree r of its vertices. When the girth of the graph is sufficiently large, this analysis leads to new lower bounds on the independence number of G and on the maximum number of vertices in an induced forest in G, which, in both cases, improve the bounds previously known. It also implies bounds on the same functions in graphs with large girth and maximum degree r and in random regular graphs. As a matter of fact, the asymptotic lower bounds on the cardinality of a maximum induced forest in a random regular graph improve earlier bounds, while, for independent sets, our bounds coincide with asymptotic lower bounds first obtained by Wormald. Our result provides an alternative proof of these bounds which avoids sharp concentration arguments. The main contribution of this work lies in the method presented rather than in these particular new bounds. This method allows us, in some sense, to directly analyse prioritised algorithms in regular graphs, so that the class of locally greedy algorithms, or slight modifications thereof, may be applied to a wider range of problems in regular graphs with large girth.

The thesis describes new results for several problems in random graph theory. The first problem relates to the uniform random graph model in the supercritical phase; i.e. a graph, uniformly distributed, on $n$ vertices and $M=n/2+s$ edges for $s=s(n)$ satisfying $n^{2/3}=o(s)$ and $s=o(n)$. The property studied is the length of the longest cycle in the graph. We give a new upper bound, which holds asymptotically almost surely, on this length. As part of our proof we establish a result about the heaviest cycle in a certain randomly-edge-weighted nearly-3-regular graph, which may be of independent interest. Our second result is a new contiguity result for a random $d$-regular graph. Let $j=j(n)$ be a function that is linear in $n$. A $(d,d-1)$-irregular graph is a graph which is $d$-regular except for $2j$ vertices of degree $d-1$. A $j$-edge matching in a graph is a set of $j$ independent edges. In this thesis we prove the new result that a random $(d,d-1)$-irregular graph plus a random $j$-edge matching is contiguous to a random $d$-regular graph, in the sense that in the two spaces, the same events have probability approaching 1 as $n\to\infty$. This allows one to deduce properties, such as colourability, of the random irregular graph from the corresponding properties of the random regular one. The proof applies the small subgraph conditioning method to the number of $j$-edge matchings in a random $d$-regular graph. The third problem is about the 3-colourability of a random 5-regular graph. Call a colouring balanced if the number of vertices of each colour is equal, and locally rainbow if every vertex is adjacent to vertices of all the other colours. Using the small subgraph conditioning method, we give a condition on the variance of the number of locally rainbow balanced 3-colourings which, if satisfied, establishes that the chromatic number of the random 5-regular graph is asymptotically almost surely equal to 3. We also describe related work which provides evidence that the condition is likely to be true. The fourth problem is about the chromatic number of a random $d$-regular graph for fixed $d$. Achlioptas and Moore recently announced a proof that a random $d$-regular graph asymptotically almost surely has chromatic number $k-1$, $k$, or $k+1$, where $k$ is the smallest integer satisfying $d < 2(k-1)\log(k-1)$. In this thesis we prove that, asymptotically almost surely, it is not $k+1$, provided a certain second moment condition holds. The proof applies the small subgraph conditioning method to the number of balanced $k$-colourings, where a colouring is balanced if the number of vertices of each colour is equal. We also give evidence that suggests that the required second moment condition is true.

Inconsistency often arises in real-world databases and, as a result, critical queries over dirty data may lead users to make ill-informed decisions. Functional dependencies (FDs) can be used to specify intended semantics of the underlying data and aid with the cleaning task. Enumerating and evaluating all the possible repairs to FD violations is infeasible, while approaches that produce a single repair or attempt to isolate the dirty portion of data are often too destructive or constraining. In this thesis, we leverage a recent advance in data cleaning that allows sampling from a well-defined space of reasonable repairs, and provide the user with a data management tool that gives uncertain query answers over this space. We propose a framework to compute probabilistic query answers as though each repair sample were a possible world. We show experimentally that queries over many possible repairs produce results that are more useful than other approaches and that our system can scale to large datasets.

This thesis is devoted to the analysis of a class of iterative probabilistic algorithms in regular graphs, called locally greedy algorithms, which will provide bounds for graph functions in regular graphs with large girth. This class is useful because, by conveniently setting the parameters associated with it, we may derive algorithms for some well-known graph problems, such as algorithms to find a large independent set, a large induced forest, or even a small dominating set in an input graph G. The name ``locally greedy" comes from the fact that, in an algorithm of this class, the probability associated with the random selection of a vertex v is determined by the current state of the vertices within some fixed distance of v. Given r > 2 and an r-regular graph G, we determine the expected performance of a locally greedy algorithm in G, depending on the girth g of the input and on the degree r of its vertices. When the girth of the graph is sufficiently large, this analysis leads to new lower bounds on the independence number of G and on the maximum number of vertices in an induced forest in G, which, in both cases, improve the bounds previously known. It also implies bounds on the same functions in graphs with large girth and maximum degree r and in random regular graphs. As a matter of fact, the asymptotic lower bounds on the cardinality of a maximum induced forest in a random regular graph improve earlier bounds, while, for independent sets, our bounds coincide with asymptotic lower bounds first obtained by Wormald. Our result provides an alternative proof of these bounds which avoids sharp concentration arguments. The main contribution of this work lies in the method presented rather than in these particular new bounds. This method allows us, in some sense, to directly analyse prioritised algorithms in regular graphs, so that the class of locally greedy algorithms, or slight modifications thereof, may be applied to a wider range of problems in regular graphs with large girth.

The thesis describes new results for several problems in random graph theory. The first problem relates to the uniform random graph model in the supercritical phase; i.e. a graph, uniformly distributed, on $n$ vertices and $M=n/2+s$ edges for $s=s(n)$ satisfying $n^{2/3}=o(s)$ and $s=o(n)$. The property studied is the length of the longest cycle in the graph. We give a new upper bound, which holds asymptotically almost surely, on this length. As part of our proof we establish a result about the heaviest cycle in a certain randomly-edge-weighted nearly-3-regular graph, which may be of independent interest. Our second result is a new contiguity result for a random $d$-regular graph. Let $j=j(n)$ be a function that is linear in $n$. A $(d,d-1)$-irregular graph is a graph which is $d$-regular except for $2j$ vertices of degree $d-1$. A $j$-edge matching in a graph is a set of $j$ independent edges. In this thesis we prove the new result that a random $(d,d-1)$-irregular graph plus a random $j$-edge matching is contiguous to a random $d$-regular graph, in the sense that in the two spaces, the same events have probability approaching 1 as $n\to\infty$. This allows one to deduce properties, such as colourability, of the random irregular graph from the corresponding properties of the random regular one. The proof applies the small subgraph conditioning method to the number of $j$-edge matchings in a random $d$-regular graph. The third problem is about the 3-colourability of a random 5-regular graph. Call a colouring balanced if the number of vertices of each colour is equal, and locally rainbow if every vertex is adjacent to vertices of all the other colours. Using the small subgraph conditioning method, we give a condition on the variance of the number of locally rainbow balanced 3-colourings which, if satisfied, establishes that the chromatic number of the random 5-regular graph is asymptotically almost surely equal to 3. We also describe related work which provides evidence that the condition is likely to be true. The fourth problem is about the chromatic number of a random $d$-regular graph for fixed $d$. Achlioptas and Moore recently announced a proof that a random $d$-regular graph asymptotically almost surely has chromatic number $k-1$, $k$, or $k+1$, where $k$ is the smallest integer satisfying $d < 2(k-1)\log(k-1)$. In this thesis we prove that, asymptotically almost surely, it is not $k+1$, provided a certain second moment condition holds. The proof applies the small subgraph conditioning method to the number of balanced $k$-colourings, where a colouring is balanced if the number of vertices of each colour is equal. We also give evidence that suggests that the required second moment condition is true.

Modern aerospace systems design problems are often characterized by the necessity to identify and enable multiple tradeoffs. This can be accomplished by transformation of the design problem to a multiple objective optimization formulation. However, existing multiple criteria techniques can lead to unattractive solutions due to their basic assumptions; namely that of monotonically increasing utility and independent decision criteria. Further, it can be difficult to quantify the relative importance of each decision metric, and it is very difficult to view the pertinent tradeoffs for large-scale problems. This thesis presents a discussion and application of Multiple Criteria Decision Making (MCDM) to aerospace systems design and quantifies the complications associated with switching from single to multiple objectives. It then presents a procedure to tackle these problems by utilizing a two-part relative importance model for each criterion. This model contains a static and dynamic portion with respect to the current value of the decision metric. The static portion is selected based on an entropy analogy of each metric within the decision space to alleviate the problems associated with quantifying basic (monotonic) relative importance. This static value is further modified by examination of the interdependence of the decision metrics. The dynamic contribution uses a penalty function approach for any constraints and further reduces the importance of any metric approaching a user-specified threshold level. This reduces the impact of the assumption of monotonically increasing utility by constantly updating the relative importance of a given metric based on its current value. A method is also developed to determine a linearly independent subset of the original requirements, resulting in compact visualization techniques for large-scale problems.

Inconsistency often arises in real-world databases and, as a result, critical queries over dirty data may lead users to make ill-informed decisions. Functional dependencies (FDs) can be used to specify intended semantics of the underlying data and aid with the cleaning task. Enumerating and evaluating all the possible repairs to FD violations is infeasible, while approaches that produce a single repair or attempt to isolate the dirty portion of data are often too destructive or constraining. In this thesis, we leverage a recent advance in data cleaning that allows sampling from a well-defined space of reasonable repairs, and provide the user with a data management tool that gives uncertain query answers over this space. We propose a framework to compute probabilistic query answers as though each repair sample were a possible world. We show experimentally that queries over many possible repairs produce results that are more useful than other approaches and that our system can scale to large datasets.

With advances in communications technologies, there is a constant need for higher data rates. One possible solution to overcome this need is to allocate additional bandwidth. However, due to spectrum scarcity this is no longer feasible. In addition, the results of spectrum measurement campaigns discovered the fact that the available spectrum is under-utilized. One of the most significant solutions to solve the under- utilization of radio-frequency (RF) spectrum is the cognitive radio (CR) concept. A valid mathematical model that can be applied for most practical scenarios and also captures the random fluctuations of the spectrum is necessary. This model provides a significant insight and also a better quantitative understanding of such systems and this is the topic of this dissertation. Compact mathematical formulations that describe the realistic spectrum usage would improve the recent theoretical work to a large extent. The data generated for such models, provide a mean for a more realistic evaluation of the performance of CR systems. However, measurement based models require a large amount of data and are subject to measurement errors. They are also likely to be subject to the measurement time, location, and methodology. In the first part of this dissertation, we introduce cognitive radio networks and their role on solving the problem of under-utilized spectrum. In the second part of this dissertation, we target the random variable which accounts for the fraction of available subcarriers for the secondary users in an OFDMA based CR system. The time and location dependency of the traffic is taken into account by a non-homogenous Poisson Point Process (PPP). In the third part, we propose a comprehensive statistical model for user activity, spectrum occupancy, and system throughput in the presence of mutual interference in an OFDMA-based CR network which accounts for the sensing procedure of spectrum sensor, spectrum demand-model and spatial density of primary users, system objective for user satisfaction which is to support as many users as possible, and environment-dependent conditions such as propagation path loss, shadowing, and channel fading. In the last part of this dissertation, unlike the second and the third parts that the modeling is theoretical and based on limiting assumptions, the spectrum usage modeling is based on real data collected from an extensive measurement.

The increasing penetration of renewable energy resources within the Great Britain (GB) transmission system has created much greater variability of power flows within the transmission network. Consequently, modern transmission networks are presented with an ever increasing range of operating conditions. As a result, decision making in the Electricity National Control Centre (ENCC) of the GB electrical power transmission system is becoming more complex and control room actions are required for reducing timescales in the future so as to enable optimum operation of the system. To maximise utilisation of the electricity transmission system there is a requirement for fast transient and dynamic stability control. In this regard, GB electrical power transmissions system reinforcement using new technology, such as High Voltage Direct Current (HVDC) links and Thyristor-Controlled Series Compensation (TCSC), is planned to come into operation. The research aim of this PhD thesis is to fully investigate the effects of HVDC lines on power system small-disturbance stability in the presence of operational uncertainties. The main research outcome is the comprehensive probabilistic assessment of the stability improvements that can be achieved through the use of supplementary damping control when applied to HVDC systems. In this thesis, two control schemes for small-signal dynamic stability enhancement of an embedded HVDC link are proposed: Modal Linear Quadratic Gaussian (MLQG) controller and Model Predictive Controller (MPC). Following these studies, probabilistic methodologies are developed in order to test of the robustness of HVDC based damping controllers, which involves using classification techniques to identify possible mitigation options for power system operators. The Monte Carlo (MC) and Point Estimated Method (PEM) are developed in order to identify the statistical distributions of critical modes of a power system in the presence of uncertainties. In addition, eigenvalue sensitivity analysis is devised and demonstrated to ensure accurate results when the PEM is used with test systems. Finally, the concepts and techniques introduced in the thesis are combined to investigate robustness for the widely adopted MLQG controller and the recently introduced MPC, which are designed as the supplementary controls of an embedded HVDC link for damping inter-area oscillations. Power system controllers are designed using a linearised model of the system and tuned for a nominal operating point. The assumption is made that the system will be operating within an acceptable proximity range of its nominal operating condition and that the uncertainty created by changes within each operating point can possibly have an adverse effect on the controller’s performance.

In this dissertation we consider several extremal and probabilistic problems in bootstrap percolation on various families of graphs, including grids, hypercubes and trees. Bootstrap percolation is one of the simplest cellular automata. The most widely studied model is the so-called r-neighbour bootstrap percolation, in which we consider the spread of infection on a graph G according to the following deterministic rule: infected vertices of G remain infected forever and in successive rounds healthy vertices with at least r already infected neighbours become infected. Percolation is said to occur if eventually every vertex is infected. In Chapter 1 we consider a particular extremal problem in 2-neighbour bootstrap percolation on the n \times n square grid. We show that the maximum time an infection process started from an initially infected set of size n can take to infect the entire vertex set is equal to the integer nearest to (5n^2-2n)/8. In Chapter 2 we relax the condition on the size of the initially infected sets and show that the maximum time for sets of arbitrary size is 13n^2/18+O(n). In Chapter 3 we consider a similar problem, namely the maximum percolation time for 2-neighbour bootstrap percolation on the hypercube. We give an exact answer to this question showing that this time is \lfloor n^2/3 \rfloor. In Chapter 4 we consider the following probabilistic problem in bootstrap percolation: let T be an infinite tree with branching number \br(T) = b. Initially, infect every vertex of T independently with probability p > 0. Given r, define the critical probability, p_c(T,r), to be the value of p at which percolation becomes likely to occur. Answering a problem posed by Balogh, Peres and Pete, we show that if b \geq r then the value of b itself does not yield any non-trivial lower bound on p_c(T,r). In other words, for any \varepsilon > 0 there exists a tree T with branching number \br(T) = b and critical probability p_c(T,r) < \varepsilon. However, in Chapter 5 we prove that this is false if we limit ourselves to the well-studied family of Galton--Watson trees. We show that for every r \geq 2 there exists a constant c_r>0 such that if T is a Galton--Watson tree with branching number \br(T) = b \geq r then \[ p_c(T,r) > \frac{c_r}{b} e^{-\frac{b}{r-1}}. \] We also show that this bound is sharp up to a factor of O(b) by describing an explicit family of Galton--Watson trees with critical probability bounded from above by C_r e^{-\frac{b}{r-1}} for some constant C_r>0.