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.

Investigations of DNA-mediated protein oxidation

DNA charge transport (CT) involves the efficient transfer of electrons or electron holes through the DNA π-stack over long molecular distances of at least 100 base-pairs. Despite this shallow distance dependence, DNA CT is sensitive to mismatches or lesions that disrupt π-stacking and is critically dependent on proper electronic coupling of the donor and acceptor moieties into the base stack. Favorable DNA CT is very rapid, occurring on the picosecond timescale. Because of this speed, electron holes equilibrate along the DNA π-stack, forming a characteristic pattern of DNA damage at low oxidation potential guanine multiplets. Furthermore, DNA CT may be used in a biological context. DNA processing enzymes with 4Fe4S clusters can perform DNA-mediated electron transfer (ET) self-exchange reactions with other 4Fe4S cluster proteins, even if the proteins are quite dissimilar, as long as the DNA-bound [4Fe4S]^3+/2+ redox potentials are conserved. This mechanism would allow low copy number DNA repair proteins to find their lesions efficiently within the cell. DNA CT may also be used biologically for the long-range, selective activation of redox-active transcription factors. Within this work, we pursue other proteins that may utilize DNA CT within the cell and further elucidate aspects of the DNA-mediated ET self-exchange reaction of 4Fe4S cluster proteins.

Dps proteins, bacterial mini-ferritins that protect DNA from oxidative stress, are implicated in the survival and virulence of pathogenic bacteria. One aspect of their protection involves ferroxidase activity, whereby ferrous iron is bound and oxidized selectively by hydrogen peroxide, thereby preventing formation of damaging hydroxyl radicals via Fenton chemistry. Understanding the specific mechanism by which Dps proteins protect the bacterial genome could inform the development of new antibiotics. We investigate whether DNA-binding E. coli Dps can utilize DNA CT to protect the genome from a distance. An intercalating ruthenium photooxidant was employed to generate oxidative DNA damage via the flash-quench technique, which localizes to a low potential guanine triplet. We find that Dps loaded with ferrous iron, in contrast to Apo-Dps and ferric iron-loaded Dps which lack available reducing equivalents, significantly attenuates the yield of oxidative DNA damage at the guanine triplet. These data demonstrate that ferrous iron-loaded Dps is selectively oxidized to fill guanine radical holes, thereby restoring the integrity of the DNA. Luminescence studies indicate no direct interaction between the ruthenium photooxidant and Dps, supporting the DNA-mediated oxidation of ferrous iron-loaded Dps. Thus DNA CT may be a mechanism by which Dps efficiently protects the genome of pathogenic bacteria from a distance.

Further work focused on spectroscopic characterization of the DNA-mediated oxidation of ferrous iron-loaded Dps. X-band EPR was used to monitor the oxidation of DNA-bound Dps after DNA photooxidation via the flash-quench technique. Upon irradiation with poly(dGdC)₂, a signal arises with g = 4.3, consistent with the formation of mononuclear high-spin Fe(III) sites of low symmetry, the expected oxidation product of Dps with one iron bound at each ferroxidase site. When poly(dGdC)₂ is substituted with poly(dAdT)₂, the yield of Dps oxidation is decreased significantly, indicating that guanine radicals facilitate Dps oxidation. The more favorable oxidation of Dps by guanine radicals supports the feasibility of a long-distance protection mechanism via DNA CT where Dps is oxidized to fill guanine radical holes in the bacterial genome produced by reactive oxygen species.

We have also explored possible electron transfer intermediates in the DNA-mediated oxidation of ferrous iron-loaded Dps. Dps proteins contain a conserved tryptophan residue in close proximity to the ferroxidase site (W52 in E. coli Dps). In comparison to WT Dps, in EPR studies of the oxidation of ferrous iron-loaded Dps following DNA photooxidation, W52Y and W52A mutants were deficient in forming the characteristic EPR signal at g = 4.3, with a larger deficiency for W52A compared to W52Y. In addition to EPR, we also probed the role of W52 Dps in cells using a hydrogen peroxide survival assay. Bacteria containing W52Y Dps survived the hydrogen peroxide challenge more similarly to those containing WT Dps, whereas cells with W52A Dps died off as quickly as cells without Dps. Overall, these results suggest the possibility of W52 as a CT hopping intermediate.

DNA-modified electrodes have become an essential tool for the study of the redox chemistry of DNA processing enzymes with 4Fe4S clusters. In many cases, it is necessary to investigate different complex samples and substrates in parallel in order to elucidate this chemistry. Therefore, we optimized and characterized a multiplexed electrochemical platform with the 4Fe4S cluster base excision repair glycosylase Endonuclease III (EndoIII). Closely packed DNA films, where the protein has limited surface accessibility, produce EndoIII electrochemical signals sensitive to an intervening mismatch, indicating a DNA-mediated process. Multiplexed analysis allowed more robust characterization of the CT-deficient Y82A EndoIII mutant, as well as comparison of a new family of mutations altering the electrostatics surrounding the 4Fe4S cluster in an effort to shift the reduction potential of the cluster. While little change in the DNA-bound midpoint potential was found for this family of mutants, likely indicating the dominant effect of DNA-binding on establishing the protein redox potential, significant variations in the efficiency of DNA-mediated electron transfer were apparent. On the basis of the stability of these proteins, examined by circular dichroism, we proposed that the electron transfer pathway in EndoIII can be perturbed not only by the removal of aromatic residues but also through changes in solvation near the cluster.

