𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Intersecting random half cubes

✍ Scribed by Michel Talagrand

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
139 KB
Volume
15
Category
Article
ISSN
1042-9832

No coin nor oath required. For personal study only.

✦ Synopsis

We provide the discrete cube Q N = -1 1 N with its uniform probability, and we consider an independent sequence ΞΎ 1 ΞΎ N uniformly distributed on Q N . Kim and Roche recently proved that there exists Ξ΅ > 0 such that the probability that there exists (resp. does not exist) a point x of Q N with ΞΎ k β€’ x β‰₯ 0 for all k ≀ Ξ΅N (resp. k ≀ 1 -Ξ΅ N goes to 1 (resp. 0) as N β†’ ∞. We use ideas from statistical mechanics to provide simpler proofs of stronger results.

πŸ“œ SIMILAR VOLUMES

Covering Cubes by Random Half Cubes, wit
Covering Cubes by Random Half Cubes, with Applications to Binary Neural Networks
✍ Jeong Han Kim; James R. Roche πŸ“‚ Article πŸ“… 1998 πŸ› Elsevier Science 🌐 English βš– 650 KB

Let Q n be the (hyper)cube [&1, 1] n . This paper is concerned with the following question: How many vectors must be chosen uniformly and independently at random from Q n before every vector in Q n itself has negative inner product with at least one of the random vectors? For any fixed =>0, a simple

Random packings by cubes
Random packings by cubes
✍ Alexey P. Poyarkov πŸ“‚ Article πŸ“… 2007 πŸ› Springer US 🌐 English βš– 110 KB
Random Induced Subgraphs of Generalizedn
Random Induced Subgraphs of Generalizedn-Cubes
✍ Christian M. Reidys πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 312 KB

vertices are adjacent if they differ in exactly one coordinate. Random induced subgraphs, . with probability . The first theorem shows that for s c ln n rn there exists n n a unique largest component in ⌫ -Q Q n which contains almost all vertices and that n ␣ Ž . the size of the second largest comp