We study tight projective 2‐designs in three different settings. In the complex setting, Zauner's conjecture predicts the existence of a tight projective 2‐design in every dimension. Pandey, Paulsen, Prakash, and Rahaman recently proposed an approach to make quantitative progress on this conjecture in terms of the entanglement breaking rank of a certain quantum channel. We show that this quantity is equal to the size of the smallest weighted projective 2‐design. Next, in the finite field setting, we introduce a notion of projective 2‐designs, we characterize when such projective 2‐designs are tight, and we provide a construction of such objects. Finally, in the quaternionic setting, we show that every tight projective 2‐design for determines an equi‐isoclinic tight fusion frame of subspaces of of dimension 3.
more » « less Award ID(s):
 1829955
 NSFPAR ID:
 10449865
 Publisher / Repository:
 Wiley Blackwell (John Wiley & Sons)
 Date Published:
 Journal Name:
 Journal of Combinatorial Designs
 Volume:
 29
 Issue:
 12
 ISSN:
 10638539
 Page Range / eLocation ID:
 p. 809832
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this

One of the most intruguing conjectures in extremal graph theory is the conjecture of Erdős and Sós from 1962, which asserts that every $n$vertex graph with more than $\frac{k1}{2}n$ edges contains any $k$edge tree as a subgraph. Kalai proposed a generalization of this conjecture to hypergraphs. To explain the generalization, we need to define the concept of a tight tree in an $r$uniform hypergraph, i.e., a hypergraph where each edge contains $r$ vertices. A tight tree is an $r$uniform hypergraph such that there is an ordering $v_1,\ldots,v_n$ of its its vertices with the following property: the vertices $v_1,\ldots,v_r$ form an edge and for every $i>r$, there is a single edge $e$ containing the vertex $v_i$ and $r1$ of the vertices $v_1,\ldots,v_{i1}$, and $e\setminus\{v_i\}$ is a subset of one of the edges consisting only of vertices from $v_1,\ldots,v_{i1}$. The conjecture of Kalai asserts that every $n$vertex $r$uniform hypergraph with more than $\frac{k1}{r}\binom{n}{r1}$ edges contains every $k$edge tight tree as a subhypergraph. The recent breakthrough results on the existence of combinatorial designs by Keevash and by Glock, Kühn, Lo and Osthus show that this conjecture, if true, would be tight for infinitely many values of $n$ for every $r$ and $k$.The article deals with the special case of the conjecture when the sought tight tree is a path, i.e., the edges are the $r$tuples of consecutive vertices in the above ordering. The case $r=2$ is the famous ErdősGallai theorem on the existence of paths in graphs. The case $r=3$ and $k=4$ follows from an earlier work of the authors on the conjecture of Kalai. The main result of the article is the first nontrivial upper bound valid for all $r$ and $k$. The proof is based on techniques developed for a closely related problem where a hypergraph comes with a geometric structure: the vertices are points in the plane in a strictly convex position and the sought path has to zigzag beetwen the vertices.more » « less

Guruswami, Venkatesan (Ed.)Algorithms with predictions is a new research direction that leverages machine learned predictions for algorithm design. So far a plethora of recent works have incorporated predictions to improve on worstcase bounds for online problems. In this paper, we initiate the study of complexity of dynamic data structures with predictions, including dynamic graph algorithms. Unlike online algorithms, the goal in dynamic data structures is to maintain the solution efficiently with every update. We investigate three natural models of prediction: (1) δaccurate predictions where each predicted request matches the true request with probability δ, (2) listaccurate predictions where a true request comes from a list of possible requests, and (3) bounded delay predictions where the true requests are a permutation of the predicted requests. We give general reductions among the prediction models, showing that bounded delay is the strongest prediction model, followed by listaccurate, and δaccurate. Further, we identify two broad problem classes based on lower bounds due to the Online Matrix Vector (OMv) conjecture. Specifically, we show that locally correctable dynamic problems have strong conditional lower bounds for listaccurate predictions that are equivalent to the nonprediction setting, unless listaccurate predictions are perfect. Moreover, we show that locally reducible dynamic problems have time complexity that degrades gracefully with the quality of bounded delay predictions. We categorize problems with known OMv lower bounds accordingly and give several upper bounds in the delay model that show that our lower bounds are almost tight. We note that concurrent work by v.d.Brand et al. [SODA '24] and Liu and Srinivas [arXiv:2307.08890] independently study dynamic graph algorithms with predictions, but their work is mostly focused on showing upper bounds.more » « less

Abstract We note that the recent polynomial proofs of the spherical and complex plank covering problems by Zhao and OrtegaMoreno give some general information on zeros of real and complex polynomials restricted to the unit sphere. As a corollary of these results, we establish several generalizations of the celebrated Bang plank covering theorem. We prove a tight polynomial analog of the Bang theorem for the Euclidean ball and an even stronger polynomial version for the complex projective space. Specifically, for the ball, we show that for every real nonzero $d$variate polynomial $P$ of degree $n$, there exists a point in the unit $d$dimensional ball at distance at least $1/n$ from the zero set of the polynomial $P$. Using the polynomial approach, we also prove the strengthening of the Fejes Tóth zone conjecture on covering a sphere by spherical segments, closed parts of the sphere between two parallel hyperplanes. In particular, we show that the sum of angular widths of spherical segments covering the whole sphere is at least $\pi $.more » « less

We construct smooth projective varieties of general type with the smallest known volume and others with the most known vanishing plurigenera in high dimensions. The optimal volume bound is expected to decay doubly exponentially with dimension, and our examples achieve this decay rate. We also consider the analogous questions for other types of varieties. For example, in every dimension we conjecture the terminal Fano variety of minimal volume, and the canonical CalabiYau variety of minimal volume. In each case, our examples exhibit doubly exponential behavior.more » « less

Abstract The Chebyshev potential of a Hermitian metric on an ample line bundle over a projective variety, introduced by Witt Nyström, is a convex function defined on the Okounkov body. It is a generalization of the symplectic potential of a torus‐invariant Kähler potential on a toric variety, introduced by Guillemin, that is a convex function on the Delzant polytope. A folklore conjecture asserts that a curve of Chebyshev potentials associated to a subgeodesic in the space of positively curved Hermitian metrics is linear in the time variable if and only if the subgeodesic is a geodesic in the Mabuchi metric. This is classically true in the special toric setting, and in general Witt Nyström established the sufficiency. The main obstacle in the conjecture is that it is difficult to compute Chebyshev potentials, that are currently only known on the Riemann sphere and toric varieties. The goal of this article is to disprove this conjecture. To that end we characterize the geodesics consisting of Fubini–Study metrics for which the conjecture is true on the hyperplane bundle of the projective space. The proof involves explicitly solving the Monge–Ampère equation describing geodesics on the subspace of Fubini–Study metrics and computing their Chebyshev potentials.