Completions of epsilon-dense partial Latin squares

A classical question in combinatorics is the following: given a partial Latin square $P$, when can we complete $P$ to a Latin square $L$? In this paper, we investigate the class of textbf{$epsilon$-dense partial Latin squares}: partial Latin squares in which each symbol, row, and column contains no more than $epsilon n$-many nonblank cells. Based on a conjecture of Nash-Williams, Daykin and H"aggkvist conjectured that all $frac{1}{4}$-dense partial Latin squares are completable. In this paper, we will discuss the proof methods and results used in previous attempts to resolve this conjecture, introduce a novel technique derived from a paper by Jacobson and Matthews on generating random Latin squares, and use this novel technique to study $ epsilon$-dense partial Latin squares that contain no more than $delta n^2$ filled cells in total.

In Chapter 2, we construct completions for all $ epsilon$-dense partial Latin squares containing no more than $delta n^2$ filled cells in total, given that $epsilon < frac{1}{12}, delta < frac{ left(1-12epsilonright)^{2}}{10409}$. In particular, we show that all $9.8 cdot 10^{-5}$-dense partial Latin squares are completable. In Chapter 4, we augment these results by roughly a factor of two using some probabilistic techniques. These results improve prior work by Gustavsson, which required $epsilon = delta leq 10^{-7}$, as well as Chetwynd and H"aggkvist, which required $epsilon = delta = 10^{-5}$, $n$ even and greater than $10^7$.

If we omit the probabilistic techniques noted above, we further show that such completions can always be found in polynomial time. This contrasts a result of Colbourn, which states that completing arbitrary partial Latin squares is an NP-complete task. In Chapter 3, we strengthen Colbourn's result to the claim that completing an arbitrary $left(frac{1}{2} + epsilonright)$-dense partial Latin square is NP-complete, for any $epsilon > 0$.

Colbourn's result hinges heavily on a connection between triangulations of tripartite graphs and Latin squares. Motivated by this, we use our results on Latin squares to prove that any tripartite graph $G = (V_1, V_2, V_3)$ such that begin{itemize} item $|V_1| = |V_2| = |V_3| = n$, item For every vertex $v in V_i$, $deg_+(v) = deg_-(v) geq (1- epsilon)n,$ and item $|E(G)| > (1 - delta)cdot 3n^2$ end{itemize} admits a triangulation, if $epsilon < frac{1}{132}$, $delta < frac{(1 -132epsilon)^2 }{83272}$. In particular, this holds when $epsilon = delta=1.197 cdot 10^{-5}$.

This strengthens results of Gustavsson, which requires $epsilon = delta = 10^{-7}$.

In an unrelated vein, Chapter 6 explores the class of textbf{quasirandom graphs}, a notion first introduced by Chung, Graham and Wilson cite{chung1989quasi} in 1989. Roughly speaking, a sequence of graphs is called "quasirandom"' if it has a number of properties possessed by the random graph, all of which turn out to be equivalent. In this chapter, we study possible extensions of these results to random $k$-edge colorings, and create an analogue of Chung, Graham and Wilson's result for such colorings.

Theoretical studies of novel organic systems : biradicals, polyradicals, and conducting polymers

Chapter 1

Cyclobutanediyl has been studied in both its singlet and triplet states by ab initio electronic structure theory. The triplet, which is the ground state of the molecule, exists in both C_(2h) and C_(2v) forms, which interconvert via a C_s transition state. For the singlet, only a C_(2h) form is found. It passes, via a C_s transition state, onto the C_(2v) surface on which bicyclobutane is the only minimum. The ring-flipping (inversion) process in bicyclobutane includes the singlet biradical as an intermediate, and involves a novel, nonleast motion pathway. Semiclassical periodic orbit theory indicates that the various minima on both the singlet and triplet surfaces can interconvert via quantum mechanical tunneling.

Chapter 2

The dimethylenepolycyclobutadienes (n) are the non-Kekulé analogues of the classical acenes. Application of a variety of theoretical methods reveals several novel features of such structures. Most interesting is the emergence of a parity rule. When n is even, n is predicted to be a singlet, with n disjoint NBMOs. When n is odd, theory predicts a triplet ground state with (n+1) NBMOs that are not fully disjoint.

