More Like this

1. Short Proof of the Asymptotic Confirmation of the Faudree-Lehel Conjecture

   https://doi.org/10.37236/11413  

   Przybyło, Jakub; Wei, Fan (October 2023, The Electronic Journal of Combinatorics)

   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. The Positive Tropical Grassmannian, the Hypersimplex, and the m = 2 Amplituhedron

   https://doi.org/10.1093/imrn/rnad010  

   Łukowski, Tomasz; Parisi, Matteo; Williams, Lauren K (March 2023, International Mathematics Research Notices)

   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
3. Improved Bounds on a Generalization of Tuza's Conjecture

   https://doi.org/10.37236/10829  

   Basit, Abdul; McGinnis, Daniel; Simmons, Henry; Sinnwell, Matt; Zerbib, Shira (October 2022, The Electronic Journal of Combinatorics)

   For an $$r$$-uniform hypergraph $$H$$, let $$\nu^{(m)}(H)$$ denote the maximum size of a set $$M$$ of edges in $$H$$ such that every two edges in $$M$$ intersect in less than $$m$$ vertices, and let $$\tau^{(m)}(H)$$ denote the minimum size of a collection $$C$$ of $$m$$-sets of vertices such that every edge in $$H$$ contains an element of $$C$$. The fractional analogues of these parameters are denoted by $$\nu^{*(m)}(H)$$ and $$\tau^{*(m)}(H)$$, respectively. Generalizing a famous conjecture of Tuza on covering triangles in a graph, Aharoni and Zerbib conjectured that for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(r-1)}(H)/\nu^{(r-1)}(H) \leq \lceil{\frac{r+1}{2}}\rceil$$. In this paper we prove bounds on the ratio between the parameters $$\tau^{(m)}$$ and $$\nu^{(m)}$$, and their fractional analogues. Our main result is that, for every $$r$$-uniform hypergraph~$$H$$,\[ \tau^{*(r-1)}(H)/\nu^{(r-1)}(H) \le \begin{cases} \frac{3}{4}r - \frac{r}{4(r+1)} &\text{for }r\text{ even,}\\\frac{3}{4}r - \frac{r}{4(r+2)} &\text{for }r\text{ odd.} \\\end{cases} \]This improves the known bound of $$r-1$.We also prove that, for every $$r$$-uniform hypergraph $$H$$, $$\tau^{(m)}(H)/\nu^{*(m)}(H) \le \operatorname{ex}_m(r, m+1)$$, where the Turán number $$\operatorname{ex}_r(n, k)$$ is the maximum number of edges in an $$r$$-uniform hypergraph on $$n$$ vertices that does not contain a copy of the complete $$r$$-uniform hypergraph on $$k$$ vertices. Finally, we prove further bounds in the special cases $(r,m)=(4,2)$ and $(r,m)=(4,3)$. 

   more » « less
4. Analysis of stochastic Lanczos quadrature for spectrum approximation

   Chen, Tyler; Trogdon, Thomas; Ubaru, Shashanka (January 2021, Proceedings of the 38th International Conference on Machine Learning)

   The cumulative empirical spectral measure (CESM) $$\Phi[\mathbf{A}] : \mathbb{R} \to [0,1]$$ of a $$n\times n$$ symmetric matrix $$\mathbf{A}$$ is defined as the fraction of eigenvalues of $$\mathbf{A}$$ less than a given threshold, i.e., $$\Phi[\mathbf{A}](x) := \sum_{i=1}^{n} \frac{1}{n} {\large\unicode{x1D7D9}}[ \lambda_i[\mathbf{A}]\leq x]$$. Spectral sums $$\operatorname{tr}(f[\mathbf{A}])$$ can be computed as the Riemann–Stieltjes integral of $$f$$ against $$\Phi[\mathbf{A}]$$, so the task of estimating CESM arises frequently in a number of applications, including machine learning. We present an error analysis for stochastic Lanczos quadrature (SLQ). We show that SLQ obtains an approximation to the CESM within a Wasserstein distance of $$t \: | \lambda_{\text{max}}[\mathbf{A}] - \lambda_{\text{min}}[\mathbf{A}] |$$ with probability at least $$1-\eta$$, by applying the Lanczos algorithm for $$\lceil 12 t^{-1} + \frac{1}{2} \rceil$$ iterations to $$\lceil 4 ( n+2 )^{-1}t^{-2} \ln(2n\eta^{-1}) \rceil$$ vectors sampled independently and uniformly from the unit sphere. We additionally provide (matrix-dependent) a posteriori error bounds for the Wasserstein and Kolmogorov–Smirnov distances between the output of this algorithm and the true CESM. The quality of our bounds is demonstrated using numerical experiments. 

   more » « less
5. Interpolation for Curves in Projective Space with Bounded Error

   https://doi.org/10.1093/imrn/rnz136  

   Larson, Eric (July 2019, International Mathematics Research Notices)

   Abstract Given $$n$$ general points $$p_1, p_2, \ldots , p_n \in{\mathbb{P}}^r$$ it is natural to ask whether there is a curve of given degree $$d$$ and genus $$g$$ passing through them; by counting dimensions a natural conjecture is that such a curve exists if and only if $$\begin{equation*}n \leq \left\lfloor \frac{(r + 1)d - (r - 3)(g - 1)}{r - 1}\right\rfloor.\end{equation*}$$The case of curves with nonspecial hyperplane section was recently studied in [2], where the above conjecture was shown to hold with exactly three exceptions. In this paper, we prove a “bounded-error analog” for special linear series on general curves; more precisely we show that existence of such a curve subject to the stronger inequality $$\begin{equation*}n \leq \left\lfloor \frac{(r + 1)d - (r - 3)(g - 1)}{r - 1}\right\rfloor - 3.\end{equation*}$$Note that the $-3$ cannot be replaced with $-2$ without introducing exceptions (as a canonical curve in $${\mathbb{P}}^3$$ can only pass through nine general points, while a naive dimension count predicts twelve). We also use the same technique to prove that the twist of the normal bundle $$N_C(-1)$$ satisfies interpolation for curves whose degree is sufficiently large relative to their genus, and deduce from this that the number of general points contained in the hyperplane section of a general curve is at least $$\begin{equation*}\min\left(d, \frac{(r - 1)^2 d - (r - 2)^2 g - (2r^2 - 5r + 12)}{(r - 2)^2}\right).\end{equation*}$$ As explained in [7], these results play a key role in the author’s proof of the maximal rank conjecture [9]. 

   more » « less