| 1. |
|
|
| 2. |
- Holroyd, Alexander E., et al.
(författare)
-
Minimal matchings of point processes
- 2022
-
Ingår i: Probability Theory and Related Fields. - : Springer Science and Business Media LLC. - 0178-8051 .- 1432-2064. ; 184:1-2, s. 571-611
-
Tidskriftsartikel (refereegranskat)abstract
- Suppose that red and blue points form independent homogeneous Poisson processes of equal intensity in R-d. For a positive (respectively, negative) parameter gamma we consider red-blue matchings that locally minimize (respectively, maximize) the sum of gamma th powers of the edge lengths, subject to locally minimizing the number of unmatched points. The parameter can be viewed as a measure of fairness. The limit gamma -> -infinity is equivalent to Gale-Shapley stable matching. We also consider limits as gamma approaches 0, 1-, 1+ and infinity. We focus on dimension d = 1. We prove that almost surely no such matching has unmatched points. (This question is open for higher d). For each gamma < 1 we establish that there is almost surely a unique such matching, and that it can be expressed as a finitary factor of the points. Moreover, its typical edge length has finite rth moment if and only if r < 1 /2. In contrast, for gamma = 1 there are uncountably many matchings, while for gamma > 1 there are countably many, but it is impossible to choose one in a translation-invariant way. We obtain existence results in higher dimensions (covering many but not all cases). We address analogous questions for one-colour matchings also.
|
|
| 3. |
- Brill, Markus, et al.
(författare)
-
Phragmén's voting methods and justified representation
- 2024
-
Ingår i: Mathematical programming. - : Springer. - 0025-5610 .- 1436-4646. ; 203:1-2, s. 47-76
-
Tidskriftsartikel (refereegranskat)abstract
- In the late 19th century, Swedish mathematician Edvard Phragmén proposed a load-balancing approach for selecting committees based on approval ballots. We consider three committee voting rules resulting from this approach: two optimization variants—one minimizing the maximum load and one minimizing the variance of loads—and a sequential variant. We study Phragmén's methods from an axiomatic point of view, focusing on properties capturing proportional representation. We show that the sequential variant satisfies proportional justified representation, which is a rare property for committee monotonic methods. Moreover, we show that the optimization variants satisfy perfect representation. We also analyze the computational complexity of Phragmén's methods and provide mixed-integer programming based algorithms for computing them.
|
|
| 4. |
- Janson, Svante, 1955-, et al.
(författare)
-
A modified bootstrap percolation on a random graph coupled with a lattice
- 2019
-
Ingår i: Discrete Applied Mathematics. - : Elsevier BV. - 0166-218X .- 1872-6771. ; 258, s. 152-165
-
Tidskriftsartikel (refereegranskat)abstract
- In this paper a random graph model G(ZN2.pd) is introduced, which is a combination of fixed torus grid edges in (z/NZ)(2) and some additional random ones. The random edges are called long, and the probability of having a long edge between vertices u, v is an element of (Z/NZ)(2) with graph distance d on the torus grid is p(d) = c/Nd, where c is some constant. We show that, whp, the diameter D(G(zN2.pd)) = Theta(log N). Moreover, we consider a modified non-monotonous bootstrap percolation on G(ZN2.pd). We prove the presence of phase transitions in mean-field approximation and provide Fairly sharp bounds on the error of the critical parameters.
|
|
| 5. |
- Janson, Svante, 1955-
(författare)
-
A graphon counter example
- 2020
-
Ingår i: Discrete Mathematics. - : ELSEVIER. - 0012-365X .- 1872-681X. ; 343:6
-
Tidskriftsartikel (refereegranskat)abstract
- We give an example of a graphon such that there is no equivalent graphon with a degree function that is (weakly) increasing.
|
|
| 6. |
- Janson, Svante, 1955-
(författare)
-
On convergence for graphexes
- 2022
-
Ingår i: European journal of combinatorics (Print). - : Elsevier. - 0195-6698 .- 1095-9971. ; 104
-
Tidskriftsartikel (refereegranskat)abstract
- We study four different notions of convergence for graphexes, recently introduced by Borgs, Chayes, Cohn and Holden, and by Veitch and Roy. We give some properties of them and some relations between them. We also extend results by Veitch and Roy on convergence of empirical graphons.
|
|
| 7. |
- Janson, Svante, 1955-
(författare)
-
Patterns in Random Permutations Avoiding Some Sets of Multiple Patterns
- 2020
-
Ingår i: Algorithmica. - : SPRINGER. - 0178-4617 .- 1432-0541. ; 82:3, s. 616-641
-
Tidskriftsartikel (refereegranskat)abstract
- We consider a random permutation drawn from the set of permutations of length n that avoid some given set of patterns of length 3. We show that the number of occurrences of another pattern sigma has a limit distribution, after suitable scaling. In several cases, the number is asymptotically normal; this contrasts to the cases of permutations avoiding a single pattern of length 3 studied in earlier papers.
|
|
| 8. |
- Janson, Svante, 1955-
(författare)
-
The number of occurrences of patterns in a random tree or forest permutation
- 2023
-
Ingår i: The Electronic Journal of Combinatorics. - : ELECTRONIC JOURNAL OF COMBINATORICS. - 1097-1440 .- 1077-8926. ; 30:2
-
Tidskriftsartikel (refereegranskat)abstract
- The classes of tree permutations and forest permutations were defined by Acan and Hitczenko (2016). We study random permutations of a given length from these classes, and in particular the number of occurrences of a fixed pattern in one of these random permutations. The main results show that the distributions of these numbers are asymptotically normal. The proof uses representations of random tree and forest permutations that enable us to express the number of occurrences of a pattern by a type of U-statistics; we then use general limit theorems for the latter.
|
|