Chapter 3

Bi(cyclobutadienyl) (2), the cyclobutadiene analogue of biphenyl, and its homologues tri- (3) and tetra(cyclobutadienyl) (4) have been studied using electronic structure theory. Ab initio calculations on 2 reveal that the central bond is a true double bond, and that the structure is best thought of as two allyl radicals plus an ethylene. The singlet and triplet states are essentially degenerate. Trimer 3 is two allyls plus a dimethylenecyclobutanediyl, while 4 is two coplanar bi(cyclobutadienyl) units connected by a single bond. For both 3 and 4, the quintet, triplet, and singlet states are essentially degenerate, indicating that they are tetraradicals. The infinite polymer, polycyclobutadiene, has been studied by HMO, EHCO, and VEH methods. Several geometries based on the structures of 3 and 4 have been studied, and the band structures are quite intriguing. A novel crossing between the valence and conduction bands produces a small band gap and a high density of states at the Fermi level.

Chapter 4

At the level of Hückel theory, polyfulvene has a HOCO-LUCO degeneracy much like that seen in polyacetylene. Higher levels of theory remove the degeneracy, but the band gap (E_g) is predicted to be significantly smaller than analogous structures such as polythiophene and polypyrrole at the fulvenoid geometry. An alternative geometry, which we have termed quinoid, is also conceivable for polyfulvene, and it is predicted to have a much larger E_g. The effects of benzannelation to produce analogues of polyisothianaphthene have been evaluated. We propose a new model for such structures based on conventional orbital mixing arguments. Several of the proposed structures have quite interesting properties, which suggest that they are excellent candidates for conducting polymers.

Chapter 5

Theoretical studies of polydimethylenecyclobutene and polydiisopropylidene- cyclobutene reveal that, because of steric crowding, they cannot achieve a planar, fully conjugated structure in either their undoped or doped states. Rather, the structure consists of essentially orthogonal hexatriene units. Such a structure is incompatible with conventional conduction mechanisms involving polarons and bipolarons.

Revealing, illuminating, and modifying proteins in human diseases using noncanonical amino acids

To better understand human diseases, much recent work has focused on proteins to either identify disease targets through proteomics or produce therapeutics via protein engineering. Noncanonical amino acids (ncAAs) are tools for altering the chemical and physical properties of proteins, providing a facile strategy not only to label proteins but also to engineer proteins with novel properties. My thesis research has focused on the development and applications of noncanonical amino acids in identifying, imaging, and engineering proteins for studying human diseases. Chapter 1 introduces the concept of ncAAs and reveals insights to how I chose my thesis projects.

ncAAs have been incorporated to tag and enrich newly synthesized proteins for mass spectrometry through a method termed BONCAT, or bioorthogonal noncanonical amino acid tagging. Chapter 2 describes the investigation of the proteomic response of human breast cancer cells to induced expression of tumor suppressor microRNA miR-126 by combining BONCAT with another proteomic method, SILAC or stable isotope labeling by amino acids in cell culture. This proteomic analysis led to the discovery of a direct target of miR-126, shedding new light on its role in suppressing cancer metastasis.

In addition to mass spectrometry, ncAAs can also be utilized to fluorescently label proteins. Chapter 3 details the synthesis of a set of cell-permeant cyclooctyne probes and demonstration of selective labeling of newly synthesized proteins in live mammalian cells using azidohomoalanine. Similar to live cell imaging, the ability to selectively label a particular cell type within a mixed cell population is important to interrogating many biological systems, such as tumor microenvironments. By taking advantage of the metabolic differences between cancer and normal cells, Chapter 5 discusses efforts to develop selective labeling of cancer cells using a glutamine analogue.

Furthermore, Chapter 4 describes the first demonstration of global replacement at polar amino acid positions and its application in developing an alternative PEGylation strategy for therapeutic proteins. Polar amino acids typically occupy solvent-exposed positions on the protein surface, and incorporation of noncanonical amino acids at these positions should allow easier modification and cause less perturbation compared to replacements at the interior positions of proteins.

Efficient methods for stochastic optimal control

