×

An interpretation of the Dittert conjecture in terms of semi-matchings. (English) Zbl 1126.05079

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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
15A15 Determinants, permanents, traces, other special matrix functions
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Brualdi, R. A.; Newman, M., Inequalities for the permanental minors of non-negative matrices, Canad. J. Math., 18, 608-615 (1966) · Zbl 0145.03803
[2] Cheon, G.-S., On the monotonicity of the Dittert function on classes of nonnegative matrices, Bull. Korean Math. Soc., 30, 265-275 (1993) · Zbl 0785.15009
[3] Cheon, G.-S.; Hwang, S.-G., Maximization of a matrix function related to the Dittert conjecture, Linear Algebra Appl., 165, 153-165 (1992) · Zbl 0744.15020
[4] Cheon, G.-S.; Wanless, I. M., An update on Minc’s survey of open problems involving permanents, Linear Algebra Appl., 403, 314-342 (2005) · Zbl 1078.15005
[5] Donald, J.; Elwin, J.; Hager, R.; Salamon, P., A graph theoretic upper bound on the permanent of a non-negative integer matrix I, Linear Algebra Appl., 61, 187-198 (1984) · Zbl 0551.15005
[6] Friedland, S., A proof of a generalized van der Waerden conjecture on permanents, Linear and Multilinear Algebra, 11, 107-120 (1982) · Zbl 0482.15003
[7] Hwang, S.-G., A note on a conjecture on permanents, Linear Algebra Appl., 76, 31-44 (1986) · Zbl 0589.15016
[8] Hwang, S.-G., On a conjecture of E. Dittert, Linear Algebra Appl., 95, 161-169 (1987) · Zbl 0628.15018
[9] Hwang, S.-G.; Sohn, M.-G.; Kim, S.-J., The Dittert’s function on a set of nonnegative matrices, Internat. J. Math. Math. Sci., 13, 709-716 (1990) · Zbl 0724.15016
[10] Minc, H., Theory of permanents 1978-1981, Linear and Multilinear Algebra, 12, 227-263 (1983) · Zbl 0511.15002
[11] Sinkhorn, R., A problem related to the van der Waerden permanent theorem, Linear and Multilinear Algebra, 16, 167-173 (1984) · Zbl 0568.15004
[12] Song, S.-Z.; Hwang, S.-G.; Rim, S.-H.; Cheon, G.-S., Extremes of permanents of (0,1)-matrices, Linear Algebra Appl., 373, 197-210 (2003) · Zbl 1048.15009
[13] Steele, J. M., Euclidean semi-matchings of random samples, Math. Programming Ser. A, 53, 127-146 (1992) · Zbl 0783.90119
[14] Wanless, I. M., The Holens-Doković conjecture on permanents fails, Linear Algebra Appl., 286, 273-285 (1999) · Zbl 0941.15003
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.