Dittert conjecture

The Dittert conjecture, or Dittert–Hajek conjecture, is a mathematical hypothesis in combinatorics concerning the maximum achieved by a particular function $\varphi$ of matrices with real, nonnegative entries satisfying a summation condition. The conjecture is due to Eric Dittert and (independently) Bruce Hajek.

Let $A=[a_{ij}]$ be a square matrix of order $n$ with nonnegative entries and with ${\sum }_{i=1}^n\left({\sum }_{j=1}^n{a}_{ij}\right)=n$. Its permanent is defined as $$\mathrm{per}(A)=\sum _{\sigma \in S_n}\prod _{i=1}^n{a}_{i,\sigma (i)},$$ where the sum extends over all elements $\sigma$ of the symmetric group.

The Dittert conjecture asserts that the function $\mathrm{\varphi }(A)$ defined by ${\prod }_{i=1}^n\left({\sum }_{j=1}^n{a}_{ij}\right)+{\prod }_{j=1}^n\left({\sum }_{i=1}^n{a}_{ij}\right)-\mathrm{per}(A)$ is (uniquely) maximized when $A=(1/n)J_n$, where $J_n$ is defined to be the square matrix of order $n$ with all entries equal to 1.

References

Template:Combin-stub