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.

Ancillary ligand effects : from zirconium(IV)-catalyzed homogeneous propylene polymerization to platinum(II)-mediated C-H bond activation

A series of C_s- and C₁-symmetric doubly-linked ansa-metallocenes of the general formula {1,1'-SiMe₂-2,2'-E-('ƞ⁵-C₅H₂-4-R¹)-(ƞ⁵-C₅H-3',5'-(CHMe₂)₂)}ZrC₂ (E = SiMe₂ (1), SiPh₂ (2), SiMe₂ -SiMe₂ (3); R¹ = H, CHMe₂, C₅H₉, C₆H₁₁, C₆H₅) has been prepared. When activated by methylaluminoxane, these are active propylene polymerization catalysts. 1 and 2 produce syndiotactic polypropylenes, and 3 produces isotactic polypropylenes. Site epimerization is the major pathway for stereoerror formation for 1 and 2. In addition, the polymer chain has slightly stronger steric interaction with the diphenylsilylene linker than with the dimethylsilylene linker. This results in more frequent site epimerization and reduced syndiospecificity for 2 compared to 1.

C₁-Symmetric ansa-zirconocenes [1,1 '-SiMe₂-(C₅H₄)-(3-R-C₅H₃)]ZrCl₂ (4), [1,1 '-SiMe₂-(C₅H₄)-(2,4-R₂-C₅H₂)]ZrCl₂ (5) and [1,1 '-SiMe₂-2,2 '-(SiMe₂-SiMe₂)-(C₅H₃)-( 4-R-C₅H₂)]ZrCl₂ (6) have been prepared to probe the origin of isospecificity in 3. While 4 and 3 produce polymers with similar isospecificity, 5 and 6 give mostly hemi-isotactic-like polymers. It is proposed that the facile site epimerization via an associative pathway allows rapid equilibration of the polymer chain between the isospecific and aspecific insertion sites. This results in more frequent insertion from the isospecific site, which has a lower kinetic barrier for chain propagation. On the other hand, site epimerization for 5 and 6 is slow. This leads to mostly alternating insertion from the isospecific and aspecific sites, and consequently, a hemi-isotactic-like polymers. In comparison, site epimerization is even slower for 3, but enchainment from the aspecific site has an extremely high kinetic barrier for monomer coordination. Therefore, enchainment occurs preferentially from the isospecific site to produce isotactic polymers.

A series of cationic complexes [(ArN=CR-CR=NAr)PtMe(L)]⁺[BF₄]⁺ (Ar = aryl; R = H, CH₃; L = water, trifluoroethanol) has been prepared. They react smoothly with benzene at approximately room temperature in trifluoroethanol solvent to yield methane and the corresponding phenyl Pt(II) cations, via Pt(IV)-methyl-phenyl-hydride intermediates. The reaction products of methyl-substituted benzenes suggest an inherent reactivity preference for aromatic over benzylic C-H bond activation, which can however be overridden by steric effects. For the reaction of benzene with cationic Pt(II) complexes, in which the diimine ligands bear 3,5-disubstituted aryl groups at the nitrogen atoms, the rate-determining step is C-H bond activation. For the more sterically crowded analogs with 2,6-dimethyl-substituted aryl groups, benzene coordination becomes rate-determining. The more electron-rich the ligand, as reflected by the CO stretching frequency in the IR spectrum of the corresponding cationic carbonyl complex, the faster the rate of C-H bond activation. This finding, however, does not reflect the actual C-H bond activation process, but rather reflects only the relative ease of solvent molecules displacing water molecules to initiate the reaction. That is, the change in rates is mostly due to a ground state effect. Several lines of evidence suggest that associative substitution pathways operate to get the hydrocarbon substrate into, and out of, the coordination sphere; i.e., that benzene substitution proceeds by a solvent- (TFE-) assisted associative pathway.

Imperfection Insensitive Thin Shells

The buckling of axially compressed cylindrical shells and externally pressurized spherical shells is extremely sensitive to even very small geometric imperfections. In practice this issue is addressed by either using overly conservative knockdown factors, while keeping perfect axial or spherical symmetry, or adding closely and equally spaced stiffeners on shell surface. The influence of imperfection-sensitivity is mitigated, but the shells designed from these approaches are either too heavy or very expensive and are still sensitive to imperfections. Despite their drawbacks, these approaches have been used for more than half a century.

This thesis proposes a novel method to design imperfection-insensitive cylindrical shells subject to axial compression. Instead of following the classical paths, focused on axially symmetric or high-order rotationally symmetric cross-sections, the method in this thesis adopts optimal symmetry-breaking wavy cross-sections (wavy shells). The avoidance of imperfection sensitivity is achieved by searching with an evolutionary algorithm for smooth cross-sectional shapes that maximize the minimum among the buckling loads of geometrically perfect and imperfect wavy shells. It is found that the shells designed through this approach can achieve higher critical stresses and knockdown factors than any previously known monocoque cylindrical shells. It is also found that these shells have superior mass efficiency to almost all previously reported stiffened shells.

Experimental studies on a design of composite wavy shell obtained through the proposed method are presented in this thesis. A method of making composite wavy shells and a photogrametry technique of measuring full-field geometric imperfections have been developed. Numerical predictions based on the measured geometric imperfections match remarkably well with the experiments. Experimental results confirm that the wavy shells are not sensitive to imperfections and can carry axial compression with superior mass efficiency.

An efficient computational method for the buckling analysis of corrugated and stiffened cylindrical shells subject to axial compression has been developed in this thesis. This method modifies the traditional Bloch wave method based on the stiffness matrix method of rotationally periodic structures. A highly efficient algorithm has been developed to implement the modified Bloch wave method. This method is applied in buckling analyses of a series of corrugated composite cylindrical shells and a large-scale orthogonally stiffened aluminum cylindrical shell. Numerical examples show that the modified Bloch wave method can achieve very high accuracy and require much less computational time than linear and nonlinear analyses of detailed full finite element models.

This thesis presents parametric studies on a series of externally pressurized pseudo-spherical shells, i.e., polyhedral shells, including icosahedron, geodesic shells, and triambic icosahedra. Several optimization methods have been developed to further improve the performance of pseudo-spherical shells under external pressure. It has been shown that the buckling pressures of the shell designs obtained from the optimizations are much higher than the spherical shells and not sensitive to imperfections.

Formulas, tables, and graphs for trapezoidal reinforced concrete beams

Not available.

Symmetric representation of an integral domain over a subdomain

Let F(θ) be a separable extension of degree n of a field F. Let Δ and D be integral domains with quotient fields F(θ) and F respectively. Assume that Δ ᴝ D. A mapping φ of Δ into the n x n D matrices is called a Δ/D rep if (i) it is a ring isomorphism and (ii) it maps d onto dI_n whenever d ϵ D. If the matrices are also symmetric, φ is a Δ/D symrep.

Every Δ/D rep can be extended uniquely to an F(θ)/F rep. This extension is completely determined by the image of θ. Two Δ/D reps are called equivalent if the images of θ differ by a D unimodular similarity. There is a one-to-one correspondence between classes of Δ/D reps and classes of Δ ideals having an n element basis over D.

The condition that a given Δ/D rep class contain a Δ/D symrep can be phrased in various ways. Using these formulations it is possible to (i) bound the number of symreps in a given class, (ii) count the number of symreps if F is finite, (iii) establish the existence of an F(θ)/F symrep when n is odd, F is an algebraic number field, and F(θ) is totally real if F is formally real (for n = 3 see Sapiro, “Characteristic polynomials of symmetric matrices” Sibirsk. Mat. Ž. 3 (1962) pp. 280-291), and (iv) study the case D = Z, the integers (see Taussky, “On matrix classes corresponding to an ideal and its inverse” Illinois J. Math. 1 (1957) pp. 108-113 and Faddeev, “On the characteristic equations of rational symmetric matrices” Dokl. Akad. Nauk SSSR 58 (1947) pp. 753-754).

The case D = Z and n = 2 is studied in detail. Let Δ’ be an integral domain also having quotient field F(θ) and such that Δ’ ᴝ Δ. Let φ be a Δ/Z symrep. A method is given for finding a Δ’/Z symrep ʘ such that the Δ’ ideal class corresponding to the class of ʘ is an extension to Δ’ of the Δ ideal class corresponding to the class of φ. The problem of finding all Δ/Z symreps equivalent to a given one is studied.

Regional variations in upper mantle structure beneath North America

Several types of seismological data, including surface wave group and phase velocities, travel times from large explosions, and teleseismic travel time anomalies, have indicated that there are significant regional variations in the upper few hundred kilometers of the mantle beneath continental areas. Body wave travel times and amplitudes from large chemical and nuclear explosions are used in this study to delineate the details of these variations beneath North America.

As a preliminary step in this study, theoretical P wave travel times, apparent velocities, and amplitudes have been calculated for a number of proposed upper mantle models, those of Gutenberg, Jeffreys, Lehman, and Lukk and Nersesov. These quantities have been calculated for both P and S waves for model CIT11GB, which is derived from surface wave dispersion data. First arrival times for all the models except that of Lukk and Nersesov are in close agreement, but the travel time curves for later arrivals are both qualitatively and quantitatively very different. For model CIT11GB, there are two large, overlapping regions of triplication of the travel time curve, produced by regions of rapid velocity increase near depths of 400 and 600 km. Throughout the distance range from 10 to 40 degrees, the later arrivals produced by these discontinuities have larger amplitudes than the first arrivals. The amplitudes of body waves, in fact, are extremely sensitive to small variations in the velocity structure, and provide a powerful tool for studying structural details.

Most of eastern North America, including the Canadian Shield has a Pn velocity of about 8.1 km/sec, with a nearly abrupt increase in compressional velocity by ~ 0.3 km/sec near at a depth varying regionally between 60 and 90 km. Variations in the structure of this part of the mantle are significant even within the Canadian Shield. The low-velocity zone is a minor feature in eastern North America and is subject to pronounced regional variations. It is 30 to 50 km thick, and occurs somewhere in the depth range from 80 to 160 km. The velocity decrease is less than 0.2 km/sec.

Consideration of the absolute amplitudes indicates that the attenuation due to anelasticity is negligible for 2 hz waves in the upper 200 km along the southeastern and southwestern margins of the Canadian Shield. For compressional waves the average Q for this region is > 3000. The amplitudes also indicate that the velocity gradient is at least 2 x 10^-3 both above and below the low-velocity zone, implying that the temperature gradient is < 4.8°C/km if the regions are chemically homogeneous.

In western North America, the low-velocity zone is a pronounced feature, extending to the base of the crust and having minimum velocities of 7.7 to 7.8 km/sec. Beneath the Colorado Plateau and Southern Rocky Mountains provinces, there is a rapid velocity increase of about 0.3 km/sec, similar to that observed in eastern North America, but near a depth of 100 km.

Complicated travel time curves observed on profiles with stations in both eastern and western North America can be explained in detail by a model taking into account the lateral variations in the structure of the low-velocity zone. These variations involve primarily the velocity within the zone and the depth to the top of the zone; the depth to the bottom is, for both regions, between 140 and 160 km.

The depth to the transition zone near 400 km also varies regionally, by about 30-40 km. These differences imply variations of 250 °C in the temperature or 6 % in the iron content of the mantle, if the phase transformation of olivine to the spinel structure is assumed responsible. The structural variations at this depth are not correlated with those at shallower depths, and follow no obvious simple pattern.

The computer programs used in this study are described in the Appendices. The program TTINV (Appendix IV) fits spherically symmetric earth models to observed travel time data. The method, described in Appendix III, resembles conventional least-square fitting, using partial derivatives of the travel time with respect to the model parameters to perturb an initial model. The usual ill-conditioned nature of least-squares techniques is avoided by a technique which minimizes both the travel time residuals and the model perturbations.

Spherically symmetric earth models, however, have been found inadequate to explain most of the observed travel times in this study. TVT4, a computer program that performs ray theory calculations for a laterally inhomogeneous earth model, is described in Appendix II. Appendix I gives a derivation of seismic ray theory for an arbitrarily inhomogeneous earth model.

High frequency wave propagation in the earth: theory and observation

The wave-theoretical analysis of acoustic and elastic waves refracted by a spherical boundary across which both velocity and density increase abruptly and thence either increase or decrease continuously with depth is formulated in terms of the general problem of waves generated at a steady point source and scattered by a radially heterogeneous spherical body. A displacement potential representation is used for the elastic problem that results in high frequency decoupling of P-SV motion in a spherically symmetric, radially heterogeneous medium. Through the application of an earth-flattening transformation on the radial solution and the Watson transform on the sum over eigenfunctions, the solution to the spherical problem for high frequencies is expressed as a Weyl integral for the corresponding half-space problem in which the effect of boundary curvature maps into an effective positive velocity gradient. The results of both analytical and numerical evaluation of this integral can be summarized as follows for body waves in the crust and upper mantle:

1) In the special case of a critical velocity gradient (a gradient equal and opposite to the effective curvature gradient), the critically refracted wave reduces to the classical head wave for flat, homogeneous layers.

2) For gradients more negative than critical, the amplitude of the critically refracted wave decays more rapidly with distance than the classical head wave.

