The O'Nan-Scott Theorem classifies finite primitive permutation groups into one of five isomorphism classes. This theorem is very useful for answering questions about finite permutation groups since four out of the five isomorphism classes are well understood. The proof of this theorem currently relies upon the classification of the finite simple groups, as it requires a consequence of this classification, the Schreier Conjecture. After reviewing some needed group theoretic concepts, I give a detailed proof of the O'Nan-Scott Theorem. I then examine how the techniques of this proof have been applied to an open problem which asks whether every finite lattice can be embedded as an interval into the subgroup lattice of a finite group.

In the thesis, we study the rearrangeability of the Banyan-type network with crosstalk constraint. Let $x$, $p$ and $c$ be nonnegative integers with $0leq x,cleq n$ and $n,pgeq 1$. $B_{n}(x,p,c)$ is the Banyan-type network with, $2^{n+1}$ inputs, $2^{n+1}$ outputs, $x$ extra-stages, and each connection containing at most $c$ crosstalk switch elements. We give the necessary and sufficient conditions for rearrangeable Banyan-type networks $B_{n}(x,p,c)$.

A t-spanner of a graph G is a subgraph H of G, which the distance between any two vertices in H is at most t times their distance in G. A tree t-spanner of G is a t-spanner which is a tree. In this dissertation, we discuss the t-spanners on trapezoid, permutation, and interval graphs. We first introduce an O(n) algorithm for finding a tree 4-spanner on trapezoid graphs. Then, give an O(n)algorithm for finding a tree 3-spanner on permutation graphs, improving the existed O(n + m) algorithm. Since the class of permutation graphs is a subclass of trapezoid graphs, we can apply the algorithm on permutation graphs to find the approximation of a tree 3-spanner on trapezoid graphs in O(n) time with edge bound 2n. Finally, we show that not all interval graphs have a tree 2-spanner.

Markov chains are algorithms that can provide critical information from exponentially large sets efficiently through random sampling. These algorithms are ubiquitous across numerous scientific and engineering disciplines, including statistical physics, biology and operations research. In this thesis we solve sampling problems at the interface of theoretical computer science with applied computer science, discrete mathematics, statistical physics, chemistry and economics. A common theme throughout each of these problems is the use of bias. The first problem we study is biased permutations which arise in the context of self-organizing lists. Here we are interested in the mixing time of a Markov chain that performs nearest neighbor transpositions in the non-uniform setting. We are given "positively biased'' probabilities $\{p_{i,j} \geq 1/2 \}$ for all $i < j$ and let $p_{j,i} = 1-p_{i,j}$. In each step, the chain chooses two adjacent elements~$k,$ and~$\ell$ and exchanges their positions with probability $p_{ \ell, k}$. We define two general classes of bias and give the first proofs that the chain is rapidly mixing for both. We also demonstrate that the chain is not always rapidly mixing by constructing an example requiring exponential time to converge to equilibrium. Next we study rectangular dissections of an $n \times n$ lattice region into rectangles of area $n$, where $n=2^k$ for an even integer $k.$ We consider a weighted version of a natural edge flipping Markov chain where, given a parameter $\lambda > 0,$ we would like to generate each rectangular dissection (or dyadic tiling)~$\sigma$ with probability proportional to $\lambda^{|\sigma|},$ where $|\sigma|$ is the total edge length. First we look at the restricted case of dyadic tilings, where each rectangle is required to have the form $R = [s2^{u},(s+1)2^{u}]\times [t2^{v},(t+1)2^{v}],$ where $s, t, u$ and~$v$ are nonnegative integers. Here we show there is a phase transition: when $\lambda < 1,$ the edge-flipping chain mixes in time $O(n^2 \log n)$, and when $\lambda > 1,$ the mixing time is $\exp(\Omega({n^2}))$. The behavior for general rectangular dissections is more subtle, and we show the chain requires exponential time when $\lambda >1$ and when $\lambda <1.$ The last two problems we study arise directly from applications in chemistry and economics. Colloids are binary mixtures of molecules with one type of molecule suspended in another. It is believed that at low density typical configurations will be well-mixed throughout, while at high density they will separate into clusters. We characterize the high and low density phases for a general family of discrete interfering colloid models by showing that they exhibit a "clustering property" at high density and not at low density. The clustering property states that there will be a region that has very high area to perimeter ratio and very high density of one type of molecule. A special case is mixtures of squares and diamonds on $\Z^2$ which correspond to the Ising model at fixed magnetization. Subsequently, we expanded techniques developed in the context of colloids to give a new rigorous underpinning to the Schelling model, which was proposed in 1971 by economist Thomas Schelling to understand the causes of racial segregation. Schelling considered residents of two types, where everyone prefers that the majority of his or her neighbors are of the same type. He showed through simulations that even mild preferences of this type can lead to segregation if residents move whenever they are not happy with their local environments. We generalize the Schelling model to include a broad class of bias functions determining individuals happiness or desire to move. We show that for any influence function in this class, the dynamics will be rapidly mixing and cities will be integrated if the racial bias is sufficiently low. However when the bias is sufficiently high, we show the dynamics take exponential time to mix and a large cluster of one type will form.

