| 11. |
- Andrén, Lina J., 1980-
(författare)
-
Avoiding (m, m, m)-arrays of order n = 2k
-
Annan publikation (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 12. |
- Andrén, Lina J., 1980-
(författare)
-
On Latin squares and avoidable arrays
- 2010
-
Doktorsavhandling (övrigt vetenskapligt/konstnärligt)abstract
- 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.
|
|
| 13. |
|
|
| 14. |
|
|
| 15. |
-
Discrete Geometry and Mathematical Morphology : First International Joint Conference, DGMM 2021, Uppsala, Sweden, May 24–27, 2021, Proceedings
- 2021
-
Samlingsverk (redaktörskap) (refereegranskat)abstract
- This book constitutes the proceedings of the First IAPR International Conference on Discrete Geometry and Mathematical Morphology, DGMM 2021, which was held during May 24-27, 2021, in Uppsala, Sweden.The conference was created by joining the International Conference on Discrete Geometry for computer Imagery, DGCI, with the International Symposium on Mathematical Morphology, ISMM.The 36 papers included in this volume were carefully reviewed and selected from 59 submissions. They were organized in topical sections as follows: applications in image processing, computer vision, and pattern recognition; discrete and combinatorial topology; discrete geometry - models, transforms, visualization; discrete tomography and inverse problems; hierarchical and graph-based models, analysis and segmentation; learning-based approaches to mathematical morphology; multivariate and PDE-based mathematical morphology, morphological filtering.The book also contains 3 invited keynote papers.
|
|
| 16. |
- Ekedahl, Torsten, 1955-
(författare)
-
Shellability of a Poset of Polygonal Subdivisions
- 2009
-
Ingår i: The Electronic Journal of Combinatorics. - : Annals of Mathematics. - 1097-1440 .- 1077-8926. ; 16:2, s. R23-
-
Tidskriftsartikel (refereegranskat)
|
|
| 17. |
- Fleischner, Herbert, et al.
(författare)
-
Circuit double covers in special types of cubic graphs
- 2009
-
Ingår i: Discrete Mathematics. - : Elsevier BV. - 0012-365X .- 1872-681X. ; 309:18, s. 5724-5728
-
Tidskriftsartikel (refereegranskat)abstract
- Suppose that a 2-connected cubic graph G of order n has a circuit C of length at least n−4 such that G−V(C) is connected. We show that G has a circuit double cover containing a prescribed set of circuits which satisfy certain conditions. It follows that hypohamiltonian cubic graphs (i.e., non-hamiltonian cubic graphs G such that G−v is hamiltonian for every v∈V(G)) have strong circuit double covers.
|
|
| 18. |
|
|
| 19. |
- Holmgren, Cecilia, 1984-, et al.
(författare)
-
Branching Markov chains: Stability and Applications
-
Annan publikation (populärvet., debatt m.m.)abstract
- We address the stability of certain tree algorithms used to solve the problem of communication between multiple users through a unique shared channel. We propose a general model based on branching Markov chains which allows us to write an intuitive stability condition. When the algorithm is stable, we show that there exist an asymptotic throughput, which is related to the asymptotic size of the underlying tree.
|
|
| 20. |
- Holmgren, Cecilia, 1984-
(författare)
-
Novel Characteristics of Split Trees by use of Renewal Theory
- 2012
-
Ingår i: Electronic Journal of Probability. - 1083-6489. ; 17, s. 5-
-
Tidskriftsartikel (refereegranskat)abstract
- We investigate characteristics of random split trees introduced by Devroye [SIAM J Comput 28, 409-432, 1998]; split trees include e. g., binary search trees, m-ary search trees, quadtrees, median of (2k + 1)-trees, simplex trees, tries and digital search trees. More precisely: We use renewal theory in the studies of split trees, and use this theory to prove several results about split trees. A split tree of cardinality n is constructed by distributing n balls (which often represent data) to a subset of nodes of an infinite tree. One of our main results is a relation between the deterministic number of balls n and the random number of nodes N. In [5] there is a central limit law for the depth of the last inserted ball so that most nodes are close to depth lnn/mu + O(root lnn), where mu is some constant depending on the type of split tree; we sharpen this result by finding an upper bound for the expected number of nodes with depths >= lnn/mu - ln(1/2+epsilon) n or depths <= lnn/mu + ln(1/2+epsilon) n for any choice of epsilon > 0. We also find the first asymptotic of the variances of the depths of the balls in the tree.
|
|
