{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,10]],"date-time":"2025-01-10T05:10:11Z","timestamp":1736485811843,"version":"3.32.0"},"reference-count":21,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T00:00:00Z","timestamp":1701129600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T00:00:00Z","timestamp":1701129600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/100007691","name":"Universidade da Beira Interior","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007691","id-type":"DOI","asserted-by":"crossref"}]},{"DOI":"10.13039\/100007691","name":"Universidade da Beira Interior","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100007691","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Order"],"published-print":{"date-parts":[[2024,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Let <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{\\mathcal {A}(n,k)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> represent the collection of all <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{n\\times n}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>\u00d7<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> zero-and-one matrices, with the sum of all rows and columns equalling <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{k}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>k<\/mml:mi>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. This set can be ordered by an extension of the classical Bruhat order for permutations, seen as permutation matrices. The Bruhat order on <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{\\mathcal {A}(n,k)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> differs from the Bruhat order on permutations matrices not being, in general, graded, which results in some intriguing issues. In this paper, we focus on the maximum length of antichains in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{\\mathcal {A}(n,k)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with the Bruhat order. The crucial fact that allows us to obtain our main results is that two distinct matrices in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{\\mathcal {A}(n,k)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> with an identical number of inversions cannot be compared using the Bruhat order. We construct sets of matrices in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{\\mathcal {A}(n,k)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula> so that each set consists of matrices with the same number of inversions. These sets are hence antichains in <jats:inline-formula><jats:alternatives><jats:tex-math>$$\\varvec{\\mathcal {A}(n,k)}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\">\n                  <mml:mrow>\n                    <mml:mi>A<\/mml:mi>\n                    <mml:mo>(<\/mml:mo>\n                    <mml:mi>n<\/mml:mi>\n                    <mml:mo>,<\/mml:mo>\n                    <mml:mi>k<\/mml:mi>\n                    <mml:mo>)<\/mml:mo>\n                  <\/mml:mrow>\n                <\/mml:math><\/jats:alternatives><\/jats:inline-formula>. We use these sets to deduce lower bounds for the maximum length of antichains in these partially ordered sets.<\/jats:p>","DOI":"10.1007\/s11083-023-09654-6","type":"journal-article","created":{"date-parts":[[2023,11,28]],"date-time":"2023-11-28T03:02:07Z","timestamp":1701140527000},"page":"709-719","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Antichains in the Bruhat Order for the Classes $$\\mathcal {A}(n,k)$$"],"prefix":"10.1007","volume":"41","author":[{"given":"Henrique F.","family":"da Cruz","sequence":"first","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2023,11,28]]},"reference":[{"key":"9654_CR1","doi-asserted-by":"publisher","first-page":"159","DOI":"10.1016\/0024-3795(80)90105-6","volume":"33","author":"RA Brualdi","year":"1980","unstructured":"Brualdi, R.A.: Matrices of zeros and ones with fixed row and column sum vectors. Linear Algebra Appl. 33, 159\u2013231 (1980)","journal-title":"Linear Algebra Appl."},{"key":"9654_CR2","first-page":"157","volume":"4","author":"RA Brualdi","year":"2001","unstructured":"Brualdi, R.A.: Short proofs of the Gale & Ryser and Ford & Fulkerson characterizations of the row and column sum vectors of $$(0, 1)$$-matrices. Math. Inequal. Appl. 4, 157\u2013159 (2001)","journal-title":"Math. Inequal. Appl."},{"key":"9654_CR3","doi-asserted-by":"crossref","unstructured":"Brualdi, R.A.: Combinatorial matrix classes. Encyclopedia of Mathematics and its Applications, vol. 108. Cambridge University Press, Cambridge (2006)","DOI":"10.1017\/CBO9780511721182"},{"issue":"2\u20133","key":"9654_CR4","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/j.laa.2006.03.034","volume":"421","author":"RA Brualdi","year":"2007","unstructured":"Brualdi, R.A., Deaett, L.: More on the Bruhat order for (0, 1)-matrices. Linear Algebra Appl. 421(2\u20133), 219\u2013232 (2007)","journal-title":"Linear Algebra Appl."},{"key":"9654_CR5","doi-asserted-by":"publisher","first-page":"6","DOI":"10.13001\/1081-3810.1141","volume":"12","author":"RA Brualdi","year":"2005","unstructured":"Brualdi, R.A., Hwang, S.-G.: A Bruhat order for the class of (0, 1)-matrices with row sum vector R and column sum vector S. Electron. J. Linear Algebra 12, 6\u201316 (2005)","journal-title":"Electron. J. Linear Algebra"},{"key":"9654_CR6","doi-asserted-by":"publisher","first-page":"49","DOI":"10.1016\/j.dam.2018.10.039","volume":"258","author":"RA Brualdi","year":"2018","unstructured":"Brualdi, R.A., Fernandes, R., Furtado, S.: On the Bruhat order of labeled graphs. Discrete Appl. Math 258, 49\u201364 (2018)","journal-title":"Discrete Appl. Math"},{"issue":"3","key":"9654_CR7","doi-asserted-by":"publisher","first-page":"753","DOI":"10.1016\/j.laa.2011.07.043","volume":"436","author":"A Conflitti","year":"2012","unstructured":"Conflitti, A., da Fonseca, C.M., Mamede, R.: The maximal length of a chain in the Bruhat order for a class of binary matrices. Linear Algebra Appl. 436(3), 753\u2013757 (2012)","journal-title":"Linear Algebra Appl."},{"issue":"1","key":"9654_CR8","doi-asserted-by":"publisher","first-page":"255","DOI":"10.1007\/s11083-011-9241-1","volume":"30","author":"A Conflitti","year":"2013","unstructured":"Conflitti, A., da Fonseca, C.M., Mamede, R.: On the largest size of an antichain in the Bruhat order for A(2k, k). Order 30(1), 255\u2013260 (2013)","journal-title":"Order"},{"key":"9654_CR9","doi-asserted-by":"publisher","first-page":"160","DOI":"10.1016\/j.laa.2017.05.014","volume":"530","author":"HF da Cruz","year":"2017","unstructured":"da Cruz, H.F., Fernandes, R., Furtado, S.: Minimal matrices in the Bruhat order for symmetric (0,1)-matrices. Linear Algebra Appl. 530, 160\u2013184 (2017)","journal-title":"Linear Algebra Appl."},{"issue":"2","key":"9654_CR10","doi-asserted-by":"publisher","first-page":"161","DOI":"10.2307\/1969503","volume":"51","author":"RP Dilworth","year":"1950","unstructured":"Dilworth, R.P.: A decomposition theorem for partially ordered sets. Ann. Math. 51(2), 161\u2013166 (1950)","journal-title":"Ann. Math."},{"key":"9654_CR11","doi-asserted-by":"publisher","first-page":"82","DOI":"10.1016\/j.laa.2020.04.015","volume":"600","author":"R Fernandes","year":"2020","unstructured":"Fernandes, R., da Cruz, H.F., Salom\u00e3o, D.: On a conjecture concerning the Bruhat order. Linear Algebra Appl. 600, 82\u201395 (2020)","journal-title":"Linear Algebra Appl."},{"key":"9654_CR12","doi-asserted-by":"publisher","first-page":"831","DOI":"10.2140\/pjm.1960.10.831","volume":"10","author":"DR Fulkerson","year":"1960","unstructured":"Fulkerson, D.R.: Zero-one matrices with zero trace. Pac. J. Math. 10, 831\u2013836 (1960)","journal-title":"Pac. J. Math."},{"key":"9654_CR13","doi-asserted-by":"publisher","first-page":"1073","DOI":"10.2140\/pjm.1957.7.1073","volume":"7","author":"D Gale","year":"1957","unstructured":"Gale, D.: A theorem on flows in networks. Pac. J. Math. 7, 1073\u20131082 (1957)","journal-title":"Pac. J. Math."},{"key":"9654_CR14","doi-asserted-by":"publisher","first-page":"377","DOI":"10.1016\/j.laa.2014.01.002","volume":"446","author":"M Ghebleh","year":"2014","unstructured":"Ghebleh, M.: On maximum chains in the Bruhat order of $$\\cal{A} (n, 2)$$. Linear Algebra Appl. 446, 377\u2013387 (2014)","journal-title":"Linear Algebra Appl."},{"key":"9654_CR15","doi-asserted-by":"publisher","first-page":"503","DOI":"10.1016\/j.laa.2014.06.021","volume":"458","author":"M Ghebleh","year":"2014","unstructured":"Ghebleh, M.: Antichains of (0, 1)-matrices through inversions. Linear Algebra Appl. 458, 503\u2013511 (2014)","journal-title":"Linear Algebra Appl."},{"key":"9654_CR16","first-page":"24","volume":"30","author":"RM Haber","year":"1960","unstructured":"Haber, R.M.: Term rank of (0, l)-matrices. Rend. Sem. Mat. Univ. Padova 30, 24\u201351 (1960)","journal-title":"Rend. Sem. Mat. Univ. Padova"},{"key":"9654_CR17","doi-asserted-by":"publisher","first-page":"876","DOI":"10.1080\/00029890.1971.11992886","volume":"78","author":"L Mirsky","year":"1971","unstructured":"Mirsky, L.: A dual of Dilworth\u2019s decomposition theorem. Am. Math. Mon. 78, 876\u2013877 (1971)","journal-title":"Am. Math. Mon."},{"key":"9654_CR18","doi-asserted-by":"publisher","first-page":"361","DOI":"10.1016\/S0012-365X(01)00472-1","volume":"256","author":"BR P\u00e9rez-Salvador","year":"2002","unstructured":"P\u00e9rez-Salvador, B.R., De-los-Cobos-Silva, S., Guti\u00e9\u00e9rrez-\u00c1ndrade, M.A., Torres-Chazaro, A.: A reduced formula for the precise number of (0,1)-matrices in $$\\cal{A} (R, S)$$. Discrete Math. 256, 361\u2013372 (2002)","journal-title":"Discrete Math."},{"key":"9654_CR19","doi-asserted-by":"publisher","first-page":"371","DOI":"10.4153\/CJM-1957-044-3","volume":"9","author":"HJ Ryser","year":"1957","unstructured":"Ryser, H.J.: Combinatorial properties of matrices of zeros and ones. Canad. J. Math. 9, 371\u2013377 (1957)","journal-title":"Canad. J. Math."},{"key":"9654_CR20","doi-asserted-by":"publisher","first-page":"211","DOI":"10.1016\/S0012-365X(97)00197-0","volume":"187","author":"B Wang","year":"1998","unstructured":"Wang, B., Zhang, F.: On the precise number of $$(0, 1)$$-matrices in $$\\cal{U} (R, S)$$. Discrete Math. 187, 211\u2013220 (1998)","journal-title":"Discrete Math."},{"key":"9654_CR21","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1016\/0012-365X(82)90152-2","volume":"39","author":"Wan-Di Wei","year":"1982","unstructured":"Wei, Wan-Di.: The class $$\\cal{A} (R, S)$$ of $$(0,1)$$-matrices. Discrete Math. 39, 301\u2013305 (1982)","journal-title":"Discrete Math."}],"container-title":["Order"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-023-09654-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1007\/s11083-023-09654-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/s11083-023-09654-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,9]],"date-time":"2025-01-09T07:10:12Z","timestamp":1736406612000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/s11083-023-09654-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,28]]},"references-count":21,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2024,12]]}},"alternative-id":["9654"],"URL":"https:\/\/doi.org\/10.1007\/s11083-023-09654-6","relation":{},"ISSN":["0167-8094","1572-9273"],"issn-type":[{"type":"print","value":"0167-8094"},{"type":"electronic","value":"1572-9273"}],"subject":[],"published":{"date-parts":[[2023,11,28]]},"assertion":[{"value":"2 May 2023","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"2 November 2023","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"28 November 2023","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The author does not have any conflict of interest to declare.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Conflict of Interests"}},{"value":"The authors declare no competing interests.","order":3,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing Interests"}}]}}