Sökning: onr:"swepub:oai:DiVA.org:umu-36024" >
Avoidability of ran...
-
Andrén, Lina J.,1980-Umeå universitet,Institutionen för matematik och matematisk statistik,Diskret matematik
(författare)
Avoidability of random arrays
Förlag, utgivningsår, omfång ...
Nummerbeteckningar
-
LIBRIS-ID:oai:DiVA.org:umu-36024
-
https://urn.kb.se/resolve?urn=urn:nbn:se:umu:diva-36024URI
Kompletterande språkuppgifter
-
Språk:engelska
-
Sammanfattning på:engelska
Ingår i deldatabas
Klassifikation
-
Ämneskategori:vet swepub-contenttype
-
Ämneskategori:ovr swepub-publicationtype
Anmärkningar
-
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.
Ämnesord och genrebeteckningar
Biuppslag (personer, institutioner, konferenser, titlar ...)
-
Umeå universitetInstitutionen för matematik och matematisk statistik
(creator_code:org_t)
Internetlänk