The Hamilton Jacobi Bellman (HJB) equation is central to stochastic optimal control (SOC) theory, yielding the optimal solution to general problems specified by known dynamics and a specified cost functional. Given the assumption of quadratic cost on the control input, it is well known that the HJB reduces to a particular partial differential equation (PDE). While powerful, this reduction is not commonly used as the PDE is of second order, is nonlinear, and examples exist where the problem may not have a solution in a classical sense. Furthermore, each state of the system appears as another dimension of the PDE, giving rise to the curse of dimensionality. Since the number of degrees of freedom required to solve the optimal control problem grows exponentially with dimension, the problem becomes intractable for systems with all but modest dimension.

In the last decade researchers have found that under certain, fairly non-restrictive structural assumptions, the HJB may be transformed into a linear PDE, with an interesting analogue in the discretized domain of Markov Decision Processes (MDP). The work presented in this thesis uses the linearity of this particular form of the HJB PDE to push the computational boundaries of stochastic optimal control.

This is done by crafting together previously disjoint lines of research in computation. The first of these is the use of Sum of Squares (SOS) techniques for synthesis of control policies. A candidate polynomial with variable coefficients is proposed as the solution to the stochastic optimal control problem. An SOS relaxation is then taken to the partial differential constraints, leading to a hierarchy of semidefinite relaxations with improving sub-optimality gap. The resulting approximate solutions are shown to be guaranteed over- and under-approximations for the optimal value function. It is shown that these results extend to arbitrary parabolic and elliptic PDEs, yielding a novel method for Uncertainty Quantification (UQ) of systems governed by partial differential constraints. Domain decomposition techniques are also made available, allowing for such problems to be solved via parallelization and low-order polynomials.

The optimization-based SOS technique is then contrasted with the Separated Representation (SR) approach from the applied mathematics community. The technique allows for systems of equations to be solved through a low-rank decomposition that results in algorithms that scale linearly with dimensionality. Its application in stochastic optimal control allows for previously uncomputable problems to be solved quickly, scaling to such complex systems as the Quadcopter and VTOL aircraft. This technique may be combined with the SOS approach, yielding not only a numerical technique, but also an analytical one that allows for entirely new classes of systems to be studied and for stability properties to be guaranteed.

The analysis of the linear HJB is completed by the study of its implications in application. It is shown that the HJB and a popular technique in robotics, the use of navigation functions, sit on opposite ends of a spectrum of optimization problems, upon which tradeoffs may be made in problem complexity. Analytical solutions to the HJB in these settings are available in simplified domains, yielding guidance towards optimality for approximation schemes. Finally, the use of HJB equations in temporal multi-task planning problems is investigated. It is demonstrated that such problems are reducible to a sequence of SOC problems linked via boundary conditions. The linearity of the PDE allows us to pre-compute control policy primitives and then compose them, at essentially zero cost, to satisfy a complex temporal logic specification.

Proton-Coupled Reduction of N2 Facilitated by Molecular Fe Complexes

The activation of Fe-coordinated N₂ via the formal addition of hydrogen atom equivalents is explored in this thesis. These reactions may occur in nitrogenase enzymes during the biological conversion of N₂ to NH₃. To understand these reactions, the N₂ reactivity of a series of molecular Fe(N₂) platforms is investigated. A trigonal pyramidal, carbon-ligated Fe^I complex was prepared that displays a similar geometry to that of the resting state 'belt' Fe atoms of nitrogenase. Upon reduction, this species was shown to coordinate N₂, concomitant with significant weakening of the C-Fe interaction. This hemilability of the axial ligand may play a critical role in mediating the interconversion of Fe(N_xH_y) species during N₂ conversion to NH₃. In fact, a trigonal pyramidal borane-ligated Fe complex was shown to catalyze this transformation, generating up to 8.49 equivalents of NH₃. To shed light on the mechanistic details of this reaction, protonation of a borane-ligated Fe(N₂) complex was investigated and found to give rise to a mixture of species that contains an iron hydrazido(2-) [Fe(NNH₂)] complex. The identification of this species is suggestive of an early N-N bond cleavage event en route to NH₃ production, but the highly-reactive nature of this complex frustrated direct attempts to probe this possibility. A structurally-analogous silyl-ligated Fe(N₂) complex was found to react productively with hydrogen atom equivalents, giving rise to an isolable Fe(NNH₂) species. Spectroscopic and crystallographic studies benefited from the enhanced stability of this complex relative to the borane analogue. One-electron reduction of this species initiates a spontaneous disproportionation reaction with an iron hydrazine [Fe(NH₂NH₂)] complex as the predominant reaction product. This transformation provides support for an Fe-mediated N₂ activation mechanism that proceeds via a late N-N bond cleavage. In hopes of gaining more fundamental insight into these reactions, a series of Fe(CN) complexes were prepared and reacted with hydrogen-atom equivalents. Significant quantities of CH₄ and NH₃ are generated in these reactions as a result of complete C-N bond activation. A series of Fe(CNH_x) were found to be exceptionally stable and may be intermediates in these reactions. The stability of these compounds permitted collection of thermodynamic parameters pertinent to the unique N-H bonds. This data is comparatively discussed with the theoretically-predicted data of the N₂-derived Fe(NNH_x) species. Exceptionally-weak N-H bond enthalpies are found for many of these compounds, and sheds light on their short-lived nature and tendency to evolve H₂. As a whole, these works both establish and provide a means to understand Fe-mediated N₂ activation via the addition of hydrogen atom equivalents.

