###

__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

*
*
min{|A|+|B|-3, p}.

(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}
*

*
*
for *any* choice of *p, A, B*, and *f*.
*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.