| 1. |
- Angel, O., et al.
(författare)
-
THE PHASE TRANSITION FOR DYADIC TILINGS
- 2014
-
Ingår i: Transactions of the American Mathematical Society. - 0002-9947 .- 1088-6850. ; 366:2, s. 1029-1046
-
Tidskriftsartikel (refereegranskat)abstract
- A dyadic tile of order n is any rectangle obtained from the unit square by n successive bisections by horizontal or vertical cuts. Let each dyadic tile of order n be available with probability p, independent of the others. We prove that for p sufficiently close to 1, there exists a set of pairwise disjoint available tiles whose union is the unit square, with probability tending to 1 as n -> infinity, as conjectured by Joel Spencer in 1999. In particular, we prove that if p = 7/8, such a tiling exists with probability at least 1 - (3/4)(n). The proof involves a surprisingly delicate counting argument for sets of unavailable tiles that prevent tiling.
|
|
| 2. |
- Basu, Riddhipratim, et al.
(författare)
-
Trapping games on random boards
- 2016
-
Ingår i: Annals of Applied Probability. - 1050-5164. ; 26:6, s. 3727-3753
-
Tidskriftsartikel (refereegranskat)abstract
- © Institute of Mathematical Statistics, 2016.We consider the following two-player game on a graph. A token is located at a vertex, and the players take turns to move it along an edge to a vertex that has not been visited before. A player who cannot move loses. We analyze outcomes with optimal play on percolation clusters of Euclidean lattices. On Z2 with two different percolation parameters for odd and even sites, we prove that the game has no draws provided closed sites of one parity are sufficiently rare compared with those of the other parity (thus favoring one player). We prove this also for certain d-dimensional lattices with d ≥ 3. It is an open question whether draws can occur when the two parameters are equal. On a finite ball of Z2, with only odd sites closed but with the external boundary consisting of even sites, we identify up to logarithmic factors a critical window for the trade-off between the size of the ball and the percolation parameter. Outside this window, one or the other player has a decisive advantage. Our analysis of the game is intimately tied to the effect of boundary conditions on maximum-cardinality matchings.
|
|
| 3. |
- Eriksen, Niklas, 1974, et al.
(författare)
-
Enumeration of derangements with descents in prescribed positions
- 2009
-
Ingår i: Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1077-8926 .- 1097-1440. ; 16:1
-
Tidskriftsartikel (refereegranskat)abstract
- We enumerate derangements with descents in prescribed positions. A generating function was given by Guo-Niu Han and Guoce Xin in 2007. We give a combinatorial proof of this result, and derive several explicit formulas. To this end, we consider fixed point $\lambda$-coloured permutations, which are easily enumerated. Several formulae regarding these numbers are given, as well as a generalisation of Euler's difference tables. We also prove that except in a trivial special case, if a permutation $\pi$ is chosen uniformly among all permutations on $n$ elements, the events that $\pi$ has descents in a set $S$ of positions, and that $\pi$ is a derangement, are positively correlated.
|
|
| 4. |
- Franzen, Bjorn, et al.
(författare)
-
Where to stand when playing darts?
- 2021
-
Ingår i: Alea. - 1980-0436. ; 18:1, s. 1561-1583
-
Tidskriftsartikel (refereegranskat)abstract
- This paper analyzes the question of where one should stand when playing darts. If one stands at distance d>0 and aims at a in R^n, then the dart (modelled by a random vector X in R^n hits a random point given by a+dX. Next, given a payoff function f, one considers sup_a Ef(a+dX) and asks if this is decreasing in d; i.e., whether it is better to stand closer rather than farther from the target. Perhaps surprisingly, this is not always the case and understanding when this does or does not occur is the purpose of this paper. We show that if X has a so-called selfdecomposable distribution, then it is always better to stand closer for any payoff function. This class includes all stable distributions as well as many more. On the other hand, if the payoff function is cos(x), then it is always better to stand closer if and only if the characteristic function |phi_X(t)| is decreasing on [0,infty). We will then show that if there are at least two point masses, then it is not always better to stand closer using cos(x). If there is a single point mass, one can find a different payoff function to obtain this phenomenon. Another large class of darts X for which there are bounded continuous payoff functions for which it is not always better to stand closer are distributions with compact support. This will be obtained by using the fact that the Fourier transform of such distributions has a zero in the complex plane. This argument will work whenever there is a complex zero of the Fourier transform. Finally, we analyze if the property of it being better to stand closer is closed under convolution and/or limits.
|
|
| 5. |
- Freij, Ragnar, 1984, et al.
(författare)
-
Partially ordered secretaries
- 2010
-
Ingår i: Electronic Communications in Probability. - 1083-589X. ; 15, s. 504-507
-
Tidskriftsartikel (refereegranskat)abstract
- The elements of a finite nonempty partially ordered set are exposed at independent uniform times in [0, 1] to a selector who, at any given time, can see the structure of the induced partial order on the exposed elements. The selector’s task is to choose online a maximal element. This generalizes the classical linear order secretary problem, for which it is known that the selector can succeed with probability 1=e and that this is best possible. We describe a strategy for the general problem that achieves success probability at least 1=e for an arbitrary partial order.
|
|
| 6. |
- Hessler, Martin, et al.
(författare)
-
Edge cover and polymatroid flow problems
- 2010
-
Ingår i: Electronic Journal of Probability. - : Institute of Mathematical Statistics. - 1083-6489. ; 15, s. 2200-2219
-
Tidskriftsartikel (refereegranskat)abstract
- In an n by n complete bipartite graph with independent exponentially distributed edge costs, we ask for the minimum total cost of a set of edges of which each vertex is incident to at least one. This so-called minimum edge cover problem is a relaxation of perfect matching. We show that the large n limit cost of the minimum edge cover is W(1)(2) + 2W(1) approximate to 1.456, where W is the Lambert W-function. In particular this means that the minimum edge cover is essentially cheaper than the minimum perfect matching, whose limit cost is pi(2)/6 approximate to 1.645. We obtain this result through a generalization of the perfect matching problem to a setting where we impose a (poly-)matroid structure on the two vertex-sets of the graph, and ask for an edge set of prescribed size connecting independent sets.
|
|
| 7. |
- 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.
|
|
| 8. |
|
|
| 9. |
- Larsson, Urban, 1965, et al.
(författare)
-
From heaps of matches to the limits of computability
- 2013
-
Ingår i: Electronic Journal of Combinatorics. - : The Electronic Journal of Combinatorics. - 1077-8926 .- 1097-1440. ; 20:3
-
Tidskriftsartikel (refereegranskat)abstract
- We study so-called invariant games played with a fixed number d of heaps of matches. A game is described by a finite list M of integer vectors of length d specifying the legal moves. A move consists in changing the current game-state by adding one of the vectors in M, provided all elements of the resulting vector are nonnegative. For instance, in a two-heap game, the vector (1, -2) would mean adding one match to the first heap and removing two matches from the second heap. If (1, -2) is an element of M, such a move would be permitted provided there are at least two matches in the second heap. Two players take turns, and a player unable to make a move loses. We show that these games embrace computational universality, and that therefore a number of basic questions about them are algorithmically undecidable. In particular, we prove that there is no algorithm that takes two games M and M' (with the same number of heaps) as input, and determines whether or not they are equivalent in the sense that every starting-position which is a first player win in one of the games is a first player win in the other.
|
|
| 10. |
- Larsson, Urban, 1965, et al.
(författare)
-
Maharaja Nim
- 2013
-
Tidskriftsartikel (övrigt vetenskapligt/konstnärligt)abstract
- We relax the hypothesis of a recent result of A. S. Fraenkel and U. Peled on certain complementary sequences of positive integers. The motivation is to understand to asymptotic behavior of the impartial game of \emph{Maharaja Nim}, an extension of the classical game of Wythoff Nim. In the latter game, two players take turn in moving a single Queen of Chess on a large board, attempting to be the first to put her in the lower left corner, position $(0,0)$. Here, in addition to the classical rules, a player may also move the Queen as the Knight of Chess moves, still taking into consideration that, by moving no coordinate increases. We prove that the second player's winning positions are close to those of Wythoff Nim, namely they are within a bounded distance to the half-lines, starting at the origin, of slope $\frac{\sqrt{5}+1}{2}$ and $\frac{\sqrt{5}-1}{2}$ respectively. We encode the patterns of the P-positions by means of a certain \emph{dictionary process}, thus introducing a new method for analyzing games related to Wythoff Nim. Via Post's Tag productions, we also prove that, in general, such dictionary processes are algorithmically undecidable.
|
|
