{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:47:17Z","timestamp":1787323637884,"version":"build-2736575974"},"reference-count":36,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2014,1]]},"abstract":"<jats:p>Phylogenetic tree reconstruction is a fundamental biological problem. Quartet trees, trees over four species, are the minimal informational unit for phylogenetic classification. While every phylogenetic tree over $n$ species defines ${n \\choose 4}$ quartets, not every set of quartets is compatible with some phylogenetic tree. Here we focus on the compatibility of quartet sets. We provide several results addressing the question of what can be inferred about the compatibility of a set from its subsets. Most of our results use probabilistic arguments to prove the sought characteristics. In particular we show that there are quartet sets $Q$ of size $m=c n \\log n$ in which every subset of cardinality $c' n\/ \\log n$ is compatible, and yet no fraction of more than $1\/3+\\epsilon$ of $Q$ is compatible. On the other hand, in contrast to the classical result stating when $Q$ is the densest, i.e., $m={n \\choose 4}$ and the compatibility of any set of three quartets implies full compatibility, we show that even for $m=\\Theta\\big({n \\choose 4}\\big)$ there are (very) incompatible sets for which every subset of large constant cardinality is compatible. Our final result relates to the conjecture of Bandelt and Dress regarding the maximum quartet distance between trees. We provide asymptotic upper and lower bounds for this value.<\/jats:p>","DOI":"10.1137\/130941043","type":"journal-article","created":{"date-parts":[[2014,9,25]],"date-time":"2014-09-25T15:54:44Z","timestamp":1411660484000},"page":"1493-1507","source":"Crossref","is-referenced-by-count":5,"title":["On the Compatibility of Quartet Trees"],"prefix":"10.1137","volume":"28","author":[{"given":"Noga","family":"Alon","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sagi","family":"Snir","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Raphael","family":"Yuster","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2014,9,25]]},"reference":[{"key":"atypb1","doi-asserted-by":"crossref","unstructured":"N. Alon and J.H. Spencer,\n                      The Probabilistic Method\n                      , 2nd ed., Wiley-Interscience, New York, 2000.","DOI":"10.1002\/0471722154"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/0196-8858(86)90038-2"},{"key":"atypb3","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00235-2"},{"key":"atypb4","first-page":"313","author":"Berry V.","year":"1999","journal-title":"Berlin"},{"key":"atypb5","doi-asserted-by":"crossref","unstructured":"O. Bininda-Emonds, ed.\n                      Phylogenetic Supertrees: Combining Information to Reveal the Tree of Life\n                      , Comput. Biol. 4, Kluwer Academic Publishers, Dordrecht, The Netherlands, 2004.","DOI":"10.1007\/978-1-4020-2330-9"},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1146\/annurev.ecolsys.33.010802.150511"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1116"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2005.10.033"},{"key":"atypb9","doi-asserted-by":"publisher","DOI":"10.1006\/aama.1995.1020"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.2000.1133"},{"key":"atypb11","first-page":"376","volume":"23","author":"Cayley A.","year":"1889","journal-title":"Quart. J. Math"},{"key":"atypb12","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-010-9276-5"},{"key":"atypb13","doi-asserted-by":"publisher","DOI":"10.1111\/j.2044-8317.1981.tb00626.x"},{"key":"atypb14","unstructured":"T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein,\n                      Introduction to Algorithms.\n                      , 2nd ed., MIT Press, Cambridge, MA, 2001."},{"key":"atypb15","doi-asserted-by":"publisher","DOI":"10.1089\/10665270252935467"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1137\/09075576X"},{"key":"atypb17","first-page":"5","volume":"16","author":"D","year":"1983","journal-title":"Ars Combin."},{"key":"atypb18","unstructured":"M. Dekker,\n                      Reconstruction Methods for Derivation Trees\n                      , Masters thesis, Vrije Universiteit, Amsterdam, 1986."},{"key":"atypb19","first-page":"395","author":"Dezulian T.","year":"2004","journal-title":"Heidelberg"},{"key":"atypb20","doi-asserted-by":"publisher","DOI":"10.1002\/(SICI)1098-2418(199903)14:2<153::AID-RSA3>3.0.CO;2-R"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(99)00028-6"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.2307\/sysbio\/34.2.193"},{"key":"atypb23","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20372"},{"key":"atypb24","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2011.09.007"},{"key":"atypb25","doi-asserted-by":"publisher","DOI":"10.1016\/j.mbs.2006.11.005"},{"key":"atypb26","doi-asserted-by":"crossref","unstructured":"T. Jiang, P. Kearney, and M. Li,\n                      Orchestrating quartets: Approximation and data correction\n                      , in Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, Palo Alto, CA, 1998, pp. 416-425.","DOI":"10.1109\/SFCS.1998.743492"},{"key":"atypb27","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799361683"},{"key":"atypb28","doi-asserted-by":"publisher","DOI":"10.1016\/0025-5564(81)90043-2"},{"key":"atypb29","doi-asserted-by":"crossref","unstructured":"C. Semple and M. A. Steel,\n                      Phylogenetics\n                      , Oxford University Press, Oxford, UK, 2003.","DOI":"10.1093\/oso\/9780198509424.001.0001"},{"key":"atypb30","doi-asserted-by":"publisher","DOI":"10.1186\/1748-7188-8-11"},{"key":"atypb31","doi-asserted-by":"crossref","unstructured":"S. Snir and S. Rao,\n                      Quartets maxcut: A divide and conquer quartets algorithm\n                      , IEEE\/ACM Trans. Comput. Biol. Bioinformatics (TCBB), 7 (2010), pp. 714-718.","DOI":"10.1109\/TCBB.2008.133"},{"key":"atypb32","doi-asserted-by":"publisher","DOI":"10.1137\/110820555"},{"key":"atypb33","doi-asserted-by":"publisher","DOI":"10.1137\/11086964X"},{"key":"atypb34","first-page":"196","author":"John K. St.","year":"2001","journal-title":"Proceedings of the Twelfth Annual ACM-SIAM Symposium on Discrete Algorithms"},{"key":"atypb35","doi-asserted-by":"publisher","DOI":"10.1007\/BF02618470"},{"key":"atypb36","doi-asserted-by":"publisher","DOI":"10.1093\/oxfordjournals.molbev.a025664"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/130941043","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:11:19Z","timestamp":1787321479000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/130941043"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,1]]},"references-count":36,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2014,1]]}},"alternative-id":["10.1137\/130941043"],"URL":"https:\/\/doi.org\/10.1137\/130941043","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,1]]}}}