پیوندهای مفید
اخبار و اعلانات
آمار
| تعداد نشریات | 43 |
| تعداد شمارهها | 1,638 |
| تعداد مقالات | 13,319 |
| تعداد مشاهده مقاله | 29,876,169 |
| تعداد دریافت فایل اصل مقاله | 11,946,530 |
A polynomial associated with rooted trees and specific posets | ||
| Transactions on Combinatorics | ||
| مقاله 7، دوره 11، شماره 3، آذر 2022، صفحه 255-279 اصل مقاله (538.23 K) | ||
| نوع مقاله: Workshop on Graphs, Topology and Topological Groups, Cape Town, South Africa | ||
| شناسه دیجیتال (DOI): 10.22108/toc.2022.130043.1895 | ||
| نویسندگان | ||
| Valisoa Razanajatovo Misanantenaina1؛ Stephan Wagner* 2 | ||
| 1Department of Logistics, Stellenbosch University, Private Bag X1, Matieland 7602, South Africa | ||
| 2Department of Mathematics, Uppsala Universitet, Box 480, 751 06 Uppsala, Sweden | ||
| چکیده | ||
| We investigate a trivariate polynomial associated with rooted trees. It generalises a bivariate polynomial for rooted trees that was recently introduced by Liu. We show that this polynomial satisfies a deletion-contraction recursion and can be expressed as a sum over maximal antichains. Several combinatorial quantities can be obtained as special values, in particular the number of antichains, maximal antichains and cutsets. We prove that two of the three possible bivariate specialisations characterise trees uniquely up to isomorphism. One of these has already been established by Liu, the other is new. For the third specialisation, we construct non-isomorphic trees with the same associated polynomial. We finally find that our polynomial can be generalised in a natural way to a family of posets that we call Ѵ-posets. These posets are obtained recursively by either disjoint unions or adding a greatest/least element to existing Ѵ-posets. | ||
| کلیدواژهها | ||
| Rooted trees؛ polynomials؛ antichains؛ cutsets؛ posets | ||
| مراجع | ||
|
[1] M. Aigner, A course in enumeration, Graduate Texts in Mathematics 238, Springer, Berlin, 2007.
[2] E. O. D. Andriantiana, S. Wagner and H. Wang, Greedy trees, subtrees and antichains, Electron. J. Combin., 20 no. 3 (2013) P28. [3] N. Biggs, Algebraic Graph Theory, Cambridge Mathematical Library, Cambridge University Press, Cambridge, 1993.
[4] I. Bouchemakh and K. Fatma, On the dual K¨onig property of the order-interval hypergraph of two classes of N-free posets, Canad. Math. Bull., 60 no. 1 (2017) 43–53. [5] F. Burghart, A modification of the random cutting model, arXiv:2111.02968, 2021.
[6] V. Campos, V. Chv´atal, L. Devroye and P. Taslakian, Transversals in trees, J. Graph Theory, 73 no. 1 (2013) 32–43.
[7] M. Chari and C. J. Colbourn, Reliability polynomials: a survey, J. Combin. Inform. System Sci., 22 no. 3–4 (1997) 177–193. [8] S. Chaudhary and G. Gordon, Tutte polynomials for trees, J. Graph Theory, 15 no. 3 (1991) 317–331.
[9] J. Cooper, P. Gartland and H. Whitlatch, A new characterization of V-posets, Order, 37 no. 2 (2020) 371–387.
[10] R. Diestel, Graph theory, Graduate Texts in Mathematics, Fifth edition, 173, Springer, Berlin, 2018.
[11] J. D. Farley, How Al Qaeda Can Use Order Theory to Evade or Defeat US Forces: The Case of Binary Posets, in Advances in Network Analysis and its Applications, Springer, 2012 315–322. [12] S. Felsner and T. Manneville, Linear extensions of N-free orders, Order, 32 no. 2 (2015) 147–155.
[13] P. Gibson and R. Maltby, Posets in which every cutset meets every fibre, Discrete Math., 194 no. 1–3 (1999) 107–127.
[14] B. Gittenberger and V. Kraus, On the number of transversals in random trees, in 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA’12), Discrete Mathematics and Theoretical Computer Science, 2012 141–154. [15] M. Habib and R. J´egou, N-free posets as generalizations of series-parallel posets, Discrete Appl. Math., 12 no. 3 (1985) 279–291. [16] T. Hasebe and S. Tsujie, Order quasisymmetric functions distinguish rooted trees, J. Algebraic Combin., 46 no. 3-4 (2017) 499–515. [17] M. Klazar, Twelve countings with rooted plane trees, European J. Combin., 18 no. 2 (1997) 195–210.
[18] S. Lang, Algebra, Revised third edition, Graduate Texts in Mathematics, 211, Springer-Verlag, New York, 2002.
[19] F. Lehner and S. Wagner, Free lamplighter groups and a question of Atiyah, Amer. J. Math., 135 no. 3 (2013) 835–849. [20] P. Liu, A tree distinguishing polynomial, Discrete Appl. Math., 288 (2021) 1–8.
[21] A. J. Schwenk, Almost all trees are cospectral, in New directions in the theory of graphs (Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971), Academic Press, New York, 1973 275–307. [22] W. T. Tutte, A ring in graph theory, Proc. Cambridge Philos. Soc. 43 (1947), 26–40.
[23] W. T. Tutte, A contribution to the theory of chromatic polynomials, Canad. J. Math., 6 (1954) 80–91.
[24] S. Wagner, Central limit theorems for additive tree parameters with small toll functions, Combin. Probab. Comput., 24 no. 1 (2015) 329–353. [25] I. Zaguia, The 1/3-2/3 conjecture for N-free ordered sets, Electron. J. Combin., 19 no. 2 (2012) P29. | ||
|
آمار تعداد مشاهده مقاله: 334 تعداد دریافت فایل اصل مقاله: 213 |
||