3) For positive, null, and gradients less negative than critical, the amplitude of the critically refracted wave decays less rapidly with distance than the classical head wave, and at sufficiently large distances, the refracted wave can be adequately described in terms of ray-theoretical diving waves. At intermediate distances from the critical point, the spectral amplitude of the refracted wave is scalloped due to multiple diving wave interference.

These theoretical results applied to published amplitude data for P-waves refracted by the major crustal and upper mantle horizons (the Pg, P*, and Pn travel-time branches) suggest that the 'granitic' upper crust, the 'basaltic' lower crust, and the mantle lid all have negative or near-critical velocity gradients in the tectonically active western United States. On the other hand, the corresponding horizons in the stable eastern United States appear to have null or slightly positive velocity gradients. The distribution of negative and positive velocity gradients correlates closely with high heat flow in tectonic regions and normal heat flow in stable regions. The velocity gradients inferred from the amplitude data are generally consistent with those inferred from ultrasonic measurements of the effects of temperature and pressure on crustal and mantle rocks and probable geothermal gradients. A notable exception is the strong positive velocity gradient in the mantle lid beneath the eastern United States (2 x 10^-3 sec^-1), which appears to require a compositional gradient to counter the effect of even a small geothermal gradient.

New seismic-refraction data were recorded along a 800 km profile extending due south from the Canadian border across the Columbia Plateau into eastern Oregon. The source for the seismic waves was a series of 20 high-energy chemical explosions detonated by the Canadian government in Greenbush Lake, British Columbia. The first arrivals recorded along this profile are on the Pn travel-time branch. In northern Washington and central Oregon their travel time is described by T = Δ/8.0 + 7.7 sec, but in the Columbia Plateau the Pn arrivals are as much as 0.9 sec early with respect to this line. An interpretation of these Pn arrivals together with later crustal arrivals suggest that the crust under the Columbia Plateau is thinner by about 10 km and has a higher average P-wave velocity than the 35-km-thick, 62-km/sec crust under the granitic-metamorphic terrain of northern Washington. A tentative interpretation of later arrivals recorded beyond 500 km from the shots suggests that a thin 8.4-km/sec horizon may be present in the upper mantle beneath the Columbia Plateau and that this horizon may form the lid to a pronounced low-velocity zone extending to a depth of about 140 km.

