A Tradução Desse Texto Poderá Ser Útil (Constructions Of Lotto Designs)

[BigMax]

Quem dominar o inglês e puder ajudar com a tradução antecipadamente agradeço.

 

Constructions of Lotto Designs

 

Simple (but useful) constructions:

–Adding a point to a lotto design L(v+1,k+1,t,m) < / =  L(v,k,t,m) 

–Complementing a lotto design L(v,k,t,m) = L(v,v-k,v+t-k-m,v-m) 

–Lotto design induced by two lotto designs L(v+1,k+1,t+1,m+1)< / = L(v,k+1,t+1,m+1) + L(v,k,t,m) 

–Summing two lotto designs L(v,k,t,m) < / = L(v1,k,t,m1) + L(v2,k,t,m2)                                    (where v=v1+v2 andm=m1+m2-1)

 

Adding a point to a lotto design:

 

–Given a (v,k,t,m)-lotto design(V,A), to each block of A we add an additional element e to obtaina new collection A*of blocks. Let (VU{e}, A*) be the lotto design desired.

The new collectionA*of blocks covers in at least tpoints any m-set in VU{e}, therefore: L(v+1,k+1,t,m) < / =  L(v,k,t,m) 

 

Complementing a lotto design:

 

–Given a(v,k,t,m)-lotto design(V,A), we consider the new lotto design (V,B = {V \A:AinA}) which is a (v,v-k,v+t-k-m,v-m) -lotto design.

Therefore: L(v,k,t,m) =L(v,v-k,v+t-k-m,v-m) 

 

Lotto design induced by two lotto designs:

 

