No Arabic abstract
In this paper we obtain a new lower bound on the ErdH{o}s distinct distances problem in the plane over prime fields. More precisely, we show that for any set $Asubset mathbb{F}_p^2$ with $|A|le p^{7/6}$, the number of distinct distances determined by pairs of points in $A$ satisfies $$ |Delta(A)| gg |A|^{frac{1}{2}+frac{149}{4214}}.$$ Our result gives a new lower bound of $|Delta{(A)}|$ in the range $|A|le p^{1+frac{149}{4065}}$. The main tools we employ are the energy of a set on a paraboloid due to Rudnev and Shkredov, a point-line incidence bound given by Stevens and de Zeeuw, and a lower bound on the number of distinct distances between a line and a set in $mathbb{F}_p^2$. The latter is the new feature that allows us to improve the previous bound due Stevens and de Zeeuw.
Given $E subseteq mathbb{F}_q^d times mathbb{F}_q^d$, with the finite field $mathbb{F}_q$ of order $q$ and the integer $d ge 2$, we define the two-parameter distance set as $Delta_{d, d}(E)=left{left(|x_1-y_1|, |x_2-y_2|right) : (x_1,x_2), (y_1,y_2) in E right}$. Birklbauer and Iosevich (2017) proved that if $|E| gg q^{frac{3d+1}{2}}$, then $ |Delta_{d, d}(E)| = q^2$. For the case of $d=2$, they showed that if $|E| gg q^{frac{10}{3}}$, then $ |Delta_{2, 2}(E)| gg q^2$. In this paper, we present extensions and improvements of these results.
In this paper, we introduce the notion of geodesic cover for Fuchsian groups, which summons copies of fundamental polygons in the hyperbolic plane to cover pairs of representatives realizing distances in the corresponding hyperbolic surface. Then we use estimates of geodesic-covering numbers to study the distinct distances problem in hyperbolic surfaces. Especially, for $Y$ from a large class of hyperbolic surfaces, we establish the nearly optimal bound $geq c(Y)N/log N$ for distinct distances determined by any $N$ points in $Y$, where $c(Y)>0$ is some constant depending only on $Y$. In particular, for $Y$ being modular surface or standard regular of genus $ggeq 2$, we evaluate $c(Y)$ explicitly. We also derive new sum-product type estimates.
Let $mathbb{F}_p$ be a prime field, and ${mathcal E}$ a set in $mathbb{F}_p^2$. Let $Delta({mathcal E})={||x-y||: x,y in {mathcal E} }$, the distance set of ${mathcal E}$. In this paper, we provide a quantitative connection between the distance set $Delta({mathcal E})$ and the set of rectangles determined by points in ${mathcal E}$. As a consequence, we obtain a new lower bound on the size of $Delta({mathcal E})$ when ${mathcal E}$ is not too large, improving a previous estimate due to Lund and Petridis and establishing an approach that should lead to significant further improvements.
The triangle covering number of a graph is the minimum number of vertices that hit all triangles. Given positive integers $s,t$ and an $n$-vertex graph $G$ with $lfloor n^2/4 rfloor +t$ edges and triangle covering number $s$, we determine (for large $n$) sharp bounds on the minimum number of triangles in $G$ and also describe the extremal constructions. Similar results are proved for cliques of larger size and color critical graphs. This extends classical work of Rademacher, ErdH os, and Lovasz-Simonovits whose results apply only to $s le t$. Our results also address two conjectures of Xiao and Katona. We prove one of them and give a counterexample and prove a modified version of the other conjecture.
For an integer $n>2$, a rank-$n$ matroid is called an $n$-spike if it consists of $n$ three-point lines through a common point such that, for all $kin{1, 2, ..., n - 1}$, the union of every set of $k$ of these lines has rank $k+1$. Spikes are very special and important in matroid theory. In 2003 Wu found the exact numbers of $n$-spikes over fields with 2, 3, 4, 5, 7 elements, and the asymptotic values for larger finite fields. In this paper, we prove that, for each prime number $p$, a $GF(p$) representable $n$-spike $M$ is only representable on fields with characteristic $p$ provided that $n ge 2p-1$. Moreover, $M$ is uniquely representable over $GF(p)$.