I am reading Zarankiewicz's paper, On a problem of P. Turan concerning graphs, to try to learn more about Zarankiewicz's conjecture, out of my own interest. I have been confused about an assertion he makes about a line segment having no points in common with a set, and my question is how I can understand the possibility of such a line segment not having these points in common. The below 2 paragraphs are Zarankiewicz's exposition of the terms he will use in the portion which confuses me:

( $\alpha$ ) in the Euclidean plane two sets of points, $A$ and $B$, are given, $A$ consisting of $p$ points $a_1, a_2, a_3, \ldots, a_p$, and $B$ consisting of $q$ points $b_1, b_2, b_3, \ldots ; b_q$, ( $p$ and $q$ are natural numbers); (ß) for each pair of points $a_i, b_j$, where $i=1,2,3, \ldots, p, j=1,2,3, \ldots, q$, there exists a simple are lying in the plane and having the points $a_i, b_j$ as its end points; $(\gamma)$ the arcs lie in such a way that no three arcs have an interior point (i. e. a point that is not an end point) in common;

A simple arc having $x$ and $y$ as its end points will be denoted by $x y$. The sum of all the arcs $a_i b_j$, where $i=1,2,3, \ldots, p$ and $j=1,2,3, \ldots, q$, will be called the graph $G(p, q)$; so that we can write $$ G(p, q)=\sum_{i, j} a_i b_j $$

The last sentence of the 2nd paragraph below is the one which arouses my confusion:

Let us draw a circle $H_i$ with the centre $\boldsymbol{a_i}$, and a radius so small that: The circles $H_i$ have no common points with the set $$ \sum_{j, k} a_j b_1+b_1 a_k+a_j b_2+b_2 a_k+a_j b_3+b_3 a_k $$ where $j$ and $k$ take all the values $1,2,3$ except the value $i$, the circles $H_i$, for $i=1,2,3$ are disjoint from one another - which is of course possible.

Let $e_{r s}$ be the first point of the simple arc $b_r a_s$, going from $b_r$ to $a_s$, which lies on the circle $H_s$; then $b_r e_{r s}$ is a simple arc which has only one point in common with the circle $H_s$, namely its end point $e_{r s}$. Let $R_{r s}$ be a segment of the radius of the circle $H_s$, with $e_{r s}$ as one end point, while the other end point $\neq a_s$; let that segment be so small that it has no points in common with the set $\sum_j a_s b_j$, where $j$ takes all the values $1,2,3$ except the value $s$.

$e_{rs}$, as pointed out in the comments, trivially intersects the arc $b_r a_s$, and if the arc $b_r a_s$ is straight, then it seems that this segment $R_{rs}$ (which is also straight as it is a portion of the radius) will have all of its points intersect $b_r a_s$. Below is my attempt to draw a picture of this scenario, with straight arcs and $R_{21}$ having points in common with $a_1b_2$. So how can we guarantee that this segment $R_{rs}$ exists? enter image description here Some assumptions I made about this text were that $+$ between sets of points refers to the union of those sets (elsewhere multiplication is clearly used for the intersection), and also that the center of the circle $H_i$ should be $a_i$, not $a$, which I have rendered as such above (originally it was written merely $a$ with a space where the subscript should go, so I assumed the $i$ got washed out).

  • $\begingroup$ I'm guessing it's a typo and they meant "except the value $r$" instead of "except the value $s$". That way $R_{rs}$ intersects the arc $b_r a_s$ (at $e_{rs}$), but no other arcs out of $a_s$. $\endgroup$ May 15 at 7:21


You must log in to answer this question.