Association scheme

Association scheme

In mathematics, association schemes are structures that appear in many different forms in the fields of combinatorics and statistics.

Definition

Recall that a binary relation R on a set X can be thought of as subset of X imes X.

A "k-class Association Scheme" is a set of points, "X", along with "k+1" binary relations R_0,R_1,ldots,R_kwhich partition X imes X and R_0 = {(x,x) | x in X} (i.e. R_0 is the identity relation), such that the following holds:

There exist (k+1)^3 non-negative integers p_{ij}^l with 0 le i,j,l le k and for any (x,y) in R_l thereare exactly p_{ij}^l elements z in X such that (x,z) in R_i and (z,y) in R_j

An association scheme is "commutative" if p_{ij}^l=p_{ji}^l for all i, j and l. Most authorsassume this property.

A "symmetric association scheme" is one in which each relation R_i is a symmetric relation. Every symmetric association scheme is commutative.

Terminology

*If (x,y) in R_i we say that x and y are "i"th associates.
*The numbers p_{ij}^l are called the parameters of the scheme.

Basic Facts

*p_{00}^0 = 1, i.e. if (x,y) in R_0 then x = y and the only z such that (x,z) in R_0 is z=x
*sum_{i=0}^{k} p_{ii}^0 = |X|, this is because the R_i partition X.

Examples

*The "Johnson scheme", denoted "J"("v,k"), is defined as follows. Let "S" be a set with "v" elements. The points of the scheme "J(v,k)" are the {v choose k} subsets of S with "k" elements. Two "k"-element subsets "A", "B" of "S" are "i" th associates when their intersection has size "k − i".

*The "Hamming scheme", denoted "H"("n,q"), is defined as follows. The points of "H(n,q)" are the "qn" ordered "n"-tuples over a set of size "q". Two "n"-tuples "x, y" are said to be "i" th associates if they disagree in exactly "i" coordinates. E.g., if "x" = (1,0,1,1), "y" = (1,1,1,1), "z" = (0,0,1,1), then "x" and "y" are 1st associates, "x" and "z" are 1st associates and "y" and "z" are 2nd associates in "H(4,2)".

*A distance-regular graph, "G", forms an association scheme by defining two vertices to be "i" th associates if their distance is "i".

*A finite group G yields an association scheme on X=G, with a class "R""g" for each group element, as follows: for each g in G let R_g={(x,y) | x=g*y} where * is the group operation. The class of the group identity is "R"0. This association scheme is commutative if and only if G is abelian.

References

* Bailey, R.A. (2004), "Association Schemes: Designed Experiments, Algebra and Combinatorics". Cambridge, Eng.: Cambridge University Press. ISBN 0-521-82446-X
* Delsarte, P. (1973), "An Algebraic Approach to the Association Schemes of Coding Theory". Philips Research Reports, Supplement No. 10.
* van Lint, J.H., and Wilson, R.M. (1992), "A Course in Combinatorics". Cambridge, Eng.: Cambridge University Press. ISBN 0-521-00601-5


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Association of Ideas — Association of Ideas, or Mental association, is a term used principally in the history of philosophy and of psychology to refer to explanations about the conditions under which representations arise in consciousness, and also for a principle put… …   Wikipedia

  • Association of Chartered Certified Accountants — Infobox Company company name = The Association of Chartered Certified Accountants (ACCA) company company type = British chartered accountancy body foundation = flagicon|UK [England, UK] (1904) company slogan = ACCA Accountancy s uncommon… …   Wikipedia

  • Association bancaire pour l'euro — L’Association bancaire pour l’euro (ABE) ou Euro Banking Association (EBA) comprend environ 190 banques membres en Europe et joue un rôle majeur dans le secteur financier en tant qu’initiateur de nouveaux systèmes de paiements paneuropéens et du… …   Wikipédia en Français

  • Association of Nene River Clubs — The Association of Nene River Clubs (ANRC) is an association and umbrella organisation for waterway societies on the River Nene, [cite web|url=http://easyweb.easynet.co.uk/jim.shead/IWAPE/IWAPElinks.htm|title=IWA Peterborough… …   Wikipedia

  • Association of Chartered Certified Accountants — Die Association of Chartered Certified Accountants (ACCA) ist ein in Großbritannien ansässiger Rechnungslegungs Verband, der den ACCA Titel vergibt. Der Verband ist einer der größten weltweit im Bereich der Rechnungslegung und hat 131.500… …   Deutsch Wikipedia

  • Association of Malayalam Movie Artists — Infobox Union name= AMMA country= India members= 320+ full name= Association of Malayalam Movie Artists native name= founded= current= president= Innocent general secretary= Padmashri Mohanlal dissolved date= dissolved state= merged into= office …   Wikipedia

  • Association of Southeast Asian Nations — Philippines|flagicon|Singapore Singapore|flagicon|Thailand Thailand|flagicon|Vietnam Vietnam admin center type = nowrap|Seat of Secretariat admin center = Jakarta, Indonesia flagicon|Indonesia leader title1 = Secretary General leader name1 =… …   Wikipedia

  • Association of secondary ticket agents — The Association of Secondary Ticket Agents, or ASTA UK, is the Regulatory Body of the Secondary Ticket Industry in the United Kingdom. The Association was established in October 2005, and represents companies engaged in the selling of tickets to… …   Wikipedia

  • Association of British Science Writers — The Association of British Science Writers (ABSW) is the UK society for science writers, journalists and communicators. It was founded in 1947 and is the oldest such national organisation in the world. The ABSW is a professional body that exists… …   Wikipedia

  • Association for Learning Technology — The Association for Learning Technology (ALT) is a United Kingdom professional body and scholarly association. ALT brings together people and organizations with an interest in the use of learning technology. ALT was founded in 1993 and is a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”