The main paper @article {GrahamPollak, AUTHOR = {Graham, R. L. and Pollak, H. O.}, TITLE = {On the addressing problem for loop switching}, JOURNAL = {Bell System Tech. J.}, FJOURNAL = {The Bell System Technical Journal}, VOLUME = {50}, YEAR = {1971}, PAGES = {2495--2519}, DOI = {10.1002/j.1538-7305.1971.tb02618.x}, URL = {https://doi.org/10.1002/j.1538-7305.1971.tb02618.x}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Our work @mastersThesis{EsquiviasThesis, author = {Esquivias Quintero, Luis}, title = {Generalizaciones de la fórmula de {G}raham-{P}ollak. Una prueba combinatoria.}, type = {Tesis de Grado}, institution = {Universidad de Sevilla}, date = {June 2023}, year = {2023}, language = {spanish}, note = {Bajo la dirección de Mercedes Rosas}, OPTeid = {}, OPTdoi = {}, OPTurl = {}, } @mastersThesis{LilloThesis, author = {Lillo Pinto, Adrián}, title = {Una prueba combinatoria de {G}raham-{P}ollak.}, type = {Tesis de Grado}, institution = {Universidad de Sevilla}, date = {July 2023}, year = {2023}, language = {spanish}, note = {Bajo la dirección de Mercedes Rosas}, OPTeid = {}, OPTdoi = {}, OPTurl = {}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% People asking for a combinatorial proof. @MastersThesis{TilliaThesis, author = {Tillia, Valerie}, title = {Determinants of Distance Matrices of Trees}, school = {Portland State University}, year = {2010}, url = {http://web.pdx.edu/~caughman/Valerie501.pdf}, quote = {Although it is not immediately or intuitively clear why the determinant has no regard for the tree’s structure, it may help to recall that a tree of n vertices always has $n-1$ edges. Edges are directly related to distance, and the term n-1 appears in the formula. In my discussions with others and research in other articles, still nowhere have I found a satisfying intuitive explanation for why the determinant is expressed by such a formula. The formula $(-1)^{n-1} 2^{n-2} (n-1)$ seems to be a counting problem. Ignoring sign, it could be counting the number of ways to first pick an edge in the tree, then whether to include or exclude each remaining edge. The sign of the determinant depends on the number of vertices in the tree. An even number of vertices will yield a negative determinant while an odd number gives a positive. How does the determinant relate geometrically to the number of edges in a tree?} } @misc{LeqiZhou, author = {Zhou, Leqi}, title = {Determinants of Distance Matrices of Trees}, incollection = {Euler circle papers}, url={http://simonrs.com/eulercircle/pftb2020/leqi-determinants.pdf}, year = 2020, quote={"Looking at the formula combinatorially, one might think that the formula is counting the number of ways to pick an edge then decide whether to include/exclude the rest of the edges. Is this the case?" (4. Questions and Remarks)}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DEFORMATIONS q-analogues and "exponential of the distance" @article {BapatLalPati, AUTHOR = {Bapat, R. B. and Lal, A. K. and Pati, Sukanta}, TITLE = {A {$q$}-analogue of the distance matrix of a tree}, JOURNAL = {Linear Algebra Appl.}, FJOURNAL = {Linear Algebra and its Applications}, VOLUME = {416}, YEAR = {2006}, NUMBER = {2-3}, PAGES = {799--814}, DOI = {10.1016/j.laa.2005.12.023}, } Variables for the edges: @article{BapatKirklandNeumann, author = {R. Bapat and S.J. Kirkland and M. Neumann}, title = {On distance matrices and Laplacians}, journal = {Linear Algebra and its Applications}, volume = {401}, pages = {193-209}, year = {2005}, note = {Special Issue in honor of Graciano de Oliveira}, issn = {0024-3795}, doi = {10.1016/j.laa.2004.05.011}, } q-analogue, with and without variables for the edges @article {YanYeh:2007, AUTHOR = {Yan, Weigen and Yeh, Yeong-Nan}, TITLE = {The determinants of {$q$}-distance matrices of trees and two quantiles relating to permutations}, JOURNAL = {Adv. in Appl. Math.}, FJOURNAL = {Advances in Applied Mathematics}, VOLUME = {39}, YEAR = {2007}, NUMBER = {3}, PAGES = {311--321}, DOI = {10.1016/j.aam.2006.04.002}, } Variables for the oriented edges @article {BapatLalPati2009, AUTHOR = {Bapat, R. B. and Lal, A. K. and Pati, Sukanta}, TITLE = {The distance matrix of a bidirected tree}, JOURNAL = {Electron. J. Linear Algebra}, FJOURNAL = {Electronic Journal of Linear Algebra}, VOLUME = {18}, YEAR = {2009}, PAGES = {233--245}, DOI = {10.13001/1081-3810.1308}, //URL = {https://doi.org/10.13001/1081-3810.1308}, } @article{ZhouDing, title = {The distance matrix of a tree with weights on its arcs}, author = {Hui Zhou and Qi Ding}, journal = {Linear Algebra and its Applications}, volume = {511}, pages = {365-377}, year = {2016}, issn = {0024-3795}, doi = {10.1016/j.laa.2016.09.028}, } Big generalization covering all of the previous stuff @article{CK19-old, //title = {Distance matrices of a tree: two more invariants, and in a unified framework}, author = {Choudhury, Projesh Nath and Khare, Apoorva}, //doi = {10.48550/arxiv.1903.11566}, journal = {arXiv e-prints}, archivePrefix = {arXiv}, eprint = {1903.11566}, primaryClass = "math.CO", year = {2019}, } @article{CK19, title = {Distance matrices of a tree: Two more invariants, and in a unified framework}, journal = {European Journal of Combinatorics}, volume = {115}, pages = {103787}, year = {2024}, issn = {0195-6698}, doi = {https://doi.org/10.1016/j.ejc.2023.103787}, url = {https://www.sciencedirect.com/science/article/pii/S019566982300104X}, author = {Projesh Nath Choudhury and Apoorva Khare}, } @article{CK23, title = {The additive-multiplicative distance matrix of a graph, and a novel third invariant}, author = {Choudhury, Projesh Nath and Khare, Apoorva}, //doi = {10.48550/arXiv.2309.08691}, journal = {arXiv e-prints}, archivePrefix = {arXiv}, eprint = {2309.08691}, primaryClass = "math.CO", year = {2023}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Alternative proofs of the Graham-Pollak Theorem: %% other proofs @article{YanYeh, AUTHOR = {Yan, Weigen and Yeh, Yeong-Nan}, TITLE = {A simple proof of {G}raham and {P}ollak's theorem}, JOURNAL = {J. Combin. Theory Ser. A}, FJOURNAL = {Journal of Combinatorial Theory. Series A}, VOLUME = {113}, YEAR = {2006}, NUMBER = {5}, PAGES = {892--893}, ISSN = {0097-3165}, DOI = {10.1016/j.jcta.2005.07.005}, } @article {DuYeh, AUTHOR = {Du, Zhibin and Yeh, Jean}, TITLE = {Another simple proof of {G}raham and {P}ollak's theorem}, JOURNAL = {Discrete Math.}, FJOURNAL = {Discrete Mathematics}, VOLUME = {343}, YEAR = {2020}, NUMBER = {10}, PAGES = {111994, 3}, ISSN = {0012-365X}, MRCLASS = {05C50 (05C12)}, MRNUMBER = {4103841}, MRREVIEWER = {Jephian C.-H. Lin}, DOI = {10.1016/j.disc.2020.111994}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Distance polynomial of a tree: @incollection {GrahamLovasz:1978:Orsay, AUTHOR = {Graham, R. L. and Lov\'{a}sz, L.}, TITLE = {Distance matrix polynomials of trees}, BOOKTITLE = {Probl\`emes combinatoires et th\'{e}orie des graphes}, SERIES = {Colloq. Internat.}, VOLUME = {260}, PAGES = {189--190}, PUBLISHER = {CNRS, Paris}, YEAR = {1978}, MRCLASS = {05C05}, MRNUMBER = {539974}, } @article {GrahamLovasz, AUTHOR = {Graham, R. L. and Lov\'{a}sz, L.}, TITLE = {Distance matrix polynomials of trees}, JOURNAL = {Adv. in Math.}, FJOURNAL = {Advances in Mathematics}, VOLUME = {29}, YEAR = {1978}, NUMBER = {1}, PAGES = {60--88}, ISSN = {0001-8708}, DOI = {10.1016/0001-8708(78)90005-1}, } @article {EdelbergGarayGraham, AUTHOR = {Edelberg, M. and Garey, M. R. and Graham, R. L.}, TITLE = {On the distance matrix of a tree}, JOURNAL = {Discrete Math.}, FJOURNAL = {Discrete Mathematics}, VOLUME = {14}, YEAR = {1976}, NUMBER = {1}, PAGES = {23--39}, ISSN = {0012-365X}, DOI = {10.1016/0012-365X(76)90003-0}, } @article {Aaliapour_et_al, AUTHOR = {Aalipour, Ghodratollah and Abiad, Aida and Berikkyzy, Zhanar and Hogben, Leslie and Kenter, Franklin H. J. and Lin, Jephian C.-H. and Tait, Michael}, TITLE = {Proof of a conjecture of {G}raham and {L}ov\'{a}sz concerning unimodality of coefficients of the distance characteristic polynomial of a tree}, JOURNAL = {Electron. J. Linear Algebra}, FJOURNAL = {Electronic Journal of Linear Algebra}, VOLUME = {34}, YEAR = {2018}, PAGES = {373--380}, DOI = {10.13001/1081-3810.3493}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% About the Gessel-Viennot lemma @article {Gessel-Viennot, AUTHOR = {Gessel, Ira and Viennot, G\'{e}rard}, TITLE = {Binomial determinants, paths, and hook length formulae}, JOURNAL = {Adv. in Math.}, FJOURNAL = {Advances in Mathematics}, VOLUME = {58}, YEAR = {1985}, NUMBER = {3}, PAGES = {300--321}, DOI = {10.1016/0001-8708(85)90121-5}, //URL = {https://doi.org/10.1016/0001-8708(85)90121-5}, } @book{sagan2020combinatorics, title={Combinatorics: The art of counting}, author={Sagan, Bruce E}, volume={210}, year={2020}, publisher={American Mathematical Soc.} } @article{BenjaminCameron, URL = {http://www.jstor.org/stable/30037518}, author = {Arthur T. Benjamin and Naiomi T. Cameron}, journal = {The American Mathematical Monthly}, number = {6}, pages = {481--492}, publisher = {Mathematical Association of America}, title = {Counting on Determinants}, urldate = {2022-07-22}, volume = {112}, year = {2005}, doi = {0.2307/30037518}, } @book {Proofs, AUTHOR = {Aigner, Martin and Ziegler, G\"{u}nter M.}, TITLE = {Proofs from {T}he {B}ook}, EDITION = {Sixth}, PUBLISHER = {Springer, Berlin}, YEAR = {2018}, DOI = {10.1007/978-3-662-57265-8}, } @article {Lindstrom, AUTHOR = {Lindstr\"{o}m, Bernt}, TITLE = {On the vector representations of induced matroids}, JOURNAL = {Bull. London Math. Soc.}, FJOURNAL = {The Bulletin of the London Mathematical Society}, VOLUME = {5}, YEAR = {1973}, PAGES = {85--90}, //ISSN = {0024-6093,1469-2120}, DOI = {10.1112/blms/5.1.85}, //URL = {https://doi.org/10.1112/blms/5.1.85}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% GENERALIZATION TO THE SUM OF ENTRIES OF THE INVERSE MATRIX (see also Chaudhury Khare) @article {GrahamPollakHosoya, AUTHOR = {Graham, R. L. and Hoffman, A. J. and Hosoya, H.}, TITLE = {On the distance matrix of a directed graph}, JOURNAL = {J. Graph Theory}, FJOURNAL = {Journal of Graph Theory}, VOLUME = {1}, YEAR = {1977}, NUMBER = {1}, PAGES = {85--88}, DOI = {10.1002/jgt.3190010116}, //URL = {https://doi.org/10.1002/jgt.3190010116}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% DERANGEMENTS @article {MantaciRakoto, AUTHOR = {Mantaci, Roberto and Rakotondrajao, Fanja}, TITLE = {Exceedingly deranging!}, NOTE = {Proceedings of {FPSAC} 2001}, JOURNAL = {Adv. in Appl. Math.}, FJOURNAL = {Advances in Applied Mathematics}, VOLUME = {30}, YEAR = {2003}, NUMBER = {1-2}, PAGES = {177--188}, ISSN = {0196-8858}, DOI = {10.1016/S0196-8858(02)00531-6}, } @article{Chapman, author = {Robin Chapman}, title = {An involution on derangements}, journal = {Discrete Mathematics}, volume = {231}, number = {1}, pages = {121-122}, year = {2001}, doi = {10.1016/S0012-365X(00)00310-1}, } @misc{AlexanderssonGetachew, doi = {10.48550/ARXIV.2105.08455}, author = {Alexandersson, Per and Getachew Kedebe, Frether}, title = {An involution on derangements preserving excedances and right-to-left minima}, publisher = {arXiv}, note = {arXiv:2105.08455 [math.CO]}, year = {2021}, } @misc{PeiZeng, doi = {10.48550/arxiv.2206.11236}, url = {https://arxiv.org/abs/2206.11236}, author = {Pei, Yanni and Zeng, Jiang}, title = {Counting signed derangements with right-to-left minima and excedances}, publisher = {arXiv}, archivePrefix = {arXiv}, eid = {arXiv:2206.11236 [math.CO]}, eprint = {2206.11236 [math.CO]}, note = {arXiv:2206.11236 [math.CO]}, year = {2022}, } @article {Wang, AUTHOR = {Wang, Xing-Zhuo}, TITLE = {Note on signed excedance enumeration of signed permutations}, JOURNAL = {Ars Combin.}, FJOURNAL = {Ars Combinatoria}, VOLUME = {150}, YEAR = {2020}, PAGES = {311--315}, ISSN = {0381-7032}, DOI = {10.1016/j.apnum.2019.10.004}, } @article {Sivasub, AUTHOR = {Sivasubramanian, Sivaramakrishnan}, TITLE = {Signed excedance enumeration via determinants}, JOURNAL = {Adv. in Appl. Math.}, FJOURNAL = {Advances in Applied Mathematics}, VOLUME = {47}, YEAR = {2011}, NUMBER = {4}, PAGES = {783--794}, ISSN = {0196-8858}, DOI = {10.1016/j.aam.2011.02.003}, } %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Lorentizan polynomials % Other material to cite, not a priori related @article {BrandenHuh, AUTHOR = {Br\"{a}nd\'{e}n, Petter and Huh, June}, TITLE = {Lorentzian polynomials}, JOURNAL = {Ann. of Math. (2)}, FJOURNAL = {Annals of Mathematics. Second Series}, VOLUME = {192}, YEAR = {2020}, NUMBER = {3}, PAGES = {821--891}, ISSN = {0003-486X}, MRCLASS = {52B40 (05A20 14T15)}, MRNUMBER = {4172622}, MRREVIEWER = {Trygve Johnsen}, DOI = {10.4007/annals.2020.192.3.4}, URL = {https://doi.org/10.4007/annals.2020.192.3.4}, }