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.

Properties of superconducting CU-rich composites containing V_3SI or V_3GA

Superconducting Cu-rich composites containing the A-15 compounds V₃Si or V₃Ga have been made by the "Tsuei" process, which consists of melting the constituent elements into ingots followed by subsequent cold working and heat treatment. The superconducting transition temperatures of the resulting composites have been measured. X-ray diffraction analyses have been performed to identify the phases in the alloys. The microstructures have been studied using both the optical metallograph and the scanning electron-microscope. For some composites containing V₃Ga, the critical current densities as functions of transverse magnetic field up to 60 kG, and as functions of temperature from 4.2°K to 12°K have been measured. It was found that the Tsuei process does not work for the composites containing V₃Si, but works satisfactorily for the composites containing V₃Ga. The reasons are discussed based on the results of microstructure studies, electrical resistivity measurements, and also the relevant binary phase diagrams. The relations between the measured properties and the various metallurgical factors such as the alloy compositions, the cross-section reduction ratios of the materials, and the heat treatment are discussed. The basic mechanism for the observed superconductivity in the materials is also discussed. In addition, it was found that the Tsuei composites are expected to have high inherent magneto-thermal stability based on the stability theory of superconducting composites.

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.