Sökning: AMNE:(NATURVETENSKAP Matematik Diskret matematik) >
Avoidability of ran...
Avoidability of random arrays
-
- Andrén, Lina J., 1980- (författare)
- Umeå universitet,Institutionen för matematik och matematisk statistik,Diskret matematik
-
(creator_code:org_t)
- Engelska.
- Relaterad länk:
-
https://urn.kb.se/re...
Abstract
Ämnesord
Stäng
- 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
- NATURVETENSKAP -- Matematik -- Diskret matematik (hsv//swe)
- NATURAL SCIENCES -- Mathematics -- Discrete Mathematics (hsv//eng)
Nyckelord
- Latin square
- avoidable array
- avoidability
- Discrete mathematics
- Diskret matematik
- Mathematics
- matematik
Publikations- och innehållstyp
- vet (ämneskategori)
- ovr (ämneskategori)