An official website of the United States government
Let $$N=\binom{n}{2}$$ and $$s\geq 2$$. Let $$e_{i,j},\,i=1,2,\ldots,N,\,j=1,2,\ldots,s$$ be $$s$$ independent permutations of the edges $$E(K_n)$$ of the complete graph $$K_n$$. A MultiTree is a set $$I\subseteq [N]$$ such that the edge sets $$E_{I,j}$$ induce spanning trees for $$j=1,2,\ldots,s$$. In this paper we study the following question: what is the smallest $m=m(n)$ such that w.h.p. $[m]$ contains a MultiTree. We prove a hitting time result for $s=2$ and an $$O(n\log n)$$ bound for $$s\geq 3$$.
more »
« less
Minors of a random binary matroid
Let $${\bf A}$$ be an $$n\times m$$ matrix over $$\mathbf{GF}_2$$ where each column consists of $$k$$ ones, and let $$M$$ be an arbitrary fixed binary matroid. The matroid growth rate theorem implies that there is a constant $$C_M$$ such that $$m\geq C_M n^2$$ implies that the binary matroid induced by {\bf A} contains $$M$$ as a minor. We prove that if the columns of $${\bf A}={\bf A}_{n,m,k}$$ are chosen \emph{randomly}, then there are constants $$k_M, L_M$$ such that $$k\geq k_M$$ and $$m\geq L_M n$$ implies that $${\bf A}$$ contains $$M$$ as a minor w.h.p.
more »
« less
- Award ID(s):
- 1661063
- PAR ID:
- 10158509
- Date Published:
- Journal Name:
- Random structures algorithms
- Volume:
- 55
- ISSN:
- 1042-9832
- Page Range / eLocation ID:
- 865-880
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Abstract The positive Grassmannian $$Gr^{\geq 0}_{k,n}$$ is a cell complex consisting of all points in the real Grassmannian whose Plücker coordinates are non-negative. In this paper we consider the image of the positive Grassmannian and its positroid cells under two different maps: the moment map$$\mu $$ onto the hypersimplex [ 31] and the amplituhedron map$$\tilde{Z}$$ onto the amplituhedron [ 6]. For either map, we define a positroid dissection to be a collection of images of positroid cells that are disjoint and cover a dense subset of the image. Positroid dissections of the hypersimplex are of interest because they include many matroid subdivisions; meanwhile, positroid dissections of the amplituhedron can be used to calculate the amplituhedron’s ‘volume’, which in turn computes scattering amplitudes in $$\mathcal{N}=4$$ super Yang-Mills. We define a map we call T-duality from cells of $$Gr^{\geq 0}_{k+1,n}$$ to cells of $$Gr^{\geq 0}_{k,n}$$ and conjecture that it induces a bijection from positroid dissections of the hypersimplex $$\Delta _{k+1,n}$$ to positroid dissections of the amplituhedron $$\mathcal{A}_{n,k,2}$$; we prove this conjecture for the (infinite) class of BCFW dissections. We note that T-duality is particularly striking because the hypersimplex is an $(n-1)$-dimensional polytope while the amplituhedron $$\mathcal{A}_{n,k,2}$$ is a $2k$-dimensional non-polytopal subset of the Grassmannian $$Gr_{k,k+2}$$. Moreover, we prove that the positive tropical Grassmannian is the secondary fan for the regular positroid subdivisions of the hypersimplex, and prove that a matroid polytope is a positroid polytope if and only if all 2D faces are positroid polytopes. Finally, toward the goal of generalizing T-duality for higher $$m$$, we define the momentum amplituhedron for any even $$m$$.more » « less
-
Let $$\Omega_q$$ denote the set of proper $[q]$-colorings of the random graph $$G_{n,m}, m=dn/2$$ and let $$H_q$$ be the graph with vertex set $$\Omega_q$$ and an edge $$\set{\s,\t}$$ where $$\s,\t$$ are mappings $$[n]\to[q]$$ iff $$h(\s,\t)=1$$. Here $$h(\s,\t)$$ is the Hamming distance $$|\set{v\in [n]:\s(v)\neq\t(v)}|$$. We show that w.h.p. $$H_q$$ contains a single giant component containing almost all colorings in $$\Omega_q$$ if $$d$$ is sufficiently large and $$q\geq \frac{cd}{\log d}$$ for a constant $c>3/2$.more » « less
-
Abstract Let $$T$$ be a satellite knot, link, or spatial graph in a 3-manifold $$M$$ that is either $S^3$ or a lens space. Let $$\b_0$$ and $$\b_1$$ denote genus 0 and genus 1 bridge number, respectively. Suppose that $$T$$ has a companion knot $$K$$ (necessarily not the unknot) and wrapping number $$\omega$$ with respect to $$K$$. When $$K$$ is not a torus knot, we show that $$\b_1(T)\geq \omega \b_1(K)$$. There are previously known counter-examples if $$K$$ is a torus knot. Along the way, we generalize and give a new proof of Schubert's result that $$\b_0(T) \geq \omega \b_0(K)$$. We also prove versions of the theorem applicable to when $$T$$ is a "lensed satellite" and when there is a torus separating components of $$T$$.more » « less
-
null (Ed.)Abstract Let $$K$$ be an algebraically closed field of prime characteristic $$p$$ , let $$X$$ be a semiabelian variety defined over a finite subfield of $$K$$ , let $$\unicode[STIX]{x1D6F7}:X\longrightarrow X$$ be a regular self-map defined over $$K$$ , let $$V\subset X$$ be a subvariety defined over $$K$$ , and let $$\unicode[STIX]{x1D6FC}\in X(K)$$ . The dynamical Mordell–Lang conjecture in characteristic $$p$$ predicts that the set $$S=\{n\in \mathbb{N}:\unicode[STIX]{x1D6F7}^{n}(\unicode[STIX]{x1D6FC})\in V\}$$ is a union of finitely many arithmetic progressions, along with finitely many $$p$$ -sets, which are sets of the form $$\{\sum _{i=1}^{m}c_{i}p^{k_{i}n_{i}}:n_{i}\in \mathbb{N}\}$$ for some $$m\in \mathbb{N}$$ , some rational numbers $$c_{i}$$ and some non-negative integers $$k_{i}$$ . We prove that this conjecture is equivalent with some difficult diophantine problem in characteristic 0. In the case $$X$$ is an algebraic torus, we can prove the conjecture in two cases: either when $$\dim (V)\leqslant 2$$ , or when no iterate of $$\unicode[STIX]{x1D6F7}$$ is a group endomorphism which induces the action of a power of the Frobenius on a positive dimensional algebraic subgroup of $$X$$ . We end by proving that Vojta’s conjecture implies the dynamical Mordell–Lang conjecture for tori with no restriction.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
