1 |
Orthogonality of Latin squares defined by abelian groupsTsai, Shu-Hui 17 July 2008 (has links)
Let G = {g1, ¡K,gn} be a finite abelian group, and let LG = [gij ] be the Latin square defined by gij = gi + gj. Denote by k(G) the largest number of mutually orthogonal system containing LG. In 1948, Paige
showed that if the Sylow 2-subgroup of G is not cyclic, then LG has a transversal. In this paper, we give an constructive proof for this theorem and give some upper bound and lower bound for the number k(G).
|
2 |
An Asymptotic Existence Theory on Incomplete Mutually Orthogonal Latin Squaresvan Bommel, Christopher Martin 23 March 2015 (has links)
An incomplete Latin square is a v x v array with an empty n x n subarray with every row and every column containing each symbol at most once and no row or column with an empty cell containing one of the last n symbols. A set of t incomplete mutually orthogonal Latin squares of order v and hole size n is a set of t incomplete Latin squares (containing the same empty subarray on the same set of symbols) with a natural extension to the condition of orthogonality. The existence of such sets have been previously explored only for small values of t. We determine an asymptotic result for the existence of t incomplete mutually orthogonal Latin squares for general t requiring large holes, which we develop from our results on incomplete pairwise balanced designs and incomplete group divisible designs. / Graduate
|
3 |
Completing partial Latin squares with one filled row, column and symbolCasselgren, Carl Johan, Häggkvist, Roland January 2013 (has links)
Let P be an n×n partial Latin square every non-empty cell of which lies in a fixed row r, a fixed column c or contains a fixed symbol s. Assume further that s is the symbol of cell (r,c) in P. We prove that P is completable to a Latin square if n≥8 and n is divisible by 4, or n≤7 and n∉{3,4,5}. Moreover, we present a polynomial algorithm for the completion of such a partial Latin square.
|
4 |
On Latin squares and avoidable arraysAndrén, Lina J. January 2010 (has links)
This thesis consists of the four papers listed below and a survey of the research area. I Lina J. Andrén: Avoiding (m, m, m)-arrays of order n = 2k II Lina J. Andrén: Avoidability of random arrays III Lina J. Andr´en: Avoidability by Latin squares of arrays with even order IV Lina J. Andrén, Carl Johan Casselgren and Lars-Daniel Öhman: Avoiding arrays of odd order by Latin squares Papers I, III and IV are all concerned with a conjecture by Häggkvist saying that there is a constant c such that for any positive integer n, if m ≤ cn, then for every n × n array A of subsets of {1, . . . , n} such that no cell contains a set of size greater than m, and none of the elements 1, . . . , n belongs to more than m of the sets in any row or any column of A, there is a Latin square L on the symbols 1, . . . , n such that there is no cell in L that contains a symbol that belongs to the set in the corresponding cell of A. Such a Latin square is said to avoid A. In Paper I, the conjecture is proved in the special case of order n = 2k . Paper III improves on the techniques of Paper I, expanding the proof to cover all arrays of even order. Finally, in Paper IV, similar methods are used together with a recoloring theorem to prove the conjecture for all orders. Paper II considers another aspect of the problem by asking to what extent way a deterministic result concerning the existence of Latin squares that avoid certain arrays can be used when the sets in the array are assigned randomly. / Denna avhandling inehåller de fyra nedan uppräknade artiklarna, samt en översikt av forskningsområdet. I Lina J. Andrén: Avoiding (m, m, m)-arrays of order n = 2k II Lina J. Andrén: Avoidability of random arrays III Lina J. Andrén: Avoidability by Latin squares of arrays with even order IV Lina J. Andrén, Carl Johan Casselgren and Lars-Daniel Öhman: Avoiding arrays of odd order by Latin squares Artikel I, III och IV behandlar en förmodan av Häggkvist, som säger att det finns en konstant c sådan att för varje positivt heltal n gäller att om m ≤ cn så finns för varje n × n array A av delmängder till {1, . . . ,n} sådan att ingen cell i A i innehåller fler än m symboler, och ingen symbol förekommer i fler än m celler i någon av raderna eller kolumnerna, så finns en latinsk kvadrat L sådan att ingen cell i L innehåller en symbol som förekommer i motsvarande cell i A. En sådan latinsk kvadrat sägs undvika A. Artikel I innehåller ett bevis av förmodan i specialfallet n = 2k. Artikel III använder och utökar metoderna i Artikel I till ett bevis av förmodan för alla latinska kvadrater av jämn ordning. Förmodan visas slutligen för samtliga ordningar i Artikel IV, där bevismetoden liknar den som finns i i Artikel I och III tillsammans med en omfärgningssats. Artikel II behandlar en annan aspekt av problemet genom att undersöka vad ett deterministiskt resultat om existens av latinska kvadrater som undviker en viss typ av array säger om arrayer där mängderna tilldelas slumpmässigt.
|
5 |
Error Structure of Randomized Design Under Background Correlation with a Missing ValueChang, Tseng-Chi 01 May 1965 (has links)
The analysis of variance technique is probably the most popular statistical technique used for testing hypotheses and estimating parameters. Eisenhart presents two classes of problems solvable by the analysis of variance and the assumption underlying each class. Cochran lists the assumptions and also discusses the consequences when these assumptions are not met. It is evident that if all the assumptions are not satisfied, the confidence placed in any result obtained in this manner is adversely affected to varying degrees according to the extent of the violation. One of the assumptions in the analysis of variance procedures is that of uncorrelated errors. The experimenter may not always meet this conditions because of economical or environmental reasons. In fact, Wilk questions the validity of the assumption of uncorrelated errors in any physical situation. For example, consider an experiment over a sequence of years. A correlation due to years may exist, no matter what randomization technique is used, because the outcome of the previous year determines to a great extent the outcome of this year. Another example would be the case of selecting experimental units from the same source, such as, sampling students with the same background or selecting units from the same production process. This points out the fact that the condition such as background, or a defect in the production process may have forced a correlation among the experimental units. Problems of this nature frequently occur in Industrial, Biological, and Psychological experiments.
|
6 |
Using Latin Square Design To Evaluate Model Interpolation And Adaptation Based Emotional Speech SynthesisHsu, Chih-Yu 19 July 2012 (has links)
¡@¡@In this thesis, we use a hidden Markov model which can use a small amount of corpus to synthesize speech with certain quality to implement speech synthesis system for Chinese. More, the emotional speech are synthesized by the flexibility of the parametric speech in this model. We conduct model interpolation and model adaptation to synthesize speech from neutral to particular emotion without target speaker¡¦s emotional speech. In model adaptation, we use monophone-based Mahalanobis distance to select emotional models which are close to target speaker from pool of speakers, and estimate the interpolation weight to synthesize emotional
speech. In model adaptation, we collect abundant of data training average voice models for each individual emotion. These models are adapted to specific emotional models of target speaker by CMLLR method. In addition, we design the Latin-square evaluation to reduce the systematic offset in the subjective tests, making results more credible and fair. We synthesize emotional speech include happiness, anger, sadness, and use Latin square design to evaluate performance in three part similarity, naturalness, and emotional expression respectively. According to result, we make a comprehensive comparison and conclusions of two method in emotional speech synthesis.
|
7 |
Power Graphs of QuasigroupsWalker, DayVon L. 26 June 2019 (has links)
We investigate power graphs of quasigroups. The power graph of a quasigroup takes the elements of the quasigroup as its vertices, and there is an edge from one element to a second distinct element when the second is a left power of the first. We first compute the power graphs of small quasigroups (up to four elements). Next we describe quasigroups whose power graphs are directed paths, directed cycles, in-stars, out-stars, and empty. We do so by specifying partial Cayley tables, which cannot always be completed in small examples. We then consider sinks in the power graph of a quasigroup, as subquasigroups give rise to sinks. We show that certain structures cannot occur as sinks in the power graph of a quasigroup. More generally, we show that certain highly connected substructures must have edges leading out of the substructure. We briefly comment on power graphs of Bol loops.
|
8 |
On the existence and enumeration of sets of two or three mutually orthogonal Latin squares with application to sports tournament schedulingKidd, Martin Philip 03 1900 (has links)
Thesis (PdD)--Stellenbosch University, 2012. / ENGLISH ABSTRACT: A Latin square of order n is an n×n array containing an arrangement of n distinct symbols with
the property that every row and every column of the array contains each symbol exactly once.
It is well known that Latin squares may be used for the purpose of constructing designs which
require a balanced arrangement of a set of elements subject to a number of strict constraints.
An important application of Latin squares arises in the scheduling of various types of balanced
sports tournaments, the simplest example of which is a so-called round-robin tournament — a
tournament in which each team opposes each other team exactly once.
Among the various applications of Latin squares to sports tournament scheduling, the problem
of scheduling special types of mixed doubles tennis and table tennis tournaments using special
sets of three mutually orthogonal Latin squares is of particular interest in this dissertation. A
so-called mixed doubles table tennis (MDTT) tournament comprises two teams, both consisting
of men and women, competing in a mixed doubles round-robin fashion, and it is known that
any set of three mutually orthogonal Latin squares may be used to obtain a schedule for such
a tournament. A more interesting sports tournament design, however, and one that has been
sought by sports clubs in at least two reported cases, is known as a spouse-avoiding mixed
doubles round-robin (SAMDRR) tournament, and it is known that such a tournament may be
scheduled using a self-orthogonal Latin square with a symmetric orthogonal mate (SOLSSOM).
These applications have given rise to a number of important unsolved problems in the theory
of Latin squares, the most celebrated of which is the question of whether or not a set of three
mutually orthogonal Latin squares of order 10 exists. Another open question is whether or not
SOLSSOMs of orders 10 and 14 exist. A further problem in the theory of Latin squares that
has received considerable attention in the literature is the problem of counting the number of
(essentially) different ways in which a set of elements may be arranged to form a Latin square,
i.e. the problem of enumerating Latin squares and equivalence classes of Latin squares of a given
order. This problem quickly becomes extremely difficult as the order of the Latin square grows,
and considerable computational power is often required for this purpose. In the literature on
Latin squares only a small number of equivalence classes of self-orthogonal Latin squares (SOLS)
have been enumerated, namely the number of distinct SOLS, the number of idempotent SOLS
and the number of isomorphism classes generated by idempotent SOLS of orders 4 n 9.
Furthermore, only a small number of equivalence classes of ordered sets of k mutually orthogonal
Latin squares (k-MOLS) of order n have been enumerated in the literature, namely main classes
of 2-MOLS of order n for 3 n 8 and isotopy classes of 8-MOLS of order 9. No enumeration
work on SOLSSOMs appears in the literature.
In this dissertation a methodology is presented for enumerating equivalence classes of Latin
squares using a recursive, backtracking tree-search approach which attempts to eliminate redundancy
in the search by only considering structures which have the potential to be completed
to well-defined class representatives. This approach ensures that the enumeration algorithm only generates one Latin square from each of the classes to be enumerated, thus also generating
a repository of class representatives of these classes. These class representatives may be used in
conjunction with various well-known enumeration results from the theory of groups and group
actions in order to determine the number of Latin squares in each class as well as the numbers
of various kinds of subclasses of each class.
This methodology is applied in order to enumerate various equivalence classes of SOLS and
SOLSSOMs of orders up to and including order 10 and various equivalence classes of k-MOLS
of orders up to and including order 8. The known numbers of distinct SOLS, idempotent SOLS
and isomorphism classes generated by idempotent SOLS are verified for orders 4 n 9, and in
addition the number of isomorphism classes, transpose-isomorphism classes and RC-paratopism
classes of SOLS of these orders are enumerated. The search is further extended to determine the
numbers of these classes for SOLS of order 10 via a large parallelisation of the backtracking treesearch
algorithm on a number of processors. The RC-paratopism class representatives of SOLS
thus generated are then utilised for the purpose of enumerating SOLSSOMs, while existing
repositories of symmetric Latin squares are also used for this purpose as a means of validating
the enumeration results. In this way distinct SOLSSOMs, standard SOLSSOMs, transposeisomorphism
classes of SOLSSOMs and RC-paratopism classes of SOLSSOMs are enumerated,
and a repository of RC-paratopism class representatives of SOLSSOMs is also produced. The
known number of main classes of 2-MOLS of orders 3 n 8 are verified in this dissertation,
and in addition the number of main classes of k-MOLS of orders 3 n 8 are also determined
for 3 k n−1. Other equivalence classes of k-MOLS of order n that are enumerated include
distinct k-MOLS and reduced k-MOLS of orders 3 n 8 for 2 k n − 1.
Finally, a filtering method is employed to verify whether any SOLS of order 10 satisfies two
basic necessary conditions for admitting a common orthogonal mate with its transpose, and it is
found via a computer search that only four of the 121 642 class representatives of RC-paratopism
classes of SOLS satisfy these conditions. It is further verified that none of these four SOLS
admits a common orthogonal mate with its transpose. By this method the spectrum of resolved
orders in terms of the existence of SOLSSOMs is improved in that the non-existence of such
designs of order 10 is established, thereby resolving a longstanding open existence question in
the theory of Latin squares. Furthermore, this result establishes a new necessary condition for
the existence of a set of three mutually orthogonal Latin squares of order 10, namely that such
a set cannot contain a SOLS and its transpose / AFRIKAANSE OPSOMMING: ’n Latynse vierkant van orde n is ’n n × n skikking van n simbole met die eienskap dat elke ry
en elke kolom van die skikking elke element presies een keer bevat. Dit is welbekend dat
Latynse vierkante gebruik kan word in die konstruksie van ontwerpe wat vra na ’n gebalanseerde
rangskikking van ’n versameling elemente onderhewig aan ’n aantal streng beperkings.
’n Belangrike toepassing van Latynse vierkante kom in die skedulering van verskeie spesiale
tipes gebalanseerde sporttoernooie voor, waarvan die eenvoudigste voorbeeld ’n sogenaamde
rondomtalietoernooi is — ’n toernooi waarin elke span elke ander span presies een keer teenstaan.
Onder die verskeie toepassings van Latynse vierkante in sporttoernooi-skedulering, is die probleem
van die skedulering van spesiale tipes gemengde dubbels tennis- en tafeltennistoernooie
deur gebruikmaking van spesiale versamelings van drie paarsgewys-ortogonale Latynse vierkante
in hierdie proefskrif van besondere belang. In sogenaamde gemengde dubbels tafeltennis (GDTT)
toernooi ding twee spanne, elk bestaande uit mans en vrouens, op ’n gemengde-dubbels rondomtalie
wyse mee, en dit is bekend dat enige versameling van drie paarsgewys-ortogonale Latynse
vierkante gebruik kan word om ’n skedule vir s´o ’n toernooi op te stel. ’n Meer interessante
sporttoernooi-ontwerp, en een wat al vantevore in minstens twee gerapporteerde gevalle deur
sportklubs benodig is, is egter ’n gade-vermydende gemengde-dubbels rondomtalie (GVGDR)
toernooi, en dit is bekend dat s´o ’n toernooi geskeduleer kan word deur gebruik te maak van ’n
self-ortogonale Latynse vierkant met ’n simmetriese ortogonale maat (SOLVSOM).
Hierdie toepassings het tot ’n aantal belangrike onopgeloste probleme in die teorie van Latynse
vierkante gelei, waarvan die mees beroemde die vraag na die bestaan van ’n versameling van
drie paarsgewys ortogonale Latynse vierkante van orde 10 is. Nog ’n onopgeloste probleem
is die vraag na die bestaan van SOLVSOMs van ordes 10 en 14. ’n Verdere probleem in die
teorie van Latynse vierkante wat aansienlik aandag in die literatuur geniet, is die bepaling
van die getal (essensieel) verskillende maniere waarop ’n versameling elemente in ’n Latynse
vierkant gerangskik kan word, m.a.w. die probleem van die enumerasie van Latynse vierkante
en ekwivalensieklasse van Latynse vierkante van ’n gegewe orde. Hierdie probleem raak vinnig
baie moeilik soos die orde van die Latynse vierkant groei, en aansienlike berekeningskrag word
dikwels hiervoor benodig. Sover is slegs ’n klein aantal ekwivalensieklasse van self-ortogonale
Latynse vierkante (SOLVe) in die literatuur getel, naamlik die getal verskillende SOLVe, die getal
idempotente SOLVe en die getal isomorfismeklasse voortgebring deur idempotente SOLVe van
ordes 4 n 9. Verder is slegs ’n klein aantal ekwivalensieklasse van geordende versamelings
van k onderling ortogonale Latynse vierkante (k-OOLVs) in die literatuur getel, naamlik die
getal hoofklasse voortgebring deur 2-OOLVs van orde n vir 3 n 8 en die getal isotoopklasse
voortgebring deur 8-OOLVs van orde 9. Daar is geen enumerasieresultate oor SOLVSOMs in
die literatuur beskikbaar nie.
In hierdie proefskrif word ’n metodologie vir die enumerasie van ekwivalensieklasse van Latynse
vierkante met behulp van ’n soekboomalgoritme met terugkering voorgestel. Hierdie algoritme
poog om oorbodigheid in die soektog te minimeer deur net strukture te oorweeg wat die potensiaal
het om tot goed-gedefinieerde klasleiers opgebou te word. Hierdie eienskap verseker dat
die algoritme slegs een Latynse vierkant binne elk van die klasse wat getel word, genereer, en
dus word ’n databasis van verteenwoordigers van hierdie klasse sodoende opgebou. Hierdie
klasverteenwoordigers kan tesame met verskeie welbekende groepteoretiese telresultate gebruik
word om die getal Latynse vierkante in elke klas te bepaal, asook die getal verskeie deelklasse
van verskillende tipes binne elke klas.
Die bogenoemde metodologie word toegepas om verskeie SOLV- en SOLVSOM-klasse van ordes
kleiner of gelyk aan 10 te tel, asook om k-OOLV-klasse van ordes kleiner of gelyk aan 8
te tel. Die getal verskillende SOLVe, idempotente SOLVe en isomorfismeklasse voortgebring
deur SOLVe word vir ordes 4 n 9 geverifieer, en daarbenewens word die getal isomorfismeklasse,
transponent-isomorfismeklasse en RC-paratoopklasse voortgebring deur SOLVe van
hierdie ordes ook bepaal. Die soektog word deur middel van ’n groot parallelisering van die
soekboomalgoritme op ’n aantal rekenaars ook uitgebrei na die tel van hierdie klasse voortgebring
deur SOLVe van orde 10. Die verteenwoordigers van RC-paratoopklasse voortgebring
deur SOLVe wat deur middel van hierdie algoritme gegenereer word, word dan gebruik om
SOLVSOMs te tel, terwyl bestaande databasisse van simmetriese Latynse vierkante as validasie
van die resultate ook vir hierdie doel ingespan word. Op hierdie manier word die getal
verskillende SOLVSOMs, standaardvorm SOLVSOMs, transponent-isomorfismeklasse voortgebring
deur SOLVSOMs asook RC-paratoopklasse voortgebring deur SOLVSOMs bepaal, en
word ’n databasis van verteenwoordigers van RC-paratoopklasse voortgebring deur SOLVSOMs
ook opgebou. Die bekende getal hoofklasse voortgebring deur 2-OOLVs van ordes 3 n 8
word in hierdie proefskrif geverifieer, en so ook word die getal hoofklasse voortgebring deur k-
OOLVs van ordes 3 n 8 bepaal, waar 3 k n−1. Ander ekwivalensieklasse voortgebring
deur k-OOLVs van orde n wat ook getel word, sluit in verskillende k-OOLVs en gereduseerde
k-OOLVs van ordes 3 n 8, waar 2 k n − 1.
Laastens word daar van ’n filtreer-metode gebruik gemaak om te bepaal of enige SOLV van
orde 10 twee basiese nodige voorwaardes om ’n ortogonale maat met sy transponent te deel
kan bevredig, en daar word gevind dat slegs vier van die 121 642 klasverteenwoordigers van
RC-paratoopklasse voortgebring deur SOLVe van orde 10 aan hierdie voorwaardes voldoen.
Dit word verder vasgestel dat geeneen van hierdie vier SOLVe ortogonale maats in gemeen
met hul transponente het nie. Die spektrum van afgehandelde ordes in terme van die bestaan
van SOLVSOMs word dus vergroot deur aan te toon dat geen sulke ontwerpe van orde 10
bestaan nie, en sodoende word ’n jarelange oop bestaansvraag in die teorie van Latynse vierkante
beantwoord. Verder bevestig hierdie metode ’n nuwe noodsaaklike bestaansvoorwaarde vir ’n
versameling van drie paarsgewys-ortogonale Latynse vierkante van orde 10, naamlik dat s´o ’n
versameling nie ’n SOLV en sy transponent kan bevat nie. / Harry Crossley Foundation / National Research Foundation
|
9 |
Lineární kódy a projektivní rovina řádu 10 / Linear codes and a projective plane of order 10Liška, Ondřej January 2013 (has links)
Projective plane of order 10 does not exist. Proof of this assertion was finished in 1989 and is based on the nonexistence of a binary code C generated by the incidence vectors of the plane's lines. As part of the proof of the nonexistence of code C, the coefficients of its weight enumerator were studied. It was shown that coefficients A12, A15, A16 and A19 have to be equal to zero, which contradicted other findings about the relationship among the coefficients. Presented diploma thesis elaborately analyses the phases of the proof and, in several places, enhances them with new observations and simplifications. Part of the proof is generalized for projective planes of order 8m + 2. 1
|
10 |
Construction of Minimal Partially Replicated Orthogonal Main-Effect Plans with 3 Factors朱正中, Chu, Cheng-Chung Unknown Date (has links)
正交主效應計畫(Orthogonal main-effect plans)因可無相關地估計主效應,故常被應用於一般工業上作為篩選因子之用。然而,實驗通常費時耗財。因此,如何設計一個較經濟且有效的計劃是很重要的。回顧過去相關的研究,Jacroux (1992)提供了最小正交主效應計劃的充份條件及正交主效應計畫之最少實驗次數表(Jacroux 1992),張純明(1998)針對此表提出修正與補充。在此,我們再次的補足此表。
正交主效應計畫中,如有重複實驗點,則純誤差可被估計,且據此檢定模型之適合度。Jacroux (1993)及張純明(1998)皆曾提出具最多部份重複之正交主效應計畫(Partially replicated orthogonal main-effect plans)。在此,我們討論所有三因子部份重複正交主效應計畫中,可能重複之最大次數,且具體提出建構此最大部份重複之最小正交主效應計畫之方法。 / Orthogonal main-effect plans (OMEP's), being able to estimate the main effects without correlation, are often employed in industrial situations for screening purpose. But experiments are expensive and time consuming. When an economical and efficient design is desired, a minimal orthogonal main-effect plans is a good choice. Jacroux (1992) derived a sufficient condition for OEMP's to have minimal number of runs and provided a table of minimal OMEP run numbers. Chang (1998) corrected and supplemented the table. In this paper, we try to improve the table to its perfection.
A minimal OMEP with replicated runs is appreciated even more since then the pure error can be estimated and the goodness-of-fit of the model can be tested. Jacroux (1993) and Chang (1998) gave some partially replicated orthogonal main-effect plans (PROMEP's) with maximal number of replicated points. Here, we discuss minimal PROMEP's with 3 factors in detail. Methods of constructing minimal PROMEP's with replicated runs are provided, and the number of replicated runs are maximal for most cases.
|
Page generated in 0.0547 seconds