Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userLines in metric spaces: universal lines counted with multiplicity
96
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
The line generated by two distinct points, $x$ and $y$, in a finite metric space $M=(V,d)$, denoted by $overline{xy}^M$, is the set of points given by $$overline{xy}^M:={zin V: d(x,y)=|d(x,z)pm d(z,y)|}.$$ A 2-set ${x,y}$ such that $overline{xy}^M=V$ is called a universal pair and its associated line a universal line. Chen and Chvatal conjectured that in any finite metric space either there is a universal line or there are at least $|V|$ different (non-universal) lines. Chvatal proved that this is indeed the case when the metric space has distances in the set ${0,1,2}$. Aboulker et al. proposed the following strengthening for Chen and Chvatal conjecture in the context of metric spaces induced by finite graphs. The number of lines plus the number of universal pairs is at least the number of point of the space. In this work we first prove that metric spaces with distances in the set ${0,1,2}$ satisfy this stronger conjecture. We also prove that for metric spaces induced by bipartite graphs the number of lines plus the number of bridges of the graph is at least the number its vertices, unless the graph is $C_4$ or $K_{2,3}$.
rate research
Read More
A classic theorem of Euclidean geometry asserts that any noncollinear set of $n$ points in the plane determines at least $n$ distinct lines. Chen and Chvatal conjectured that this holds for an arbitrary finite metric space, with a certain natural definition of lines in a metric space. We prove that in any metric space with $n$ points, either there is a line containing all the points or there are at least $Omega(sqrt{n})$ lines. This is the first polynomial lower bound on the number of lines in general finite metric spaces. In the more general setting of pseudometric betweenness, we prove a corresponding bound of $Omega(n^{2/5})$ lines. When the metric space is induced by a connected graph, we prove that either there is a line containing all the points or there are $Omega(n^{4/7})$ lines, improving the previous $Omega(n^{2/7})$ bound. We also prove that the number of lines in an $n$-point metric space is at least $n / 5w$, where $w$ is the number of different distances in the space, and we give an $Omega(n^{4/3})$ lower bound on the number of lines in metric spaces induced by graphs with constant diameter, as well as spaces where all the positive distances are from {1, 2, 3}.
Let $mathfrak{M}$ be a class of metric spaces. A metric space $Y$ is minimal $mathfrak{M}$-universal if every $Xinmathfrak{M}$ can be isometrically embedded in $Y$ but there are no proper subsets of $Y$ satisfying this property. We find conditions under which, for given metric space $X$, there is a class $mathfrak{M}$ of metric spaces such that $X$ is minimal $mathfrak{M}$-universal. We generalize the notion of minimal $mathfrak{M}$-universal metric space to notion of minimal $mathfrak{M}$-universal class of metric spaces and prove the uniqueness, up to an isomorphism, for these classes. The necessary and sufficient conditions under which the disjoint union of the metric spaces belonging to a class $mathfrak{M}$ is minimal $mathfrak{M}$-universal are found. Examples of minimal universal metric spaces are constructed for the classes of the three-point metric spaces and $n$-dimensional normed spaces. Moreover minimal universal metric spaces are found for some subclasses of the class of metric spaces $X$ which possesses the following property. Among every three distinct points of $X$ there is one point lying between the other two points.
We give a fairly elementary and simple proof that shows that the number of incidences between $m$ points and $n$ lines in ${mathbb R}^3$, so that no plane contains more than $s$ lines, is $$ Oleft(m^{1/2}n^{3/4}+ m^{2/3}n^{1/3}s^{1/3} + m + nright) $$ (in the precise statement, the constant of proportionality of the first and third terms depends, in a rather weak manner, on the relation between $m$ and $n$). This bound, originally obtained by Guth and Katz~cite{GK2} as a major step in their solution of Erd{H o}ss distinct distances problem, is also a major new result in incidence geometry, an area that has picked up considerable momentum in the past six years. Its original proof uses fairly involved machinery from algebraic and differential geometry, so it is highly desirable to simplify the proof, in the interest of better understanding the geometric structure of the problem, and providing new tools for tackling similar problems. This has recently been undertaken by Guth~cite{Gu14}. The present paper presents a different and simpler derivation, with better bounds than those in cite{Gu14}, and without the restrictive assumptions made there. Our result has a potential for applications to other incidence problems in higher dimensions.
Let $L$ be a set of $n$ lines in $R^3$ that is contained, when represented as points in the four-dimensional Plucker space of lines in $R^3$, in an irreducible variety $T$ of constant degree which is emph{non-degenerate} with respect to $L$ (see below). We show: medskip oindent{bf (1)} If $T$ is two-dimensional, the number of $r$-rich points (points incident to at least $r$ lines of $L$) is $O(n^{4/3+epsilon}/r^2)$, for $r ge 3$ and for any $epsilon>0$, and, if at most $n^{1/3}$ lines of $L$ lie on any common regulus, there are at most $O(n^{4/3+epsilon})$ $2$-rich points. For $r$ larger than some sufficiently large constant, the number of $r$-rich points is also $O(n/r)$. As an application, we deduce (with an $epsilon$-loss in the exponent) the bound obtained by Pach and de Zeeuw (2107) on the number of distinct distances determined by $n$ points on an irreducible algebraic curve of constant degree in the plane that is not a line nor a circle. medskip oindent{bf (2)} If $T$ is two-dimensional, the number of incidences between $L$ and a set of $m$ points in $R^3$ is $O(m+n)$. medskip oindent{bf (3)} If $T$ is three-dimensional and nonlinear, the number of incidences between $L$ and a set of $m$ points in $R^3$ is $Oleft(m^{3/5}n^{3/5} + (m^{11/15}n^{2/5} + m^{1/3}n^{2/3})s^{1/3} + m + n right)$, provided that no plane contains more than $s$ of the points. When $s = O(min{n^{3/5}/m^{2/5}, m^{1/2}})$, the bound becomes $O(m^{3/5}n^{3/5}+m+n)$. As an application, we prove that the number of incidences between $m$ points and $n$ lines in $R^4$ contained in a quadratic hypersurface (which does not contain a hyperplane) is $O(m^{3/5}n^{3/5} + m + n)$. The proofs use, in addition to various tools from algebraic geometry, recent bounds on the number of incidences between points and algebraic curves in the plane.
We investigate equiangular lines in finite orthogonal geometries, focusing specifically on equiangular tight frames (ETFs). In parallel with the known correspondence between real ETFs and strongly regular graphs (SRGs) that satisfy certain parameter constraints, we prove that ETFs in finite orthogonal geometries are closely aligned with a modular generalization of SRGs. The constraints in our finite field setting are weaker, and all but~18 known SRG parameters on $v leq 1300$ vertices satisfy at least one of them. Applying our results to triangular graphs, we deduce that Gerzons bound is attained in finite orthogonal geometries of infinitely many dimensions. We also demonstrate connections with real ETFs, and derive necessary conditions for ETFs in finite orthogonal geometries. As an application, we show that Gerzons bound cannot be attained in a finite orthogonal geometry of dimension~5.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
