| 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. |
|
|
| 5. |
- 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.
|
|
| 6. |
- Angulo, Julio, 1980-, et al.
(författare)
-
What Would It Take for You to Tell Your Secrets to a Cloud? : Studying decision factors when disclosing information to cloud services
- 2014
-
Ingår i: Secure IT Systems. - Cham : Springer. - 9783319115993 ; , s. 129-145
-
Konferensbidrag (refereegranskat)abstract
- We investigate the end users’ behaviours and attitudes with regards to the control they place in the personal information that they disclose to cloud storage services. Three controlled experiments were carried out to study the influence in users’ decisions to retain or surrender control over their personal information depending on different factors. The results of these experiments reveal, among other things, the users’ willingness to surrender control over personal information that is perceived as non-sensitive in exchange for valuable rewards, and that users would value the possibility of knowing and controlling the parties who are granted access to their data in the cloud. Based on the results from the experiments we provide implications for the design of end-user tools that can promote transparency and accountability in cloud computing environments.
|
|
| 7. |
- 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.
|
|
| 8. |
- 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.
|
|
| 9. |
- 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.
|
|
| 10. |
- 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.
|
|