Šiame darbe aš apibendrinau informaciją apie pasirinkimo tarp tiesinio prognozavimo mikro ir makro-modelių problemą. Agregavimas suprantamas kaip sektorinis agregavomas, o modeliai yra iš vienmatės tiesinės regresijos klasės. Aš išvedžiau kriterijų pasirinkimui tarp makro ir mikro-modelių ir idealaus agregavimo testą tiesinio agregavimo su fiksuotais ir atsitiktiniais svoriais atvejais. Paskutiniu atveju idealų agregavimą rekomenduoju tikrinti permutaciniu testu. Rezultatai iliustruoju ekonominiu pavyzdžiu. Modeliuoju Lietuvos vidutinį darbo užmokestį agreguotu modeliu ir atskirose ekonominės veiklos sektoriuose. Analizės rezultatas parodo, kad modeliai yra ekvivalentūs. / This paper focuses on the choice between macro and micro models. I suggest a hypothesis testing procedure for in-sample model selection for such variables as average wage. Empirical results show that Lithuanian average wage should be predict by using aggregate model.

No description available.

No abstract available. / Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 2002.

Discrete mathematics has had many applications in recent years and this is only one reason for its increasing dynamism. The study of finite structures is a broad area which has a unity not merely of description but also in practice, since many of the structures studied give results which can be applied to other, apparently dissimilar structures. Apart from the applications, which themselves generate problems, internally there are still many difficult and interesting problems in finite geometry and combinatorics. There are still many puzzling features about sub-structures of finite projective spaces, the minimum weight of the dual codes of polynomial codes, as well as about finite projective planes. Finite groups are an ever strong theme for several reasons. There is still much work to be done to give a clear geometric identification of the finite simple groups. There are also many problems in characterizing structures which either have a particular group acting on them or which have some degree of symmetry from a group action. Codes obtained from permutation representations of finite groups have been given particular attention in recent years. Given a representation of group elements of a group G by permutations we can work modulo 2 and obtain a representation of G on a vector space V over lF2 . The invariant subspaces (the subspaces of V taken into themselves by every group element) are then all the binary codes C for which G is a subgroup of Aut(C). Similar methods produce codes over arbitrary fields. Through a module-theoretic approach, and based on a study of monomial actions and projective representations, codes with given transitive permutation group were determined by various authors. Starting with well known simple groups and defining designs and codes through the primitive actions of the groups will give structures that have this group in their automorphism groups. For each of the primitive representations, we construct the permutation group and form the orbits of the stabilizer of a point. Taking these ideas further we have investigated the codes from the primitive permutation representations of the simple alternating and symplectic groups of odd characteristic in their natural rank-3 primitive actions. We have also investigated alternative ways of constructing these codes, and these have come about by noticing that the codes constructed from the primitive permutations of the groups could also be obtained from graphs. We achieved this by constructing codes from the span of adjacency matrices of graphs. In particular we have constructed codes from the triangular graphs and from the graphs on triples. The simple symplectic group PSp2m(q), where m is at least 2 and q is any prime power, acts as a primitive rank-3 group of degree q2m-1/q-1 on the points of the projective (2m-1)-space PG2m-1(IFq ). The codes obtained from the primitive rank-3 action of the simple projective symplectic groups PSp2m(Q), where Q= 2t with t an integer such that t ≥ 1, are the well known binary subcodes of the projective generalized Reed-Muller codes. However, by looking at the simple symplectic groups PSp2m(q), where q is a power of an odd prime and m ≥ 2, we observe that in their rank-3 action as primitive groups of degree q2m-1/q-1 these groups have 2-modular representations that give rise to self-orthogonal binary codes whose properties can be linked to those of the underlying geometry. We establish some properties of these codes, including bounds for the minimum weight and the nature of some classes of codewords. The knowledge of the structures of the automorphism groups has played a key role in the determination of explicit permutation decoding sets (PD-sets) for the binary codes obtained from the adjacency matrix of the triangular graph T(n) for n ≥ 5 and similarly from the adjacency matrices of the graphs on triples. The successful decoding came about by ordering the points in such a way that the nature of the information symbols was known and the action of the automorphism group apparent. Although the binary codes of the triangular graph T(n) were known, we have examined the codes and their duals further by looking at the question of minimum weight generators for the codes and for their duals. In this way we find bases of minimum weight codewords for such codes. We have also obtained explicit permutation-decoding sets for these codes. For a set Ω of size n and Ω{3} the set of subsets of Ω of size 3, we investigate the binary codes obtained from the adjacency matrix of each of the three graphs with vertex set Ω{3}1 with adjacency defined by two vertices as 3-sets being adjacent if they have zero, one or two elements in common, respectively. We show that permutation decoding can be used, by finding PD-sets, for some of the binary codes obtained from the adjacency matrix of the graphs on (n3) vertices, for n ≥ 7. / Thesis (Ph.D.)-University of Natal, Pietermaritzburg, 2002.

We investigate various methods for testing whether two groups of curves are statistically significantly different, with the motivation to apply the techniques to the analysis of data arising from designed experiments. We propose a set of tests based on pairwise differences between individual curves. Our objective is to compare the power and robustness of a variety of tests, including a collection of permutation tests, a test based on the functional principal components scores, the adaptive Neyman test and the functional F test. We illustrate the application of these tests in the context of a designed 2^4 factorial experiment with a case study using data provided by NASA. We apply the methods for comparing curves to this factorial data by dividing the data into two groups by each effect (A, B, . . . , ABCD) in turn. We carry out a large simulation study investigating the power of the tests in detecting contamination, location, and shift effects on unimodal and monotone curves. We conclude that the permutation test using the mean of the pairwise differences in L1 norm has the best overall power performance and is a robust test statistic applicable in a wide variety of situations. The advantage of using a permutation test is that it is an exact, distribution-free test that performs well overall when applied to functional data. This test may be extended to more than two groups by constructing test statistics based on averages of pairwise differences between curves from the different groups and, as such, is an important building-block for larger experiments and more complex designs.

No description available.