@inbook{2369, abstract = {One of the most remarkable recent developments in the study of ultracold Bose gases is the observation of a reversible transition from a Bose Einstein condensate to a state composed of localized atoms as the strength of a periodic, optical trapping potential is varied. In [1] a model of this phenomenon has been analyzed rigorously. The gas is a hard core lattice gas and the optical lattice is modeled by a periodic potential of strength λ. For small λ and temperature Bose- Einstein condensation (BEC) is proved to occur, while at large λ BEC disappears, even in the ground state, which is a Mott-insulator state with a characteristic gap. The inter-particle interaction is essential for this effect. This contribution gives a pedagogical survey of these results.}, author = {Aizenman, Michael and Lieb, Élliott H and Robert Seiringer and Solovej, Jan P and Yngvason, Jakob}, booktitle = {Mathematical Physics of Quantum Mechanics}, editor = {Asch, Joachim and Joye, Alain}, pages = {199 -- 215}, publisher = {Springer}, title = {{Bose-Einstein condensation as a quantum phase transition in an optical lattice}}, doi = {10.1007/b11573432}, volume = {690}, year = {2006}, } @inbook{2416, author = {Bang-Jensen, Jørgen and Reed, Bruce and Schacht, Bruce and Šámal, Robert and Toft, Bjarne and Uli Wagner}, booktitle = {Topics in Discrete Mathematics}, pages = {613 -- 627}, publisher = {Springer}, title = {{On six problems posed by Jarik Nešetřil}}, doi = {10.1007/3-540-33700-8_30}, volume = {26}, year = {2006}, } @article{2430, abstract = {We consider an online version of the conflict-free coloring of a set of points on the line, where each newly inserted point must be assigned a color upon insertion, and at all times the coloring has to be conflict-free, in the sense that in every interval I there is a color that appears exactly once in I. We present deterministic and randomized algorithms for achieving this goal, and analyze their performance, that is, the maximum number of colors that they need to use, as a function of the number n of inserted points. We first show that a natural and simple (deterministic) approach may perform rather poorly, requiring Ω(√̃) colors in the worst case. We then derive two efficient variants of this simple algorithm. The first is deterministic and uses O(log 2 n) colors, and the second is randomized and uses O(log n) colors with high probability. We also show that the O(log 2 n) bound on the number of colors used by our deterministic algorithm is tight on the worst case. We also analyze the performance of the simplest proposed algorithm when the points are inserted in a random order and present an incomplete analysis that indicates that, with high probability, it uses only O(log n) colors. Finally, we show that in the extension of this problem to two dimensions, where the relevant ranges are disks, n colors may be required in the worst case.}, author = {Chent, Ke and Fiat, Amos and Kaplan, Haim and Levy, Meital B and Matoušek, Jiří and Mossel, Elchanan and Pach, János and Sharir, Micha and Smorodinsky, Shakhar and Uli Wagner and Welzl, Emo}, journal = {SIAM Journal on Computing}, number = {5}, pages = {1342 -- 1359}, publisher = {SIAM}, title = {{Online conflict-free coloring for intervals}}, doi = {10.1137/S0097539704446682}, volume = {36}, year = {2006}, } @inproceedings{2431, abstract = {We prove an upper bound, tight up to a factor of 2, for the number of vertices of level at most t in an arrangement of n halfspaces in R , for arbitrary n and d (in particular, the dimension d is not considered constant). This partially settles a conjecture of Eckhoff, Linhart, and Welzl. Up to the factor of 2, the result generalizes McMullen's Upper Bound Theorem for convex polytopes (the case ℓ = O) and extends a theorem of Linhart for the case d ≤ 4. Moreover, the bound sharpens asymptotic estimates obtained by Clarkson and Shor. The proof is based on the h-matrix of the arrangement (a generalization, introduced by Mulmuley, of the h-vector of a convex polytope). We show that bounding appropriate sums of entries of this matrix reduces to a lemma about quadrupels of sets with certain intersection properties, and we prove this lemma, up to a factor of 2, using tools from multilinear algebra. This extends an approach of Alon and Kalai, who used linear algebra methods for an alternative proof of the classical Upper Bound Theorem. The bounds for the entries of the h-matrix also imply bounds for the number of i-dimensional faces, i > 0, at level at most ℓ. Furthermore, we discuss a connection with crossing numbers of graphs that was one of the main motivations for investigating exact bounds that are valid for arbitrary dimensions.}, author = {Uli Wagner}, pages = {635 -- 645}, publisher = {IEEE}, title = {{On a geometric generalization of the Upper Bound Theorem}}, doi = {10.1109/FOCS.2006.53}, year = {2006}, } @article{2429, abstract = {We show, with an elementary proof, that the number of halving simplices in a set of n points in 4 in general position is O(n4-2/45). This improves the previous bound of O(n4-1/134). Our main new ingredient is a bound on the maximum number of halving simplices intersecting a fixed 2-plane. }, author = {Matoušek, Jiří and Sharir, Micha and Smorodinsky, Shakhar and Uli Wagner}, journal = {Discrete & Computational Geometry}, number = {2}, pages = {177 -- 191}, publisher = {Springer}, title = {{K-sets in four dimensions}}, doi = {10.1007/s00454-005-1200-4}, volume = {35}, year = {2006}, }