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: The diameter of the uniform spanning tree of dense graphs
Abstract We show that the diameter of a uniformly drawn spanning tree of a simple connected graph on n vertices with minimal degree linear in n is typically of order $$\sqrt{n}$$ . A byproduct of our proof, which is of independent interest, is that on such graphs the Cheeger constant and the spectral gap are comparable.  more » « less
Award ID(s):
1855464
PAR ID:
10428427
Author(s) / Creator(s):
; ;
Date Published:
Journal Name:
Combinatorics, Probability and Computing
Volume:
31
Issue:
6
ISSN:
0963-5483
Page Range / eLocation ID:
1010 to 1030
Format(s):
Medium: X
Sponsoring Org:
National Science Foundation
More Like this
  1. Given a simple graph $$G$$, the irregularity strength of $$G$$, denoted $s(G)$, is the least positive integer $$k$$ such that there is a weight assignment on edges $$f: E(G) \to \{1,2,\dots, k\}$$ for which each vertex weight $$f^V(v):= \sum_{u: \{u,v\}\in E(G)} f(\{u,v\})$$ is unique amongst all $$v\in V(G)$$. In 1987, Faudree and Lehel conjectured that there is a constant $$c$$ such that $$s(G) \leq n/d + c$$ for all $$d$$-regular graphs $$G$$ on $$n$$ vertices with $d>1$, whereas it is trivial that $$s(G) \geq n/d$$. In this short note we prove that the Faudree-Lehel Conjecture holds when $$d \geq n^{0.8+\epsilon}$$ for any fixed $$\epsilon >0$$, with a small additive constant $c=28$ for $$n$$ large enough. Furthermore, we confirm the conjecture asymptotically by proving that for any fixed $$\beta\in(0,1/4)$$ there is a constant $$C$$ such that for all $$d$$-regular graphs $$G$$, $$s(G) \leq \frac{n}{d}(1+\frac{C}{d^{\beta}})+28$$, extending and improving a recent result of Przybyło that $$s(G) \leq \frac{n}{d}(1+ \frac{1}{\ln^{\epsilon/19}n})$$ whenever $$d\in [\ln^{1+\epsilon} n, n/\ln^{\epsilon}n]$$ and $$n$$ is large enough. 
    more » « less
  2. null (Ed.)
    Abstract This article describes the effects of gravity on the response of systems of identical, cyclically arranged, centrifugal pendulum vibration absorbers (CPVAs) fitted to a rotor spinning about a vertical axis. CPVAs are passive devices composed of movable masses suspended on a rotor, suspended such that they reduce torsional vibrations at a given engine order. Gravitational effects acting on the absorbers can be important for systems spinning at relatively low rotation speeds, for example, during engine idle conditions. The main goal of this study is to predict the response of a CPVA/rotor system in the presence of gravity. A linearized model that includes the effects of gravity and an order n torque acting on the rotor is analyzed by exploiting the cyclic symmetry of the system. The results show that a system of N absorbers responds in one or more groups, where the absorbers in each group have identical waveforms but shifted phases. The nature of the waveforms can have a limiting effect on the absorber operating envelope. The number of groups is shown to depend on the engine order n and the ratio N/n. It is also shown that there are special resonant effects if the engine order is n = 1 or n = 2, the latter of which is particularly important in applications. In these cases, the response of the absorbers has a complicated dependence on the relative levels of the applied torque and gravity. In addition, it is shown that for N > 1, the rotor response is not affected by gravity, at least to leading order, due to the cyclic symmetry of the gravity effects. The linear model and the attendant analytical predictions are verified by numerical simulations of the full nonlinear equations of motion. 
    more » « less
  3. This data package contains bird abundance data collected in plots that have had various plant functional groups or species experimentally removed at the Jornada Basin LTER site in southern New Mexico, USA. This data was collected in an effort to distinguish the differential effects of plant community biomass, plant community functional groups, and biodiversity within functional groups on plant community function, including effects on animals. To make these distinctions, treatments were established by the selective removal of plant species or functional groups within experimental plots. There are eight treatments: control (C, no removals); four functional group removal treatments (PG, perennial grass removed; S, shrubs removed; SSh, subshrubs removed; Succ, succulents removed), and three species richness manipulation treatments. Richness manipulations included a simplified treatment (Simp), where only the single most abundant species of each growth form is preserved and all other species in the growth form are removed, a reduced‐Larrea treatment (rL), where the Larrea is assumed to be the dominant and is removed while minority components remain, and a reduced-Prosopsis treatment (rP), where Prosopis rather than Larrea is removed as the shrub dominant. Following treatments, bird abundance and habitat preference data was collected in 1997. This data set consists of plot number, treatment type, and time of bird presence by taxa and by habitat and behavior. This study is complete. 
    more » « less
  4. Abstract The Witt algebra  $${\mathfrak{W}}_{n}$$ is the Lie algebra of all derivations of the $$n$$-variable polynomial ring $$\textbf{V}_{n}=\textbf{C}[x_{1}, \ldots , x_{n}]$$ (or of algebraic vector fields on $$\textbf{A}^{n}$$). A representation of $${\mathfrak{W}}_{n}$$ is polynomial if it arises as a subquotient of a sum of tensor powers of $$\textbf{V}_{n}$$. Our main theorems assert that finitely generated polynomial representations of $${\mathfrak{W}}_{n}$$ are noetherian and have rational Hilbert series. A key intermediate result states polynomial representations of the infinite Witt algebra are equivalent to representations of $$\textbf{Fin}^{\textrm{op}}$$, where $$\textbf{Fin}$$ is the category of finite sets. We also show that polynomial representations of $${\mathfrak{W}}_{n}$$ are equivalent to polynomial representations of the endomorphism monoid of $$\textbf{A}^{n}$$. These equivalences are a special case of an operadic version of Schur–Weyl duality, which we establish. 
    more » « less
  5. The spread of a graph $$G$$ is the difference between the largest and smallest eigenvalue of the adjacency matrix of $$G$$. Gotshall, O'Brien and Tait conjectured that for sufficiently large $$n$$, the $$n$$-vertex outerplanar graph with maximum spread is the graph obtained by joining a vertex to a path on $n-1$ vertices. In this paper, we disprove this conjecture by showing that the extremal graph is the graph obtained by joining a vertex to a path on $$\lceil(2n-1)/3\rceil$$ vertices and $$\lfloor(n-2)/3\rfloor$$ isolated vertices. For planar graphs, we show that the extremal $$n$$-vertex planar graph attaining the maximum spread is the graph obtained by joining two nonadjacent vertices to a path on $$\lceil(2n-2)/3\rceil$$ vertices and $$\lfloor(n-4)/3\rfloor$$ isolated vertices. 
    more » « less