While the 4Fe4S cluster of EndoIII is relatively insensitive to oxidation and reduction in solution, we have found that upon DNA binding, the reduction potential of the [4Fe4S]^3+/2+ couple shifts negatively by approximately 200 mV, bringing this couple into a physiologically relevant range. Demonstrated using electrochemistry experiments in the presence and absence of DNA, these studies do not provide direct molecular evidence for the species being observed. Sulfur K-edge X-ray absorbance spectroscopy (XAS) can be used to probe directly the covalency of iron-sulfur clusters, which is correlated to their reduction potential. We have shown that the Fe-S covalency of the 4Fe4S cluster of EndoIII increases upon DNA binding, stabilizing the oxidized [4Fe4S]³⁺ cluster, consistent with a negative shift in reduction potential. The 7% increase in Fe-S covalency corresponds to an approximately 150 mV shift, remarkably similar to DNA electrochemistry results. Therefore we have obtained direct molecular evidence for the shift in 4Fe4S reduction potential of EndoIII upon DNA binding, supporting the feasibility of our model whereby these proteins can utilize DNA CT to cooperate in order to efficiently find DNA lesions inside cells.

In conclusion, in this work we have explored the biological applications of DNA CT. We discovered that the DNA-binding bacterial ferritin Dps can protect the bacterial genome from a distance via DNA CT, perhaps contributing to pathogen survival and virulence. Furthermore, we optimized a multiplexed electrochemical platform for the study of the redox chemistry of DNA-bound 4Fe4S cluster proteins. Finally, we have used sulfur K-edge XAS to obtain direct molecular evidence for the negative shift in 4Fe4S cluster reduction potential of EndoIII upon DNA binding. These studies contribute to the understanding of DNA-mediated protein oxidation within cells.

I. Reactively sputtered Ti-Si-N thin films for diffusion barrier applications. II. Oxidation, diffusion and crystallization of an amorphous Zr_(60)Al_(15)Ni_(25) alloy.

Films of Ti-Si-N obtained by reactively sputtering a TiSi_2, a Ti_5Si_3, or a Ti_3Si target are either amorphous or nanocrystalline in structure. The atomic density of some films exceeds 10^23 at./cm^3. The room-temperature resistivity of the films increases with the Si and the N content. A thermal treatment in vacuum at 700 °C for 1 hour decreases the resistivity of the Ti-rich films deposited from the Ti_5Si_3 or the Ti_3Si target, but increases that of the Si-rich films deposited from the TiSi_2 target when the nitrogen content exceeds about 30 at. %.

Ti_(34)Si_(23)N_(43) deposited from the Ti_5Si_3 target is an excellent diffusion barrier between Si and Cu. This film is a mixture of nanocrystalline TiN and amorphous SiN_x. Resistivity measurement from 80 K to 1073 K reveals that this film is electrically semiconductor-like as-deposited, and that it becomes metal-like after an hour annealing at 1000 °C in vacuum. A film of about 100 nm thick, with a resistivity of 660 µΩcm, maintains the stability of Si n+p shallow junction diodes with a 400 nm Cu overlayer up to 850 °C upon 30 min vacuum annealing. When used between Si and Al, the maximum temperature of stability is 550 °C for 30 min. This film can be etched in a CF_4/O_2 plasma.

The amorphous ternary metallic alloy Zr_(60)Al_(15)Ni_(25) was oxidized in dry oxygen in the temperature range 310 °C to 410 °C. Rutherford backscattering and cross-sectional transmission electron microscopy studies suggest that during this treatment an amorphous layer of zirconium-aluminum-oxide is formed at the surface. Nickel is depleted from the oxide and enriched in the amorphous alloy below the oxide/alloy interface. The oxide layer thickness grows parabolically with the annealing duration, with a transport constant of 2.8x10^(-5) m^2/s x exp(-1.7 eV/kT). The oxidation rate is most likely controlled by the Ni diffusion in the amorphous alloy.

At later stages of the oxidation process, precipitates of nanocrystalline ZrO_2 appear in the oxide near the interface. Finally, two intermetallic phases nucleate and grow simultaneously in the alloy, one at the interface and one within the alloy.

Band Engineering in Thermoelectric Materials Using Optical, Electronic, and Ab-Initio Computed Properties

Thermoelectric materials have demanded a significant amount of attention for their ability to convert waste heat directly to electricity with no moving parts. A resurgence in thermoelectrics research has led to significant enhancements in the thermoelectric figure of merit, zT, even for materials that were already well studied. This thesis approaches thermoelectric zT optimization by developing a detailed understanding of the electronic structure using a combination of electronic/thermoelectric properties, optical properties, and ab-initio computed electronic band structures. This is accomplished by applying these techniques to three important classes of thermoelectric materials: IV-VI materials (the lead chalcogenides), Half-Heusler’s (XNiSn where X=Zr, Ti, Hf), and CoSb₃ skutterudites.

