An interpretation of the Dittert conjecture in terms of semi-matchings (Q2455576): Difference between revisions

Let \(G\) be a complete bipartite graph with non-negative edge weights and with bipartition \(G = U \sqcup V\) where \(| U| = | V| = n\). A \(k\)-semimatching in \(G\) is a set of \(k\) edges such that the edges have distinct ends in \(U\) or distinct ends in \(V\). The weight of a \(k\)-semimatching is the product of the weights of the involved edges. The authors prove that the Dittert conjecture is equivalent to the following assertion: For a fixed total weight, the number of \(n\)-semimatchings of that weight in \(G\) is maximized by weighting all edges of \(G\) equally. The authors also prove that the methods they have been used to disprove the Holens-Dokovic conjecture cannot be used to disprove the Dittert conjecture.