Solubility and Diffusivity of Water in Lunar Basalt, and Chemical Zonation in Olivine-Hosted Melt Inclusions

I report the solubility and diffusivity of water in lunar basalt and an iron-free basaltic analogue at 1 atm and 1350 °C. Such parameters are critical for understanding the degassing histories of lunar pyroclastic glasses. Solubility experiments have been conducted over a range of fO₂ conditions from three log units below to five log units above the iron-wüstite buffer (IW) and over a range of pH₂/pH₂O from 0.03 to 24. Quenched experimental glasses were analyzed by Fourier transform infrared spectroscopy (FTIR) and secondary ionization mass spectrometry (SIMS) and were found to contain up to ~420 ppm water. Results demonstrate that, under the conditions of our experiments: (1) hydroxyl is the only H-bearing species detected by FTIR; (2) the solubility of water is proportional to the square root of pH₂O in the furnace atmosphere and is independent of fO₂ and pH₂/pH₂O; (3) the solubility of water is very similar in both melt compositions; (4) the concentration of H₂ in our iron-free experiments is <3 ppm, even at oxygen fugacities as low as IW-2.3 and pH₂/pH₂O as high as 24; and (5) SIMS analyses of water in iron-rich glasses equilibrated under variable fO₂ conditions can be strongly influenced by matrix effects, even when the concentrations of water in the glasses are low. Our results can be used to constrain the entrapment pressure of the lunar melt inclusions of Hauri et al. (2011).

Diffusion experiments were conducted over a range of fO₂ conditions from IW-2.2 to IW+6.7 and over a range of pH₂/pH₂O from nominally zero to ~10. The water concentrations measured in our quenched experimental glasses by SIMS and FTIR vary from a few ppm to ~430 ppm. Water concentration gradients are well described by models in which the diffusivity of water (D^*_water) is assumed to be constant. The relationship between D^*_water and water concentration is well described by a modified speciation model (Ni et al. 2012) in which both molecular water and hydroxyl are allowed to diffuse. The success of this modified speciation model for describing our results suggests that we have resolved the diffusivity of hydroxyl in basaltic melt for the first time. Best-fit values of D^*_water for our experiments on lunar basalt vary within a factor of ~2 over a range of pH₂/pH₂O from 0.007 to 9.7, a range of fO₂ from IW-2.2 to IW+4.9, and a water concentration range from ~80 ppm to ~280 ppm. The relative insensitivity of our best-fit values of D^*_water to variations in pH₂ suggests that H₂ diffusion was not significant during degassing of the lunar glasses of Saal et al. (2008). D^*_water during dehydration and hydration in H₂/CO₂ gas mixtures are approximately the same, which supports an equilibrium boundary condition for these experiments. However, dehydration experiments into CO₂ and CO/CO₂ gas mixtures leave some scope for the importance of kinetics during dehydration into H-free environments. The value of D^*_water chosen by Saal et al. (2008) for modeling the diffusive degassing of the lunar volcanic glasses is within a factor of three of our measured value in our lunar basaltic melt at 1350 °C.