Studies on T-even bacteriophage DNA

Part I. The regions of sequence homology and non-homology between the DNA molecules of T2, T4, and T6 have been mapped by the electron microscopic heteroduplex method. The heteroduplex maps have been oriented with respect to the T4 genetic map. They show characteristic, reproducible patterns of substitution and deletion loops. All heteroduplex molecules show more than 85% homology. Some of the loop patterns in T2/T4 heteroduplexes are similar to those in T4/T6.

We find that the rII, the lysozyme and ac genes, the D region, and gene 52 are homologous in T2, T4, and T6. Genes 43 and 47 are probably homologous between T2 and T4. The region of greatest homology is that bearing the late genes. The host range region, which comprises a part of gene 37 and all of gene 38, is heterologous in T2, T4, and T6. The remainder of gene 37 is partially homologous in the T2/T4 heteroduplex (Beckendorf, Kim and Lielausis, 1972) but it is heterologous in T4/T6 and in T2/T6. Some of the tRNA genes are homologous and some are not. The internal protein genes in general seem to be non-homologous.

The molecular lengths of the T-even DNAs are the same within the limit of experimental error; their calculated molecular weights are correspondingly different due to unequal glucosylation. The size of the T2 genome is smaller than that of T4 or T6, but the terminally repetitious region in T2 is larger. There is a length distribution of the terminal repetition for any one phage DNA, indicating a variability in length of the DNA molecules packaged within the phage.

