Assignment 1 in Geometric Graphs

Submission instructions:

Deadline: November, 24, to be submitted by 4PM to the Teaching Assistant email

razla@post.bgu.ac.il.

Submissions must indicate class, student ID, and the full name, and be individual and

clearly typed either in Hebrew or in English. You are allowed to borrow solution ideas from

fellow students or other external sources. However, the solutions must be self-contained and the

external sources/collaborators should be clearly mentioned in the submission.

- • Let 1 ≤ r ≤ s be constant integers. Show that any bipartite graph G = (V1, V2, E)

with |V1| = n1 and |V2| = n2 (for n1 ≥ n2), that does not contain a copy of Ks,r

as a subgraph, has |E| = O

n1n

1−1/r

2

edges.

• Let P = {p1, . . . , pn} be set of n points, and C = {c1, . . . , cm} be a family of m

distinct circles in the plane, for m ≥ n.

1 Show that the set of their incidences

I(P, C) = {(pi

, cj ) | pi ∈ cj

, 1 ≤ i ≤ n, 1 ≤ j ≤ m} has cardinality |I(P, C)| =

O(mn1/2

). - For any two sets A, B of real numbers denote A + B := {a + b | a ∈ A, b ∈ B} and

A × B := {a · b | a ∈ A, b ∈ B}.

Show that there is a constant C > 0 so that for any set A = {a1, . . . , an} of n > 0

distinct real numbers at least one of the following inequalities is satisfied 1. |A + A| ≥

Cn5/4

, 2. |A × A| ≥ Cn5/4

.

Hint: To bound |P| = |A + A| · |A × A| from below, use the upper bound on the number of

incidences between points P = (A+A)×(A×A) and

n

2

lines of the form `i,j : y = ai(x−aj ).

Check that the number of such incidences is at least Ω(n

3

). - • Show that the Vapnik-Chervonenkis (VC) dimension of a range space (X , R) (if

it is bounded) is equal to the order |V | of the largest complete hypergraph (V, F)

in this range space. 2

• Determine the VC-dimension of the range space (X , R), where X = R

2 and

R = {R(a, b, c, d) | a, b, c, d ∈ R

+} is comprised of all the rectangles of the form

R(a, b, c, d) := {(x, y) | a ≤ x ≤ b, c ≤ y ≤ d}.

• Show that the Sauer Shelah Theorem is not tight some range spaces. Describe a

range space (X , R) so that X = X, V Cdim (X , R) = 3, yet for any hypergraph

(V, F) in (X , R) we have that |F| = O(|V |

2

).

1Each circle is comprised of all the points (x, y) ∈ R

2

that satisfy the equality (x − a)

2 + (y − b)

2 = r

2

,

for some real r > 0.

2A hypergraph (V, F) is complete is |F| = 2|V