Generalized Erdos-Heilbronn and Bipartite Graphs

The famous Erdos-Heilbronn conjecture was that given two sets A and B of residues modulo a prime p, the number of elements of the "restricted sum" A^B is always at least

(The restricted sum A^B is defined to be the set of all the residues representable in the form a+b, where a and b are distinct, a is an element of A, and b is an element of B.)

This conjecture was proved in 1994 by Dias da Silva and Hamidoune. Later, their proof was drastically simplified and generalized by Alon, Nathanson, and Ruzsa who actually developed a powerful method which allows one to settle numerous similar problems with the restricting condition "a is not equal to b" replaced by "f(a,b) is not equal to zero" for arbitrary given polynomial f over the field of residues modulo p.

My conjecture is that a similar result holds when the sums a+b excluded from the consideration obey a much more general pattern. Specifically, let f be an arbitrary injective mapping from A to B. Define A^B to be the set of the residues representable as a+b with a in A, b in B, and b distinct from f(a).

Conjecture 1. The cardinality of A^B is at least

min{|A|+|B|-3, p-2}

Remark 1. If true, this is best possible. For |A|+|B| not exceeding p+1 this is shown by the example of two arithmetic progressions sharing the same difference and a suitably chosen f. For |A|+|B| greater than or equal to p+2, we have a more elaborate example.

Remark 2. Though in Conjecture 1 we have p-2 instead of p in the Erdos-Heilbronn conjecture, the former conjecture is easily seen to imply the latter.

In the case |A|+|B|>p Conjecture 1 reduces to the following graph-theoretic problem.

Conjecture 2. Let a be any fixed residue, distinct from 0 and 1, modulo a prime number p. Consider a cubic bipartite graph G_a on two copies of the group of residues modulo p, such that any vertex x from the first copy is adjacent to the vertices x, x+1, and x+a of the second copy. Then any induced subgraph of order p+1 of any such G_a contains a path of length 2.

For a=2, a=(p+1)/2, and a=p-1 this is easy; otherwise, nothing is known.

See my note "A generalization of the Erdos-Heilbronn conjecture" for more on this and related problems.