In the IV-VI materials (PbTe, PbSe, PbS) I present a shifting temperature-dependent optical absorption edge which correlates well to the computed ab-initio molecular dynamics result. Contrary to prior literature that suggests convergence of the primary and secondary bands at 400 K, I suggest a higher convergence temperature of 700, 900, and 1000 K for PbTe, PbSe, and PbS, respectively. This finding can help guide electronic properties modelling by providing a concrete value for the band gap and valence band offset as a function of temperature.

Another important thermoelectric material, ZrNiSn (half-Heusler), is analyzed for both its optical and electronic properties; transport properties indicate a largely different band gap depending on whether the material is doped n-type or p-type. By measuring and reporting the optical band gap value of 0.13 eV, I resolve the discrepancy in the gap calculated from electronic properties (maximum Seebeck and resistivity) by correlating these estimates to the electron-to-hole weighted mobility ratio, A, in narrow gap materials (A is found to be approximately 5.0 in ZrNiSn).

I also show that CoSb₃ contains multiple conduction bands that contribute to the thermoelectric properties. These bands are also observed to shift towards each other with temperature, eventually reaching effective convergence for T>500 K. This implies that the electronic structure in CoSb₃ is critically important (and possibly engineerable) with regards to its high thermoelectric figure of merit.

Electron microprobe investigations of metamorphic reactions and mineral growth histories, Kwoiek area, British Columbia

The Kwoiek Area of British Columbia contains a pendant or screen of metamorphosed sedimentary and volcanic rocks almost entirely surrounded by a portion of the Coast Range Batholith, and intruded by several dozen stocks. The major metamorphic effects were produced by the quartz diorite batholithic rocks, with minor and later effects by the quartz diorite stocks. The sequence of important metamorphic reactions in the metasedimentary and metavolcanic rocks, ranging in grade from chlorite to sillimanite, is:

1. chlorite + carbonate + muscovite → epidote + biotite

2. chlorite + carbonate → actinolite + epidote

3. chlorite + muscovite → garnet + biotite

4. chlorite + epidote → garnet + hornblende

5. chlorite + muscovite → garnet + staurolite + biotite

6. chlorite + muscovite → aluminum silicate + biotite

7. muscovite + staurolite → garnet + aluminum silicate + biotite

8. staurolite → garnet + aluminum silicate

Continuous reactions, occurring between reactions 5 and 7, are:

A. chlorite + (high Ti) biotite + Al₂O₃ (from plagioclase?)→ garnet + staurolite + (low Ti) biotite + O₂

B. muscovite (phengitic) → garnet + staurolite +muscovite (less phengitic) + O₂ (?)

Detailed electron microprobe work on garnet, staurolite, biotite, and chlorite shows that:

(1) The garnet porphyroblasts are zoned according to a depletion model, called the Rayleigh depletion model, which assumes equilibrium between the edge of a growing garnet and the minerals which are unzoned, notably biotite, chlorite, and muscovite, but which assumes disequilibrium within the garnet.

(2) The staurolite porphyroblasts are also zoned, and from their zoning patterns reactions A, B, and 5 are documented. Progressive reduction of iron with increasing grade of metamorphism is also inferred from the staurolite zoning patterns.

(3) During a late period of falling temperature garnet continued to grow and the biotite and chlorite reequilibrated. The biotite, chlorite, and garnet edge compositions can vary from point to point in a given thin section, indicating that the volume of equilibrium at the final stage of metamorphism was only a few cubic microns.

(4) The horizon within the garnet that grew at maximum temperature can be identified. The Mg/Fe ratio of this horizon, if the garnet composition is a limiting composition in the Al₂O₃ - K₂O - FeO - MgO tetrahedron, increases systematically with increasing metamorphic grade. Biotite and chlorite compositions also show a general increase in Mg/Fe ratio with increasing metamorphic grade, but staurolite appears to show the reverse effect.

(5) The Mg/Fe ratio at the maximum temperature horizon of the garnet porphyroblasts is a function of its Mn content as evidenced from the study of five garnet-bearing rocks, collected from one outcrop area, with the same assemblage but with differing proportions of minerals.

An important implication of zoned minerals is that the effective composition of a system in a phase lies on the join between the homogeneous minerals (if there are two) and not within three-or- four-phase fields when a zoned mineral, such as garnet or staurolite, is present in the assemblage.

Study of the three aluminum silicates found in the Kwoiek Area showed that a constant pressure change in polymorphs from andalusite to kyanite to sillimanite took place with increasing temperature. This transition series is best explained by the metastable formation of andalusite.

Photographic materials on pages 15, 121, 160, 162, and 164 are essential and will not reproduce clearly on Xerox copies. Photographic copies should be ordered.