umu.sePublications
Change search
Link to record
Permanent link

Direct link
BETA
Jansson Andren, Lina
Alternative names
Publications (8 of 8) Show all publications
Andren, L. J., Casselgren, C. J. & Öhman, L.-D. (2013). Avoiding Arrays of Odd Order by Latin Squares. Combinatorics, probability & computing, 22(2), 184-212
Open this publication in new window or tab >>Avoiding Arrays of Odd Order by Latin Squares
2013 (English)In: Combinatorics, probability & computing, ISSN 0963-5483, E-ISSN 1469-2163, Vol. 22, no 2, p. 184-212Article in journal (Refereed) Published
Abstract [en]

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 <= 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 -> infinity.

National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-66768 (URN)10.1017/S0963548312000570 (DOI)000314296400002 ()
Available from: 2013-03-15 Created: 2013-03-05 Last updated: 2018-06-08Bibliographically approved
Riener, C., Theobald, T., Jansson Andren, L. & Lasserre, J. B. (2013). Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization. Mathematics of Operations Research, 38(1), 122-141
Open this publication in new window or tab >>Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization
2013 (English)In: Mathematics of Operations Research, ISSN 0364-765X, E-ISSN 1526-5471, Vol. 38, no 1, p. 122-141Article in journal (Refereed) Published
Abstract [en]

In this paper we study various approaches for exploiting symmetries in polynomial optimization problems within the framework of semidefinite programming relaxations. Our special focus is on constrained problems especially when the symmetric group is acting on the variables. In particular, we investigate the concept of block decomposition within the framework of constrained polynomial optimization problems, show how the degree principle for the symmetric group can be computationally exploited, and also propose some methods to efficiently compute the geometric quotient.

Keywords
polynomial optimization, semidefinite programming, semidefinite relaxation symmetry, symmetric group, constrained optimization
National Category
Discrete Mathematics
Identifiers
urn:nbn:se:umu:diva-67602 (URN)10.1287/moor.1120.0558 (DOI)000315190000006 ()
Available from: 2013-06-03 Created: 2013-03-25 Last updated: 2018-06-08Bibliographically approved
Andrén, L. J. (2012). Avoiding (m, m, m)-arrays of order n=2(k). The Electronic Journal of Combinatorics, 19(1), P63
Open this publication in new window or tab >>Avoiding (m, m, m)-arrays of order n=2(k)
2012 (English)In: The Electronic Journal of Combinatorics, ISSN 1097-1440, E-ISSN 1077-8926, Vol. 19, no 1, p. P63-Article in journal (Refereed) Published
Abstract [en]

An (m, m, m)-array of order n is an n x n array such that each cell is assigned a set of at most m symbols from f 1,...,n g such that no symbol occurs more than m times in any row or column. An (m, m, m)-array is called avoidable if there exists a Latin square such that no cell in the Latin square contains a symbol that also belongs to the set assigned to the corresponding cell in the array. We show that there is a constant gamma such that if m <= gamma 2(k) and k >= 14, then any (m, m, m)-array of order n = 2(k) is avoidable. Such a constant gamma has been conjectured to exist for all n by Haggkvist.

National Category
Mathematics
Identifiers
urn:nbn:se:umu:diva-55037 (URN)000302381200004 ()
Available from: 2012-05-07 Created: 2012-05-07 Last updated: 2018-06-08Bibliographically approved
Andrén, L. J. (2010). On Latin squares and avoidable arrays. (Doctoral dissertation). Umeå: Umeå universitet, Instituionen för matematik och matematisk statisitik
Open this publication in new window or tab >>On Latin squares and avoidable arrays
2010 (English)Doctoral thesis, comprehensive summary (Other academic)
Abstract [en]

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.

Abstract [sv]

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.

Place, publisher, year, edition, pages
Umeå: Umeå universitet, Instituionen för matematik och matematisk statisitik, 2010. p. 31
Series
Doctoral thesis / Umeå University, Department of Mathematics, ISSN 1102-8300 ; 46
Keywords
Latin square, avoidability, avoidable array
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-36040 (URN)978-91-7459-060-9 (ISBN)
Public defence
2010-10-07, MA121, MIT-huset, Umeå universitet, Umeå, 11:04 (Swedish)
Opponent
Supervisors
Available from: 2010-09-16 Created: 2010-09-15 Last updated: 2018-06-08Bibliographically approved
Andrén, L. J.Avoidability by Latin squares of arrays of even order.
Open this publication in new window or tab >>Avoidability by Latin squares of arrays of even order
(English)Manuscript (preprint) (Other academic)
Abstract [en]

We prove that for any k and any 2k × 2k array A such that no cell in A contains more than   k/2550 symbols, and no symbol occurs more than k/2550 times in any row or column, there is a Latin square such that no 2550cell in the Latin square contains a symbol that occurs in the corresponding cell in A. This proves a conjecture of Häggkvist [8] in the special case of arrays with even side.

Keywords
Latin square, avoidability, avoidable array
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-36025 (URN)
Available from: 2010-09-15 Created: 2010-09-14 Last updated: 2018-06-08Bibliographically approved
Andrén, L. J.Avoidability of random arrays.
Open this publication in new window or tab >>Avoidability of random arrays
(English)Manuscript (preprint) (Other academic)
Abstract [en]

An n×n array that in each cell contains a subset of the symbols 1, . . . , n is avoidable if there exists a Latin square of order n such that no cell in the Latin square contains a symbol which belongs to the set of symbols in the corresponding cell of the array. Some results on deterministic conditions for avoidability of arrays have been found, but here we study the problem of having an array with randomly assigned subsets of C in its cells. This is equivalent to the problem of list-edge-coloring  with randomly assigned lists from the set {1, . . . , n}. We show that an array where each symbol appears in each cell with probability p will be avoidable with very high probability even if p is such that the expected number of symbols forbidden in each cell is slightly higher than what deterministic theorems can prove is avoidable.

Keywords
Latin square, avoidable array, avoidability
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-36024 (URN)
Available from: 2010-09-15 Created: 2010-09-14 Last updated: 2018-06-08Bibliographically approved
Andrén, L. J., Casselgren, C. J. & Öhman, L.-D.Avoiding arrays of odd order by Latin squares.
Open this publication in new window or tab >>Avoiding arrays of odd order by Latin squares
(English)Manuscript (preprint) (Other academic)
Abstract [en]

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.

Keywords
Latin square, avoidability, avoidable array
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-36026 (URN)
Available from: 2010-09-15 Created: 2010-09-14 Last updated: 2018-06-08Bibliographically approved
Andrén, L. J.Avoiding (m, m, m)-arrays of order n = 2k.
Open this publication in new window or tab >>Avoiding (m, m, m)-arrays of order n = 2k
(English)Manuscript (preprint) (Other academic)
Abstract [en]

An (m, m, m)-array of order n is an n × n array such that each cell is assigned a set of at most m symbols from {1,...,n} such that no symbol occurs more than m times in any row or column. An (m,m,m)- array is called avoidable if there exists a Latin square such that no cell in the Latin square contains a symbol that also belongs to the set assigned to the corresponding cell in the array. We show that there is a constant γ such that if m ≤ γ2k, then any (m,m,m)-array of order 2k is avoidable. Such a constant γ has been conjectured to exist for all n by Häggkvist.

Keywords
Latin square, avoidability, avoidable array
National Category
Discrete Mathematics
Research subject
Mathematics
Identifiers
urn:nbn:se:umu:diva-36023 (URN)
Available from: 2010-09-15 Created: 2010-09-14 Last updated: 2018-06-08Bibliographically approved
Organisations

Search in DiVA

Show all publications