Prove that from an $n\times n$ grid, one can find $\Omega (n^{\frac{5}{3}})$ points such that no four of them are vertices of a square with sides parallel to lines of the grid. Imagine yourself as Erdos (!) and guess what is the best exponent instead of $\frac{5}{3}$!
1. **Assumption and Setup:**
   We are given an \( n \times n \) grid and need to find a set of points such that no four points form the vertices of a square with sides parallel to the grid lines. We assume there are \( n \) points per row.

2. **Choosing Points Randomly:**
   We choose a set \( S \) of \( cn^{\frac{5}{3}} \) points from the grid uniformly and at random, where \( c \) is a positive constant to be determined later.

3. **Probability Calculation:**
   The probability that a randomly chosen set of four points forms the vertices of a square with sides parallel to the grid is given by:
   \[
   \frac{\frac{(n - 1)n(2n - 1)}{6}}{\frac{(n^2)(n^2 - 1)(n^2 - 2)(n^2 - 3)}{24}} \le Cn^{-5}
   \]
   for some positive constant \( C \).

4. **Expected Number of Squares:**
   Among \( cn^{\frac{5}{3}} \) points, the expected number of squares with sides parallel to the grid is:
   \[
   Cn^{-5} \binom{cn^{\frac{5}{3}}}{4} \le \frac{c^4 C n^{\frac{5}{3}}}{24}
   \]

5. **Configuration and Removal:**
   There exists a configuration in which there are at most this many squares. Removing all vertices of every such square, we are left with:
   \[
   cn^{\frac{5}{3}} - \frac{c^4 C n^{\frac{5}{3}}}{6} = \left(c - \frac{c^4 C}{6}\right) n^{\frac{5}{3}}
   \]
   points. For some positive \( c \) sufficiently small, the constant multiplier is positive, ensuring that we have a positive number of points left.

6. **Conclusion:**
   Therefore, we can find \( \Omega(n^{\frac{5}{3}}) \) points such that no four of them form the vertices of a square with sides parallel to the grid lines.

The final answer is \( \boxed{ \Omega(n^{\frac{5}{3}}) } \)