Recent zbMATH articles in MSC 05C30https://zbmath.org/atom/cc/05C302024-03-13T18:33:02.981707ZWerkzeugLattice paths and branched continued fractions: an infinite sequence of generalizations of the Stieltjes-Rogers and Thron-Rogers polynomials, with coefficientwise Hankel-total positivityhttps://zbmath.org/1528.050012024-03-13T18:33:02.981707Z"Pétréolle, Mathias"https://zbmath.org/authors/?q=ai:petreolle.mathias"Sokal, Alan D."https://zbmath.org/authors/?q=ai:sokal.alan-d"Zhu, Bao-Xuan"https://zbmath.org/authors/?q=ai:zhu.baoxuanSummary: We define an infinite sequence of generalizations, parametrized by an integer \(m \ge 1\), of the Stieltjes-Rogers and Thron-Rogers polynomials; they arise as the power-series expansions of some branched continued fractions, and as the generating polynomials for \(m\)-Dyck and \(m\)-Schröder paths with height-dependent weights. We prove that all of these sequences of polynomials are coefficientwise Hankel-totally positive, jointly in all the (infinitely many) indeterminates. We then apply this theory to prove the coefficientwise Hankel-total positivity for combinatorially interesting sequences of polynomials. Enumeration of unlabeled ordered trees and forests gives rise to multivariate Fuss-Narayana polynomials and Fuss-Narayana symmetric functions. Enumeration of increasing (labeled) ordered trees and forests gives rise to multivariate Eulerian polynomials and Eulerian symmetric functions, which include the univariate \(m\)th-order Eulerian polynomials as specializations. We also find branched continued fractions for ratios of contiguous hypergeometric series \({}_r \! F_s\) for arbitrary \(r\) and \(s\), which generalize Gauss' continued fraction for ratios of contiguous \({}_2 \! F_1\); and for \(s=0\) we prove the coefficientwise Hankel-total positivity. Finally, we extend the branched continued fractions to ratios of contiguous basic hypergeometric series \({}_r \! \phi_s\).Counting maximal independent sets in some \(n\)-gonal cactihttps://zbmath.org/1528.050352024-03-13T18:33:02.981707Z"Klamsakul, Natawat"https://zbmath.org/authors/?q=ai:klamsakul.natawat"Thengarnanchai, Pantaree"https://zbmath.org/authors/?q=ai:thengarnanchai.pantaree"Suebtangjai, Mattanaporn"https://zbmath.org/authors/?q=ai:suebtangjai.mattanaporn"Kaewperm, Pailin"https://zbmath.org/authors/?q=ai:kaewperm.pailin"Songsuwan, Nuttanon"https://zbmath.org/authors/?q=ai:songsuwan.nuttanon"Kaemawichanurat, Pawaton"https://zbmath.org/authors/?q=ai:kaemawichanurat.pawatonSummary: Counting the number of maximal independent sets of graphs was started over 50 years ago by Erdős and Mooser. The problem has been continuously studied with a number of variations. Interestingly, when the maximal condition of an independent set is removed, such the concept presents one of topological indices in molecular graphs, the so called Merrifield-Simmons index. In this paper, we applied the concept of bivariate generating function to establish the recurrence relations of the numbers of maximal independent sets of regular \(n\)-gonal cacti when \(3 \leq n \leq 6\). By the ideas on meromorphic functions and the growth of power series coefficients, the asymptotic behaviors through simple functions of these recurrence relations have been established.The equivalence of the Szemerédi and Petruska conjecture and the maximum order of 3-uniform \(\tau\)-critical hypergraphshttps://zbmath.org/1528.050682024-03-13T18:33:02.981707Z"Kézdy, André E."https://zbmath.org/authors/?q=ai:kezdy.andre-e"Lehel, Jenő"https://zbmath.org/authors/?q=ai:lehel.jenoIn this article, the authors establish a correspondence between the maximum number of vertices of 3-uniform \(\tau\)-critical hypergraphs and the Szemerédi-Petruska conjecture [\textit{E. Szemerédi} and \textit{G. Petruska}, Stud. Sci. Math. Hung. 7, 363--374 (1973; Zbl 0302.05002)]. \textit{A. Gyarfas} et al. [J. Comb. Theory, Ser. B 33, 161--165 (1982; Zbl 0498.05050)] had already observed, via a straightforward but unpublished argument, this equivalence. The authors also present open problems, and applications of the Szemerédi-Petruska conjecture to combinatorial geometry.
A hypergraph \(H=(V,E)\) is \(\tau\)-critical if it has no isolated vertices (that is, every vertex belongs to some edge) and \(\tau(H-e)=\tau(H)-1\), where \(H-e\) is the partial hypergraph with vertex set \(V\) and edge set \(E\setminus{e}\). An \(r\)-uniform hypergraph \(H\) on \(n\) vertices is defined to be an \(r\)-uniform \((n,k)\)-witness hypergraph provided its clique number \(\omega(H)=k\) and the \(k\)-cliques of \(H\) have no common vertex. The Szemerédi and Petruska conjecture [loc. cit.] states that, in terms of \(m=n-k\), the maximum number of vertices of a \(3\)-uniform \((n,k)\)-witness hypergraph is \(\binom{m+2}{2}\). Note that in particular, in the case \(r=2\) the order of an \((n, k)\)-witness graph is at most \(2m\) by the Hajnal-Folkmann lemma.
Reviewer: Gaurav Sunil Kucheriya (Praha)