We prove that for every finite connected simple graph $G$ on $n$ vertices with minimum degree $k\geq 2$, there is a coupling of its uniform spanning tree and its random $1$-out subgraph under which the expected number of differing edges is $O(n\log (k)/\sqrt{k})$. More generally, we establish analogous couplings between a wide class of determinantal processes and their corresponding $1$-out processes, including Kalai's determinantal hypertrees, with expected symmetric difference negligible compared to the size of the determinantal set. While the graphical case admits a surprisingly short and elegant proof, the more general result requires establishing an asymptotic equipartition property for the determinantal measures in this class, from which we also derive exponential growth rates for the homology torsion of determinantal hyperforests in higher-dimensional regular high-degree complexes.
We consider the adjacency matrix of a uniformly random simple $d$-regular graph on $N$ vertices. For every fixed $d\geq3$ and every fixed bulk energy, we prove that the rescaled eigenvalue point process converges to the $\mathrm{Sine}_1$ process with intensity $1/\pi$. We also establish universality of consecutive gaps...
We prove that the number of labelled embeddings of any $n$-vertex tree $T$ into an $n$-vertex graph $G$ of maximum degree $d$ satisfies $$ \mathrm{inj}(T,G) \leq (d/e)^n \exp(o_d(1) n). $$ The bound is sharp up to determining $o_d(1)$, even for paths, and the dependence of the error $\exp(o_d(1)n)$ on $d$ is necessary....
Csongor Beke, V. Boskovic, Nina Kamčev et al.· 0 citations
We introduce a determinantal linear process on the space of $1$-forms over a weighted graph endowed with a unitary local system, which we call the determinantal linear spanning forest (DLSF). This process is the analog of the uniform spanning tree in the presence of an arbitrary rank $n$ quenched gauge field in ${\rm U...
Let $G$ be a finite bipartite graph and let $\widetilde G$ be an $M$-fold cover. We compare independent sets of $\widetilde G$ with those of the trivial cover, consisting of $M$ disjoint copies of $G$, after prescribing how many vertices are selected above each vertex of $G$. A conjecture from 2011, motivated by the Be...
Optimising the vertex correspondence can substantially increase the number of edges shared by two independent realisations of the same random graph. We quantify this phenomenon for uniformly random $d$-regular graphs and derive corresponding results for their edge-based graph edit distance. For every fixed $d\geq 3$, w...
We construct a fixed triangular family of noncommutative polynomials that spans the joint cyclic module of a real symmetric pair from any prescribed vector. In dimension at most $N$, when the second matrix has spectral diameter at most $N-1$, the family has $N(N+1)/2$ members, degree at most $N-1$, and a shared arithme...
Zhi-Peng Lu· 0 citations
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
