skip to main content
US FlagAn official website of the United States government
dot gov icon
Official websites use .gov
A .gov website belongs to an official government organization in the United States.
https lock icon
Secure .gov websites use HTTPS
A lock ( lock ) or https:// means you've safely connected to the .gov website. Share sensitive information only on official, secure websites.


Title: On Edge-Disjoint Spanning Trees in a Randomly Weighted Complete Graph
Assume that the edges of the complete graph K n are given independent uniform [0, 1] weights. We consider the expected minimum total weight μ k of k ⩽ 2 edge-disjoint spanning trees. When k is large we show that μ k ≈ k 2 . Most of the paper is concerned with the case k = 2. We show that m 2 tends to an explicitly defined constant and that μ 2 ≈ 4.1704288. . . .  more » « less
Award ID(s):
1661063
PAR ID:
10054180
Author(s) / Creator(s):
;
Date Published:
Journal Name:
Combinatorics, Probability and Computing
Volume:
27
Issue:
02
ISSN:
0963-5483
Page Range / eLocation ID:
228 to 244
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. In adaptive importance sampling and other contexts, we haveK> 1 unbiased and uncorrelated estimates μ^kof a common quantity μ. The optimal unbiased linear combination weights them inversely to their variances, but those weights are unknown and hard to estimate. A simple deterministic square root rule based on a working model that Var(μ^k) ∝k−1/2gives an unbiased estimate of μ that is nearly optimal under a wide range of alternative variance patterns. We show that if Var(μ^k)∝k−yfor an unknown rate parametery∈[0,1], then the square root rule yields the optimal variance rate with a constant that is too large by at most 9/8 for any 0 ⩽y⩽ 1 and any numberKof estimates. Numerical work shows that rule is similarly robust to some other patterns with mildly decreasing variance askincreases. 
    more » « less
  2. Private information retrieval (PIR) allows a user to retrieve a desired message out of K possible messages from N databases without revealing the identity of the desired message. There has been significant recent progress on understanding fundamental information-theoretic limits of PIR, and in particular the download cost of PIR for several variations. Majority of existing works however, assume the presence of replicated databases, each storing all the K messages. In this work, we consider the problem of PIR from storage constrained databases. Each database has a storage capacity of μKL bits, where K is the number of messages, L is the size of each message in bits, and μ ∈ [1/N, 1] is the normalized storage. In the storage constrained PIR problem, there are two key design questions: a) how to store content across each database under storage constraints; and b) construction of schemes that allow efficient PIR through storage constrained databases. The main contribution of this work is a general achievable scheme for PIR from storage constrained databases for any value of storage. In particular, for any (N, K), with normalized storage μ = t/N, where the parameter t can take integer values t ∈ {1, 2, ..., N}, we show that our proposed PIR scheme achieves a download cost of (1 + 1/t + 1/2 + ⋯ + 1/t K-1 ). The extreme case when μ = 1 (i.e., t = N) corresponds to the setting of replicated databases with full storage. For this extremal setting, our scheme recovers the information-theoretically optimal download cost characterized by Sun and Jafar as (1 + 1/N + ⋯ +1/N K-1 ). For the other extreme, when μ = 1/N (i.e., t = 1), the proposed scheme achieves a download cost of K. The most interesting aspect of the result is that for intermediate values of storage, i.e., 1/N <; μ <; 1, the proposed scheme can strictly outperform memory-sharing between extreme values of storage. 
    more » « less
  3. Six salts ([Au2(μ-dppe)2](BF4)2·CHCl3, [Au2(μ- dppe)2](BF4)2·1,2-Cl2C2H4, [Au2(μ-dppe)2](PF6)2·CHCl3, [Au2(μ-dppe)2](PF6)2, [Au2(μ-dppe)2](SbF6)2, and [Au2(μ- dppe)2](OTf)2·2CHCl3), (dppe is bis(diphenylphosphine)ethane) containing the dication, [Au2(μ-dppe)2]2+, have been prepared and structurally characterized by single-crystal X-ray crystallography. Unlike the three-coordinate dppe-bridged dimers, Au2X2(μ-dppe)2 (X = Br, I), which show considerable variation in the distance between the gold(I) ions over the range 3.0995(10) to 3.8479(3) Å in various solvates, the structure of the helical dication, [Au2(μ- dppe)2], in the new salts is remarkably consistent with the Au···Au separation falling in the narrow range 2.8787(9) to 2.9593(5) Å. In the solid state, the six crystals display a green luminescence both at room temperature and at 77 K, which has been assigned as phosphorescence. However, solutions of the dication are not luminescent. Salts containing the analogous dication [Au2(μ-dppp)2](PF6)2 (dppp is bis(diphenylphosphine)propane) have been prepared to determine whether the longer bridging ligand might also twist into a helical shape. These salts include [Au2(μ- dppp)2](OTf)2 (OTf is triflate) and three crystalline forms of [Au2(μ-dppp)2](PF6)2: the solvate [Au2(μ-dppp)2](PF6)2·(CHCl3) and two polymorphs of the unsolvated salt. None of these crystals are luminescent, but all contain a similar dication, [Au2(μ- dppp)2]2+, that contains two nearly parallel, linear P−Au−P groups and a long separation between the gold ions that varies from 5.3409(4) to 5.6613(6)Å. 
    more » « less
  4. Addition of [UI 2 (THF) 3 (μ-OMe)] 2 ·THF (2·THF) to THF solutions containing 6 equiv. of K[C 14 H 10 ] generates the heteroleptic dimeric complexes [K(18-crown-6)(THF) 2 ] 2 [U(η 6 -C 14 H 10 )(η 4 -C 14 H 10 )(μ-OMe)] 2 ·4THF (118C6·4THF) and {[K(THF) 3 ][U(η 6 -C 14 H 10 )(η 4 -C 14 H 10 )(μ-OMe)]} 2 (1THF) upon crystallization of the products in THF in the presence or absence of 18-crown-6, respectively. Both 118C6·4THF and 1THF are thermally stable in the solid-state at room temperature; however, after crystallization, they become insoluble in THF or DME solutions and instead gradually decompose upon standing. X-ray diffraction analysis reveals 118C6·4THF and 1THF to be structurally similar, possessing uranium centres sandwiched between bent anthracenide ligands of mixed tetrahapto and hexahapto ligation modes. Yet, the two complexes are distinguished by the close contact potassium-arenide ion pairing that is seen in 1THF but absent in 118C6·4THF, which is observed to have a significant effect on the electronic characteristics of the two complexes. Structural analysis, SQUID magnetometry data, XANES spectral characterization, and computational analyses are generally consistent with U( iv ) formal assignments for the metal centres in both 118C6·4THF and 1THF, though noticeable differences are detected between the two species. For instance, the effective magnetic moment of 1THF (3.74 μ B ) is significantly lower than that of 118C6·4THF (4.40 μ B ) at 300 K. Furthermore, the XANES data shows the U L III -edge absorption energy for 1THF to be 0.9 eV higher than that of 118C6·4THF, suggestive of more oxidized metal centres in the former. Of note, CASSCF calculations on the model complex {[U(η 6 -C 14 H 10 )(η 4 -C 14 H 10 )(μ-OMe)] 2 } 2− (1*) shows highly polarized uranium–arenide interactions defined by π-type bonds where the metal contributions are primarily comprised by the 6d-orbitals (7.3 ± 0.6%) with minor participation from the 5f-orbitals (1.5 ± 0.5%). These unique complexes provide new insights into actinide–arenide bonding interactions and show the sensitivity of the electronic structures of the uranium atoms to coordination sphere effects. 
    more » « less
  5. Abstract We present near-infrared Large Binocular Telescope LMIRCam imagery of the disk around the Herbig Ae/Be star AB Aurigae. A comparison of the surface brightness at K s (2.16 μ m), H 2 O narrowband (3.08 μ m), and L ′ (3.7 μ m) allows us to probe the presence of icy grains in this (pre)transitional disk environment. By applying reference differential imaging point-spread function subtraction, we detect the disk at high signal-to-noise ratios in all three bands. We find strong morphological differences between the bands, including asymmetries consistent with the observed spiral arms within 100 au in L ′ . An apparent deficit of scattered light at 3.08 μ m relative to the bracketing wavelengths ( K s and L ′ ) is evocative of ice absorption at the disk surface layer. However, the Δ( K s − H 2 O) color is consistent with grains with little to no ice (0%–5% by mass). The Δ ( H 2 O − L ′ ) color, conversely, suggests grains with a much higher ice mass fraction (∼0.68), and the two colors cannot be reconciled under a single grain population model. Additionally, we find that the extremely red Δ ( K s − L ′ ) disk color cannot be reproduced under conventional scattered light modeling with any combination of grain parameters or reasonable local extinction values. We hypothesize that the scattering surfaces at the three wavelengths are not colocated, and that the optical depth effects in each wavelength result from probing the grain population at different disk surface depths. The morphological similarity between K s and H 2 O suggests that their scattering surfaces are near one another, lending credence to the Δ( K s − H 2 O) disk color constraint of <5% ice mass fraction for the outermost scattering disk layer. 
    more » « less