Problem 3

A k-biclique in a bipartite graph G = (L, R, E) is a pair of vertex sets SC

L, TCR of sizes |S| = |T|= k such that ry € E for every 2 € S, y ≤ T.

Let G(n,n, 1/2) denote a random bipartite graph with n vertices in each

part (i.e., |L| = |R| = n) where every edge ry, for r € L,y € R appears

independently with probability 1/2.

1. Construct a deterministic polynomial-time algorithm that receives a bi-

partite graph G = (L, R, E) and returns a k-biclique in G such that the

probability

(k≥ 0.9 log n) → 1

Pr

G~G(n,n,1/2)

as n → ∞o.

To clarify, the algorithm always returns a biclique in G, and if the input G

is a G(n,1/2, 1/2) random graph then the biclique the algorithm returns

has at least 0.9 log n vertices on each part with high probability.

2. Construct a polynomial-time deterministic algorithm that receives an in-

put bipartite graph G and returns a number K = K(G) satisfying:

• For every graph G, there is no K(G)-biqlique in G.

2/n• Ec> 0 such that if G~ G(n, n, 1/2) then

Pr(K(G) > c√n) → 0

as n → ∞o.

The following theorems may be used.

Theorem. Let G~ G(n,n, 1/2), A its adjacency matrix, J the adjacency ma-

trix of the complete bipartite graph Kn,n and

B := 2A - J.

Then, there exists a constant >0 such that Pr(A₁(B) > {√√n) →0 as n→ ∞.

(Note that A, J and B are square matrices of order 2n)

Theorem. There exists a polynomial-time algorithm the receives a symmetric

matriz A and returns its eigenvalues and eigenvectors.