| 1. |
- Eriksson, Henrik, et al.
(författare)
-
Sorting a bridge hand
- 2001
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 241:1-3, s. 289-300
-
Tidskriftsartikel (refereegranskat)abstract
- Sorting a permutation by block moves is a task that every bridge player has to solve every time she picks up a new hand of cards. It is also a problem for the computational biologist, for block moves are a fundamental type of mutation that can explain why genes common to two species do not occur in the same order in the chromosome, It is not known whether there exists an optimal sorting procedure running in polynomial time. Bafna and Pevzner gave a polynomial time algorithm that sorts any permutation of length n in at most 3n/4 moves. Our new algorithm improves this to [(2n - 2)/3] for n greater than or equal to 9. For the reverse permutation, we give an exact expression for the number of moves needed, namely [(n + 1)/2]. Computations of Bafha and Pevzner up to n = 10 seemed to suggest that this is the worst case; but as it turns out, a first counterexample occurs for n = 13, i.e. the bridge player's case. Professional card players never sort by rank, only by suit. For this case, we give a complete answer to the optimal sorting problem.
|
|
| 2. |
- Eriksson, Henrik, et al.
(författare)
-
Sorting a bridge hand.
- 2001
-
Ingår i: Discrete Mathematics. - 0012-365X .- 1872-681X. ; 241:1-3, s. 289-300
-
Tidskriftsartikel (refereegranskat)
|
|
| 3. |
- Håstad, Johan, et al.
(författare)
-
A smaller sleeping bag for a baby snake
- 2001
-
Ingår i: Discrete & Computational Geometry. - : Springer Science and Business Media LLC. - 0179-5376 .- 1432-0444. ; 26:1, s. 173-181
-
Tidskriftsartikel (refereegranskat)abstract
- By a sleeping bag for a baby snake in d dimensions we mean a subset of Rd which can cover, by rotation and translation, every curve of unit length. We construct sleeping bags which are smaller than any previously known in dimensions 3 and higher. In particular, we construct a three-dimensional sleeping bag of volume approximately 0.075803. For large d we construct d-dimensional sleeping bags with volume less than (cvlog d)d/d3d/2 for some constant c. To obtain the last result, we show that every curve of unit length in Rd lies between two parallel hyperplanes at distance at most C1d-3/2vlog d, for some constant c1.
|
|
| 4. |
- 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.
|
|
| 5. |
- 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.
|
|
| 6. |
- 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.
|
|
| 7. |
- 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.
|
|
| 8. |
- 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.
|
|
| 9. |
- 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.
|
|
| 10. |
- Eriksson, Henrik, et al.
(författare)
-
Dense packing of patterns in a permutation
- 2007
-
Ingår i: Annals of Combinatorics. - : Springer Science and Business Media LLC. - 0218-0006 .- 0219-3094. ; 11:3-4, s. 459-470
-
Tidskriftsartikel (refereegranskat)abstract
- We study the length L-k of the shortest permutation containing all patterns of length k. We establish the bounds e(-2)k(2) < L-k <= (2/3 + o(1))k(2). We also prove that as k there are permutations of length (1/4+o(1))k(2) containing almost all patterns of length k.
|
|