Part II. E. coli cells infected with phage strains carrying extensive deletions encompassing the gene for the phage ser-tRNA are missing the phage tRNAs normally present in wild type infected cells. By DNA-RNA hybridization we have demonstrated that the DNA complementary to the missing tRNAs is also absent in such deletion mutants. Thus the genes for these tRNAs must be clustered in the same region of the genome as the ser-tRNA gene. Physical mapping of several deletions of the ser-tRNA and lysozyme genes, by examination of heteroduplex DNA in the electron microscope, has enabled us to locate the cluster, to define its maximum size, and to order a few of the tRNA genes within it. That such deletions can be isolated indicates that the phage-specific tRNAs from this cluster are dispensable.

Part III. Genes 37 and 38 between closely related phages T2 and T4 have been compared by genetic, biochemical, and hetero-duplex studies. Homologous, partially homologous and non-homologous regions of the gene 37 have been mapped. The host range determinant which interacts with the gene 38 product is identified.

Part IV. A population of double-stranded ØX-RF DNA molecules carrying a deletion of about 9% of the wild-type DNA has been discovered in a sample cultivated under conditions where the phage lysozyme gene is nonessential. The structures of deleted monomers, dimers, and trimers have been studied by the electron microscope heteroduplex method. The dimers and trimers are shown to be head-to-tail repeats of the deleted monomers. Some interesting examples of the dynamical phenomenon of branch migration in vitro have been observed in heteroduplexes of deleted dimer and trimer strands with undeleted wild-type monomer viral strands.