–Given a(v,k+1,t+1,m+1)-lotto design(V,A) and a (v,k,t,m)-lotto design(V, , to each block of Bwe add an additional element e to obtaina new collection B*.

Let (VU{e},A UB*)bethe lotto design desired.

The new collectionAUB*of blocks covers in at least t+1points any m+1-set in VU{e}, therefore: L(v+1,k+1,t+1,m+1)< / =  L(v,k+1,t+1,m+1) + L(v,k,t,m) 

 

Summing two lotto designs:

 

–Given a(v1,k,t,m1)-lotto design(V1,A)  and a (v2,k,t,m2)-lotto design(V2, , let (V1U V2,A UB)bethe lotto design desired.

The new collectionA UBof blocks covers in at least tpoints any m-set in V1 U V2(see table alongside) therefore: L(v,k,t,m) < / = L(v1,k,t,m1) + L(v2,k,t,m2) (Where v=v1+v2 andm=m1+m2-1)

 

Summing two lotto designs –Upper bounds for L(v,6,3,6) L(v,6,3,6)< / =  L(v1,6,3,3) + L(v2,6,3,4)

–Example: 

•L(49,6,3,6)< / =  L(22,6,3,3) + L(27,6,3,4) 163 

–L(22,6,3,3) = C(22,6,3) = 77 since there exists a Steiner System S(22,6,3) 

–L(27,6,3,4) 86 since R. Belicand D. Stojiljkovic[2] obtained a record-breaking (27,6,3,4)-lotto designof size 86

 

Upper bounds for L(v,6,4,6): AGeneral Construction

 

•Divide in two partsV1andV2(respectively of order v1 and v2) a given set V of order v. 

•Consider a(v1,6,4)-covering design (V1,A)  and a  (v2,6,4)-covering design (V2, . 

•Finally, consider C= D1D2= {D1UD2: D1inD1, D2inD2}, where D1andD2are, respectively, the blocks of a (v1,3,2,3)-lottodesign(V1,D1 ) and the blocks of a      (v1,3,2,3)-lottodesign (V2,D2 ). 

•Let (V, A UB UC) be the lotto design desired. 

•The new collection A UB UCof blocks covers in at least 6 points any 6-set in V, therefore:

  L(v,6,4,6)  minv1+v2 = v(L(v1,6,4,4) + L(v2,6,4,4) + L(v1,3,2,3)*L(v2,3,2,3)) 

 

Upper bounds for L(v,6,4,6): Multi-splitConstruction

P. Crescenzi, F. Montecalvoand G. Rossi described the following construction [4]: 

•Divide in two partsV1 andV2 (respectively of orderv1 andv2)a given set V. Divide again V2 inthree partsV2.1, V2.2 and V2.3(respectively of orderv2.1, v2.2 andv2.3). 

•Consider a(v1,6,4)-covering design (V1,D)  and a (v2,6,4,5)-lotto design (V2,F). 

•For j=1,2,3let Bjbe the blocks of a (v2.j,3,2)-covering design (V2.jBj)and assume that each covering design(V2.jBj)can be partitioned into hj(v2.j,3,1)-covering designs(V2.jBpj)(where p=1,2,…,hj).  

•Consider h (v1,3,2)-covering designs(V1Ai)such that  A1UA2U …UAh =V13, where V13is the set of all the triples in V1 andh = h1+h2+h3. 

•Let C  bedefined as: C= A1B11 U …UAh1 Bh11 UAh1+1 B12 U …UAh1+h2 Bh22 UAh1+h2+1 B13U …UAh Bh33 Where, given two sets Aand B, ABdenotes the set {A UB: Ain A, Bin B} 

•(V, C  U D UF)is a(v2,6,4,6)-lotto design. Therefore, if all the covering designs involved in the construction of the collection C are optimal, we have:

L(v,6,4,6)  C(v1,6,4) + L(v2,6,4,5) + C(v1,3,2)*C(v2.1,3,2) + C(v1,3,2)*C(v2.2,3,2) + C(v1,3,2)*C(v2.3,3,2)

 

[DixieJoe]

Já que não consigo construir os desdobramentos, minha modesta contribuição, com a tradução do texto acima:

 

Construções de “Lotto Designs”

(ou apenas “Desdobramentos”)

 

Construções Simples (mas úteis):

-Acrescentando um ponto (dezena) a um desdobramento L (v + 1, k + 1, t, m) </ = L (v, k, t, m)

-Complementando  um desdobramento L (v, k, t, m) = L (v, v-k, v + t-k-m, v-m)

-Desdobramento Induzido (criado) por dois desdobramentos  L (v + 1, k + 1, T + 1, m + 1) </ = L (v, k + 1, t + 1, m + 1) +L (v, k, t, m)

-Somando dois desdobramentos L (v, k, t, m) </ = L (v1, k, t, m1) + L (v2, k, t, m2) (onde  v = v1 + v2   e  m= m1 + m2-1)

 

Acrescentando um ponto a um desdobramento:

 

-Dado um desdobramento (V, A) do tipo  (v, k, t, m), a cada bloco de A nós adicionamos um elemento adicional e para obter uma nova  coleção A * de blocos (linhas).  Seja (VU {e}, A *)  o desdobramento  desejado.

O novo conjunto A* de blocos  cobre em, pelo menos,  t pontos,  qualquer conjunto m em

VU {e}.  Por conseguinte:  L (v + 1, k + 1, t, m) </ =L (v, b, t, m)

 

Complementando um desdobramento:

 

-Dado um desdobramento (V,A) do tipo  a(v, k, t, m) -lotto (V, A), consideramos o novo desdobramento  (V,  = {V \ A: A pertence a A}) que é um desdobramento (v, v-k, v + t-k-m, v-m) .

Portanto: L (v, k, t, m) = L (v, v-v, v + t-k-m, v-m)

 

 Desdobramento Induzido (criado por dois outros desdobramentos) 

-Dados um desdobramento (V,A) do tipo a (v, k + 1, t+ 1, t + 1) e outro desdobramento (V,  do tipo a (v, k, t, m),  para cada bloco de B nós acrescentamos um elemento adicional e para obter uma  nova coleção B *.

Seja (VU {e}, A UB *) o novo desdobramento desejado.

A nova coleção AUB * de linhas cobre, pelo menos em t + 1pontos  qualquer conjunto m + 1 de VU {e}. Por conseguinte: L (v + 1, k + 1, t + 1, m + 1) </ = L ( v, k + 1, t + 1, m + 1) + L (v, k, t, m)

 

Somando dois  desdobramentos :

 

-Dados um desdobramento (V1, A)   do tipo a(v1, k, t, m1)  e um desdobramento (V2,  do tipo  a(v2, k, t, m2),  (V1U V2, A UB) será o desdobramento desejado.

A nova coleção A UB de blocos cobre, em pelo menos t pontos, qualquer conjunto de  V1 U V2 (ver tabela ao lado).  Por conseguinte,  L (v, k, t, m) </ = L (v1, K, T, m1) + L (v2, k, t, m2)

 (Onde v = v1 + v2 = e  m= m1 + M2-1)

 

Somando dois desdobramentos  -  Limites Superiores para L (v, 6,3,6) L (v, 6,3,6) </ = L (v1,6,3,3) + L (v2,6,3, 4)

-Exemplo:

• L (49,6,3,6) </ = L (22,6,3,3) + L (27,6,3,4) 163

-L (22,6,3,3) = C (22,6,3) = 77, pois já  existe um sistema Steiner S (22,6,3)

-L (27,6,3,4) = 86  pois R. Belicand D. Stojiljkovic [2] obtiveram um desdobramento record (27,6,3,4) com tamanho de 86 linhas

 

Limites superiores para L (v, 6,4,6): Uma construção básica

 

• Divida em duas partes V1 e V2 (respectivamente de tamanhos v1 e v2) um determinado conjunto V de tamanho  v.

• Considere um desdobramento (V1,A)  do tipo  (v1,6,4) e outro  desdobramento (V2,B do tipo (v2,6,4) .

• Finalmente, considere C = D1D2 = {D1UD2: D1inD1, D2inD2}, onde D1andD2 são, respectivamente, os blocos de um desdobramento (V1, D1) do tipo (v1,3,2,3)   e os blocos de outro desdobramento (V2, D2) do tipo (v1,3 , 2,3).

• Seja (V, A UB UC) o desdobramento desejado..

• A nova coleção de blocos A UB UC  cobre,  em pelo menos 6 pontos, qualquer conjunto de 6 pontos de  V.

Portanto:   L (v, 6,4,6) mínimo v1 + v2 =  v (L (v1,6,4,4) + L (v2,6,4,4) + L (v1,3,2,3) * L (v2,3,2,3))

 

Limites superiores para L (V, 6,4,6): Construção Multi-split (“quebras Múltiplas”)

P. Crescenzi, F. Montecalvo e G. Rossi descreveram a seguinte construção [4]:

• Divida em duas partes V1 e V2 (respectivamente de tamanhos v1 e  v2) um conjunto dado V. Divida V2 novamente em 3 partes V2.1, V2.2 e V2.3 (respectivamente de tamanhos  v2.1, v2.2 e v2.3).

• Considere um desdobramento (V1, D)  do tipo (v1,6,4)  e um desdobramento (V2, F) do tipo (v2,6,4,5).

• Para j = 1,2,3 faça com que  Bj seja os blocos de  um desdobramento (V2.jBj)  do tipo (v2.j,3,2) e assuma que cada desdobramento (V2.jBj)  possa ser particionado em desdobramentos  (V2.jBpj) do tipo hj (v2. j, 3,1),   (onde p = 1,2, ..., hj).

• Considere desdobramentos (V1Ai) do tipo h(v1,3,2) tais que A1UA2U ... UAH = V13, onde V13 é o conjunto de todos os triplos em V1 e h = h1 + H2 + h3.

• Considere a definição de C como: C = A1B11 U ... UAh1 Bh11 UAh1 + 1 B12 U ... UAh1 + h2 Bh22 UAh1 + h2 + 1 B13U ... UAH Bh33 onde, dados 2 conjuntos A e B, AB denota o conjunto {A UB: A pertence a  A, B pertence a  B}

• (V, C U D UF) é um desdobramento  (v2,6,4,6) . Portanto, se todos os desdobramentos envolvidos na construção da coleção C são ótimos, temos:

L(v, 6,4,6) C (v1,6,4) + L(v2,6,4,5) + C (v1,3,2) * C (v2.1,3,2) + C (v1,3,2) * C (v2.2,3,2) + C (v1,3,2) * C (v2.3,3,2)

Edited January 1, 2016 by DixieJoe

[BigMax]

Obrigado!

[DixieJoe]

Detalhe: Não estou conseguindo editar a carinha em AMARELO...

 

Considerem (nos 3 lugares em que aparecem as carinhas em Amarelo), como sendo UM B MAIUSCULO SEGUIDO POR )

 

Não sei porque isso acontece. Ao colar ficou OK. Depois apareceu a carinha e não consigo editar....

Edited January 1, 2016 by DixieJoe

[BigMax]

Clicar em + opções e desabilitar emoticons

 

[DixieJoe]

Obrigado, BigMax,

 

Testando

 

[DixieJoe]

Enviando de novo, já que não consigo editar....

 

Construções de “Lotto Designs”

(ou apenas “Desdobramentos”)

 

Construções Simples (mas úteis):

-Acrescentando um ponto (dezena) a um desdobramento L (v + 1, k + 1, t, m) </ = L (v, k, t, m)

-Complementando  um desdobramento L (v, k, t, m) = L (v, v-k, v + t-k-m, v-m)

-Desdobramento Induzido (criado) por dois desdobramentos  L (v + 1, k + 1, T + 1, m + 1) </ = L (v, k + 1, t + 1, m + 1) +L (v, k, t, m)

-Somando dois desdobramentos L (v, k, t, m) </ = L (v1, k, t, m1) + L (v2, k, t, m2) (onde  v = v1 + v2   e  m= m1 + m2-1)

 

Acrescentando um ponto a um desdobramento:

 

-Dado um desdobramento (V, A) do tipo  (v, k, t, m), a cada bloco de A nós adicionamos um elemento adicional e para obter uma nova  coleção A * de blocos (linhas).  Seja (VU {e}, A *)  o desdobramento  desejado.

O novo conjunto A* de blocos  cobre em, pelo menos,  t pontos,  qualquer conjunto m em

VU {e}.  Por conseguinte:  L (v + 1, k + 1, t, m) </ =L (v, b, t, m)

 

Complementando um desdobramento:

 

-Dado um desdobramento (V,A) do tipo  a(v, k, t, m) -lotto (V, A), consideramos o novo desdobramento  (V,   = {V \ A: A pertence a A}) que é um desdobramento (v, v-k, v + t-k-m, v-m) .

Portanto: L (v, k, t, m) = L (v, v-v, v + t-k-m, v-m)

 

 Desdobramento Induzido (criado por dois outros desdobramentos) 

-Dados um desdobramento (V,A) do tipo a (v, k + 1, t+ 1, t + 1) e outro desdobramento (V,  do tipo a (v, k, t, m),  para cada bloco de B nós acrescentamos um elemento adicional e para obter uma  nova coleção B *.

Seja (VU {e}, A UB *) o novo desdobramento desejado.

A nova coleção AUB * de linhas cobre, pelo menos em t + 1pontos  qualquer conjunto m + 1 de VU {e}. Por conseguinte: L (v + 1, k + 1, t + 1, m + 1) </ = L ( v, k + 1, t + 1, m + 1) + L (v, k, t, m)

 

Somando dois  desdobramentos :

 

-Dados um desdobramento (V1, A)   do tipo a(v1, k, t, m1)  e um desdobramento (V2,  do tipo  a(v2, k, t, m2),  (V1U V2, A UB) será o desdobramento desejado.

A nova coleção A UB de blocos cobre, em pelo menos t pontos, qualquer conjunto de  V1 U V2 (ver tabela ao lado).  Por conseguinte,  L (v, k, t, m) </ = L (v1, K, T, m1) + L (v2, k, t, m2)

 (Onde v = v1 + v2 = e  m= m1 + M2-1)

 

Somando dois desdobramentos  -  Limites Superiores para L (v, 6,3,6) L (v, 6,3,6) </ = L (v1,6,3,3) + L (v2,6,3, 4)

-Exemplo:

• L (49,6,3,6) </ = L (22,6,3,3) + L (27,6,3,4) 163

-L (22,6,3,3) = C (22,6,3) = 77, pois já  existe um sistema Steiner S (22,6,3)

-L (27,6,3,4) = 86  pois R. Belicand D. Stojiljkovic [2] obtiveram um desdobramento record (27,6,3,4) com tamanho de 86 linhas

 

Limites superiores para L (v, 6,4,6): Uma construção básica

 

• Divida em duas partes V1 e V2 (respectivamente de tamanhos v1 e v2) um determinado conjunto V de tamanho  v.

• Considere um desdobramento (V1,A)  do tipo  (v1,6,4) e outro  desdobramento (V2,B do tipo (v2,6,4) .

• Finalmente, considere C = D1D2 = {D1UD2: D1inD1, D2inD2}, onde D1andD2 são, respectivamente, os blocos de um desdobramento (V1, D1) do tipo (v1,3,2,3)   e os blocos de outro desdobramento (V2, D2) do tipo (v1,3 , 2,3).

• Seja (V, A UB UC) o desdobramento desejado..

• A nova coleção de blocos A UB UC  cobre,  em pelo menos 6 pontos, qualquer conjunto de 6 pontos de  V.

Portanto:   L (v, 6,4,6) mínimo v1 + v2 =  v (L (v1,6,4,4) + L (v2,6,4,4) + L (v1,3,2,3) * L (v2,3,2,3))

 

Limites superiores para L (V, 6,4,6): Construção Multi-split (“quebras Múltiplas”)

P. Crescenzi, F. Montecalvo e G. Rossi descreveram a seguinte construção [4]:

• Divida em duas partes V1 e V2 (respectivamente de tamanhos v1 e  v2) um conjunto dado V. Divida V2 novamente em 3 partes V2.1, V2.2 e V2.3 (respectivamente de tamanhos  v2.1, v2.2 e v2.3).

• Considere um desdobramento (V1, D)  do tipo (v1,6,4)  e um desdobramento (V2, F) do tipo (v2,6,4,5).

• Para j = 1,2,3 faça com que  Bj seja os blocos de  um desdobramento (V2.jBj)  do tipo (v2.j,3,2) e assuma que cada desdobramento (V2.jBj)  possa ser particionado em desdobramentos  (V2.jBpj) do tipo hj (v2. j, 3,1),   (onde p = 1,2, ..., hj).

• Considere desdobramentos (V1Ai) do tipo h(v1,3,2) tais que A1UA2U ... UAH = V13, onde V13 é o conjunto de todos os triplos em V1 e h = h1 + H2 + h3.

• Considere a definição de C como: C = A1B11 U ... UAh1 Bh11 UAh1 + 1 B12 U ... UAh1 + h2 Bh22 UAh1 + h2 + 1 B13U ... UAH Bh33 onde, dados 2 conjuntos A e B, AB denota o conjunto {A UB: A pertence a  A, B pertence a  B}

• (V, C U D UF) é um desdobramento  (v2,6,4,6) . Portanto, se todos os desdobramentos envolvidos na construção da coleção C são ótimos, temos:

L(v, 6,4,6) C (v1,6,4) + L(v2,6,4,5) + C (v1,3,2) * C (v2.1,3,2) + C (v1,3,2) * C (v2.2,3,2) + C (v1,3,2) * C (v2.3,3,2)

 

 

 

 

Ufaaa.... Agora deu certo. Obrigado BigMax. Mas só funciona numa Resposta inicial. Não funciona para Editar... Resolvido

Edited January 1, 2016 by DixieJoe