In Chapter 4 of this thesis, I document significant zonation in major, minor, trace, and volatile elements in naturally glassy olivine-hosted melt inclusions from the Siqueiros Fracture Zone and the Galapagos Islands. Components with a higher concentration in the host olivine than in the melt (MgO, FeO, Cr₂O₃, and MnO) are depleted at the edges of the zoned melt inclusions relative to their centers, whereas except for CaO, H₂O, and F, components with a lower concentration in the host olivine than in the melt (Al₂O₃, SiO₂, Na₂O, K₂O, TiO₂, S, and Cl) are enriched near the melt inclusion edges. This zonation is due to formation of an olivine-depleted boundary layer in the adjacent melt in response to cooling and crystallization of olivine on the walls of the melt inclusions concurrent with diffusive propagation of the boundary layer toward the inclusion center.

Concentration profiles of some components in the melt inclusions exhibit multicomponent diffusion effects such as uphill diffusion (CaO, FeO) or slowing of the diffusion of typically rapidly diffusing components (Na₂O, K₂O) by coupling to slow diffusing components such as SiO₂ and Al₂O₃. Concentrations of H2O and F decrease towards the edges of some of the Siqueiros melt inclusions, suggesting either that these components have been lost from the inclusions into the host olivine late in their cooling histories and/or that these components are exhibiting multicomponent diffusion effects.

A model has been developed of the time-dependent evolution of MgO concentration profiles in melt inclusions due to simultaneous depletion of MgO at the inclusion walls due to olivine growth and diffusion of MgO in the melt inclusions in response to this depletion. Observed concentration profiles were fit to this model to constrain their thermal histories. Cooling rates determined by a single-stage linear cooling model are 150–13,000 °C hr^-1 from the liquidus down to ~1000 °C, consistent with previously determined cooling rates for basaltic glasses; compositional trends with melt inclusion size observed in the Siqueiros melt inclusions are described well by this simple single-stage linear cooling model. Despite the overall success of the modeling of MgO concentration profiles using a single-stage cooling history, MgO concentration profiles in some melt inclusions are better fit by a two-stage cooling history with a slower-cooling first stage followed by a faster-cooling second stage; the inferred total duration of cooling from the liquidus down to ~1000 °C is 40 s to just over one hour.

Based on our observations and models, compositions of zoned melt inclusions (even if measured at the centers of the inclusions) will typically have been diffusively fractionated relative to the initially trapped melt; for such inclusions, the initial composition cannot be simply reconstructed based on olivine-addition calculations, so caution should be exercised in application of such reconstructions to correct for post-entrapment crystallization of olivine on inclusion walls. Off-center analyses of a melt inclusion can also give results significantly fractionated relative to simple olivine crystallization.

All melt inclusions from the Siqueiros and Galapagos sample suites exhibit zoning profiles, and this feature may be nearly universal in glassy, olivine-hosted inclusions. If so, zoning profiles in melt inclusions could be widely useful to constrain late-stage syneruptive processes and as natural diffusion experiments.

Dynamics of non-Abelian Aharonov-Bohm systems

This thesis examines several examples of systems in which non-Abelian magnetic flux and non-Abelian forms of the Aharonov-Bohm effect play a role. We consider the dynamical consequences in these systems of some of the exotic phenomena associated with non-Abelian flux, such as Cheshire charge holonomy interactions and non-Abelian braid statistics. First, we use a mean-field approximation to study a model of U(2) non-Abelian anyons near its free-fermion limit. Some self-consistent states are constructed which show a small SU(2)-breaking charge density that vanishes in the fermionic limit. This is contrasted with the bosonic limit where the SU(2) asymmetry of the ground state can be maximal. Second, a global analogue of Chesire charge is described, raising the possibility of observing Cheshire charge in condensedmatter systems. A potential realization in superfluid He-3 is discussed. Finally, we describe in some detail a method for numerically simulating the evolution of a network of non-Abelian (S₃) cosmic strings, keeping careful track of all magnetic fluxes and taking full account of their non-commutative nature. I present some preliminary results from this simulation, which is still in progress. The early results are suggestive of a qualitatively new, non-scaling behavior.