# An interpretation of the Dittert conjecture in terms of semi-matchings

Let G be K_{n,n} with non-negative edge weights and let
U and V be the two colour classes of vertices in G. We define a
k-semimatching in G to be a set of k edges such that the edges
either have distinct ends in U or distinct ends in
V. Semimatchings are to be counted according to the product of the
weights on the edges in the semimatching. The Dittert conjecture is a
longstanding open problem involving matrix permanents. Here we show
that it is equivalent to the following assertion: For a fixed total
weight, the number of n-semimatchings in G is maximised by
weighting all edges of G equally. We also introduce sub-Dittert
functions which count k-semimatchings and are analogous to the
subpermanent functions which count k-matchings. We prove some
results about the extremal values of our sub-Dittert functions,
and also that the Dittert conjecture cannot be disproved by means
of unweighted graphs.
Click here to download the whole paper.

Last modified: Tue Jan 23 15:29:26 EST 2007