| 1. |
- Andren, Lina J., et al.
(författare)
-
Avoiding Arrays of Odd Order by Latin Squares
- 2013
-
Ingår i: Combinatorics, probability & computing. - : Cambridge University Press (CUP). - 0963-5483 .- 1469-2163. ; 22:2, s. 184-212
-
Tidskriftsartikel (refereegranskat)abstract
- We prove that there is a constant c such that, for each positive integer k, every (2k + 1) x (2k + 1) array A on the symbols 1, ... , 2k + 1 with at most c(2k + 1) symbols in every cell, and each symbol repeated at most c(2k + 1) times in every row and column is avoidable; that is, there is a (2k + 1) x (2k + 1) Latin square S on the symbols 1, ... , 2k + 1 such that, for each i, j is an element of {1, ... , 2k + 1}, the symbol in position (i, j) of S does not appear in the corresponding cell in Lambda. This settles the last open case of a conjecture by Haggkvist. Using this result, we also show that there is a constant rho, such that, for any positive integer n, if each cell in an n x n array B is assigned a set of m andlt;= rho n symbols, where each set is chosen independently and uniformly at random from {1, ... , n}, then the probability that B is avoidable tends to 1 as n -andgt; infinity.
|
|
| 2. |
- Andrén, Lina J., 1980-, et al.
(författare)
-
Avoiding arrays of odd order by Latin squares
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- We prove that there exists a constant c such that for each pos- itive integer k every (2k+1)×(2k+1) array A on the symbols 1,...,2k+1 with at most c(2k + 1) symbols in every cell, and each symbol repeated at most c(2k+1) times in every row and column is avoidable; that is, there is a (2k+1)×(2k+1) Latin square S on the symbols 1,...,2k+1 such that for each cell (i, j) in S the symbol in (i, j) does not appear in the corresponding cell in A. This settles the last open case of a conjecture by Häggkvist.
|
|
| 3. |
- Björklund, Johanna, et al.
(författare)
-
Simulation relations for pattern matching in directed graphs
- 2013
-
Ingår i: Theoretical Computer Science. - : Elsevier. - 0304-3975 .- 1879-2294. ; 485, s. 1-15
-
Tidskriftsartikel (refereegranskat)abstract
- We consider the problem of finding the occurrences of a pattern tree t in a directed graph g, and propose two algorithms, one for preprocessing and one for searching for t in g. It is assumed that the object graph itself is large and static, and that the pattern tree is small and frequently updated. To model varying abstraction levels in the data, we work with partially ordered alphabets and compute simulation relations rather than equivalence relations. In particular, vertices and edges are labelled with elements from a pair of preorders instead of unstructured alphabets. Under the above assumptions, we obtain a search algorithm that runs in time O(height (t) . vertical bar t vertical bar . vertical bar(V-g(+/-)t/R-g(+/-)t vertical bar(2)) where vertical bar (V-g(+/-)t/R-g(+/-)t)vertical bar is the number of equivalence classes in the coarsest simulation relation R-g(+/-)t on the graph g((+/-))t, the disjoint union of g and t. This means that the size of the object graph only affects the running time of the search algorithm indirectly, because of the groundwork done by the preprocessing routine in time O(k . vertical bar g vertical bar . vertical bar(V-g/R-g)vertical bar(2)), where vertical bar(V-g/R-g) is the number of equivalence classes in the coarsest simulation relation R-g on g, taking k = vertical bar V-g vertical bar(2) in the general case and k = height (g) if g is acyclic.
|
|
| 4. |
|
|
| 5. |
|
|
| 6. |
- Cutler, Jonathan, et al.
(författare)
-
Latin squares with forbidden entries
- 2006
-
Ingår i: The Electronic Journal of Combinatorics. - 1097-1440 .- 1077-8926. ; 13:1, s. R47-
-
Tidskriftsartikel (refereegranskat)
|
|
| 7. |
- Denley, Tristan, et al.
(författare)
-
Extending partial latin cubes
- 2014
-
Ingår i: Ars combinatoria. - 0381-7032. ; 113, s. 405-414
-
Tidskriftsartikel (refereegranskat)abstract
- In the spirit of Ryser's theorem, we prove sufficient conditions on k, and m so that k xexm Latin boxes, i.e. partial Latin cubes whose filled cells form a k x x m rectangular box, can be extended to akxnxm latin box, and also to akxnxn latin box, where n is the number of symbols used, and likewise the order of the Latin cube. We also prove a partial Evans type result for Latin cubes, namely that any partial Latin cube of order n with at most n 1 filled cells is completable, given certain conditions on the spatial distribution of the filled cells.
|
|
| 8. |
|
|
| 9. |
- Jäger, Gerold, et al.
(författare)
-
Enumeration of sets of mutually orthogonal latin rectangles
- 2024
-
Ingår i: The Electronic Journal of Combinatorics. - : Australian National University Press. - 1097-1440 .- 1077-8926. ; 31:1
-
Tidskriftsartikel (refereegranskat)abstract
- We study sets of mutually orthogonal Latin rectangles (MOLR), and a natural variation of the concept of self-orthogonal Latin squares which is applicable on larger sets of mutually orthogonal Latin squares and MOLR, namely that each Latin rectangle in a set of MOLR is isotopic to each other rectangle in the set. We call such a set of MOLR co-isotopic. In the course of doing this, we perform a complete enumeration of sets of t mutually orthogonal k × n Latin rectangles for k ≤ n ≤ 7, for all t < n up to isotopism, and up to paratopism. Additionally, for larger n we enumerate co-isotopic sets of MOLR, as well as sets of MOLR where the autotopism group acts transitively on the rectangles, and we call such sets of MOLR transitive. We build the sets of MOLR row by row, and in this process we also keep track of which of the MOLR are co-isotopic and/or transitive in each step of the construction process. We use the prefix stepwise to refer to sets of MOLR with this property at each step of their construction. Sets of MOLR are connected to other discrete objects, notably finite geometries and certain regular hypergraphs. Here we observe that all projective planes of order at most 9 except the Hughes plane can be constructed from a stepwise transitive MOLR.
|
|
| 10. |
|
|
