Balanced critical sets in Latin squares

In this note we first introduce balanced critical sets and near balanced critical sets in Latin squares. Then we prove that there exist balanced critical sets in the back circulant Latin squares of order 3n for n even. Using this result we decompose the back circulant Latin squares of order 3n, n even, into three isotopic and disjoint balanced critical sets each of size 3n. We also find near balanced critical sets in the back circulant Latin squares of order 3n for n odd. Finally, we examine representatives of each main class of Latin squares of order up to six in order to determine which main classes contain balanced or near balanced critical sets.

A census of critical sets in the Latin squares of order at most six

A critical set in a Latin square of order n is a set of entries from the square which can be embedded in precisely one Latin square of order n, Such that if any element of the critical set. is deleted, the remaining set can be embedded, in more than one Latin square of order n.. In this paper we find all the critical sets of different sizes in the Latin squares of order at most six. We count the number of main and isotopy classes of these critical sets and classify critical sets from the main classes into various strengths. Some observations are made about the relationship between the numbers of classes, particularly in the 6 x 6 case. Finally some examples are given of each type of critical set.

An investigation of 2-critical sets in latin squares

In this paper we focus on the existence of 2-critical sets in the latin square corresponding to the elementary abelian 2-group of order 2(n). It has been shown by Stinson and van Rees that this latin square contains a 2-critical set of volume 4(n) - 3(n). We provide constructions for 2-critical sets containing 4(n) - 3(n) + 1 - (2(k-1) + 2(m-1) + 2(n-(k+m+1))) entries, where 1 less than or equal to k less than or equal to n and 1 less than or equal to m less than or equal to n - k. That is, we construct 2-critical sets for certain values less than 4(n) - 3(n) + 1 - 3 (.) 2([n /3]-1). The results raise the interesting question of whether, for the given latin square, it is possible to construct 2-critical sets of volume m, where 4(n) - 3(n) + 1 - 3 (.) 2([n/3]-1) < m < 4(n) - 3(n).

A new class of critical sets in Latin squares

Previously the process of finding critical sets in Latin squares has been inside cumbersome by the complexity and number of Latin trades that, must be constructed. In this paper we develop a theory of Latin trades that yields more transparent constructions. We use these Latin trades to find a new class of critical sets for Latin squares which are a product of the Latin square of order 2 with a. back circulant Latin square of odd order.

Transformações socioambientais na comunidade de Dom Manuel Barcarena/PA

Esta dissertação de mestrado se propõe a identificar e analisar as transformações socioambientais ocorridas na comunidade remanescente de indígenas Dom Manuel, situada no município de Barcarena – PA, a partir da intensificação das atividades industriais ao redor da área da comunidade, buscando compreender como se dá os impactos ambientais das empresas nas comunidades tradicionais no município de Barcarena, além de analisar e refletir sobre o processo de descaracterização das comunidades tradicionais frente ao processo industrial e discutir o conhecimento da área da Educação Ambiental, bem como de suas políticas como um elemento chave para a implementação da sustentabilidade na região. A metodologia utilizada nesta pesquisa se fundamenta na perspectiva da interdisciplinaridade, para coleta dos dados foram realizadas entrevistas semi-estruturadas com os moradores da comunidade, bem como registros fotográficos e técnicas de observação. A partir das análises realizadas constatou-se que a realidade da Comunidade Dom Manuel e as relações estabelecidas entre os moradores sofreram profundas modificações a partir da implantação das indústrias na área do pólo industrial. O acirramento da lógica capitalista ao redor da comunidade Dom Manuel vem proporcionando ao longo de seu processo a descaracterização de sua cultura e consequentemente a perda de sua identidade, bem como modificado o seu ambiente natural. Neste contexto a Educação Ambiental crítica se configura num importante viés para a sustentabilidade das comunidades tradicionais e de seus saberes, uma vez que se propõe à articular as discussões entre os seres humanos e o meio ambiente partindo do campo das relações sociais e político-ideológicas, buscando a formação de sujeitos críticos, capazes de compreenderem e intervirem na realidade que encontram-se inseridos, na defesa de seus direitos e deveres.

Watching subgraphs to improve efficiency in maximum clique search

This paper describes a new technique referred to as watched subgraphs which improves the performance of BBMC, a leading state of the art exact maximum clique solver (MCP). It is based on watched literals employed by modern SAT solvers for boolean constraint propagation. In efficient SAT algorithms, a list of clauses is kept for each literal (it is said that the clauses watch the literal) so that only those in the list are checked for constraint propagation when a (watched) literal is assigned during search. BBMC encodes vertex sets as bit strings, a bit block representing a subset of vertices (and the corresponding induced subgraph) the size of the CPU register word. The paper proposes to watch two subgraphs of critical sets during MCP search to efficiently compute a number of basic operations. Reported results validate the approach as the size and density of problem instances rise, while achieving comparable performance in the general case.

On the forced matching numbers of bipartite graphs

Let G be a graph that admits a perfect matching. A forcing set for a perfect matching M of G is a subset S of M, such that S is contained in no other perfect matching of G. This notion has arisen in the study of finding resonance structures of a given molecule in chemistry. Similar concepts have been studied for block designs and graph colorings under the name defining set, and for Latin squares under the name critical set. There is some study of forcing sets of hexagonal systems in the context of chemistry, but only a few other classes of graphs have been considered. For the hypercubes Q(n), it turns out to be a very interesting notion which includes many challenging problems. In this paper we study the computational complexity of finding the forcing number of graphs, and we give some results on the possible values of forcing number for different matchings of the hypercube Q(n). Also we show an application to critical sets in back circulant Latin rectangles. (C) 2003 Elsevier B.V. All rights reserved.

Minimal Homogeneous Latin Trades

A latin trade is a subset of a latin square which may be replaced with a disjoint mate to obtain a new latin square. A d-homogeneous latin trade is one which intersects each row, each column and each entry of the latin square either 0 or d times. In this paper we give a construction for minimal d-homogeneous latin trades of size dm, for every integer d >= 3, and m >= 1.75d(2) + 3. We also improve this bound for small values of d. Our proof relies on the construction of cyclic sequences whose adjacent sums are distinct. (c) 2006 Elsevier B.V. All rights reserved.