Recent zbMATH articles in MSC 06Ahttps://zbmath.org/atom/cc/06A2021-05-28T16:06:00+00:00WerkzeugEdge-matching graph contractions and their interlacing properties.https://zbmath.org/1459.051782021-05-28T16:06:00+00:00"Leiter, Noam"https://zbmath.org/authors/?q=ai:leiter.noam"Zelazo, Daniel"https://zbmath.org/authors/?q=ai:zelazo.danielSummary: For a given graph \(\mathcal{G}\) of order \(n\) with \(m\) edges, and a real symmetric matrix associated to the graph, \(M(\mathcal{G})\in\mathbb{R}^{n\times n}\), the interlacing graph reduction problem is to find a graph \(\mathcal{G}_r\) of order \(r<n\) such that the eigenvalues of \(M(\mathcal{G}_r)\) interlace the eigenvalues of \(M(\mathcal{G})\). Graph contractions over partitions of the vertices are widely used as a combinatorial graph reduction tool. In this study, we derive a graph reduction interlacing theorem based on subspace mappings and the minmax theory. We then define a class of edge-matching graph contractions and show how two types of edge-matching contractions provide Laplacian and normalized Laplacian interlacing. An \(\mathcal{O}(mn)\) algorithm is provided for finding a normalized Laplacian interlacing contraction and an \(\mathcal{O}(n^2+nm)\) algorithm is provided for finding a Laplacian interlacing contraction.Proof of Stahl's conjecture in some new cases.https://zbmath.org/1459.050902021-05-28T16:06:00+00:00"Osztényi, József"https://zbmath.org/authors/?q=ai:osztenyi.jozsefGiven positive integers \(s\) and \(t\), an \(s\)-tuple coloring of a graph \(G\) with \(t\) colors is an assignment of \(s\) distinct colors to each vertex of \(G\) such that no two adjacent vertices share a color. The smallest integer \(t\) for which \(G\) has an \(s\)-tuple coloring with \(t\) colors is called the \(s\)th-multichromatic number of \(G\) and denoted by \(\chi_{s}(G)\). For positive integers \(m\), \(n\) with \(m \geq 2n\), the Kneser graph \(KG_{m,n}\) has as vertices all \(n\)-subsets of \(\{1, \ldots, m\}\), two vertices being connected by an edge if the corresponding subsets are disjoint. \textit{S. Stahl} [J. Comb. Theory, Ser. B 20, 185--203 (1976; Zbl 0293.05115)] formulated the conjecture that for all \(2n \le m\) and \(q\), \(0 \le r < n\), \(\chi_{nq-r}(KG_{m,n})=mq-2r\). \textit{L. Lovász} [J. Comb. Theory, Ser. A 25, 319--324 (1978; Zbl 0418.05028)] has proved the conjecture for \(nq-r=1\). Stahl [loc. cit.] showed it for \(r=0\) and also that \(\chi_{s+1} \geq \chi_{s}+2\) for any positive integer \(s\), which proved the conjecture for \(1 < s \le n\). \textit{S. Stahl} [loc. cit.; Discrete Math. 185, No. 1--3, 287--291 (1998; Zbl 0956.05045)] also settled the cases \(n=2,3\) and \(m=2n+1\), and \textit{J. Kincses} et al. [Eur. J. Comb. 34, No. 2, 502--511 (2013; Zbl 1254.05116)] the case \(m=10\) and \(n=4\). Finally, the conjecture is known to hold for \(s=qn\). In this paper, a new lower bound on the multichromatic number of Kneser graphs \(KG_{m,n}\) is presented and shown to be sharp for graph parameters \(2n < m < 3n\) and cases \(qn - \frac{n}{m-2n} < s < qn\) hereby confirming Stahl's conjecture [loc. cit.] for these new cases.
Reviewer: Reinhardt Euler (Brest)Introducing Boolean semilattices.https://zbmath.org/1459.030972021-05-28T16:06:00+00:00"Bergman, Clifford"https://zbmath.org/authors/?q=ai:bergman.cliffordSummary: We present and discuss a variety of Boolean algebras with operators that is closely related to the variety generated by all complex algebras of semilattices. We consider the problem of finding a generating set for the variety, representation questions, and axiomatizability. Several interesting subvarieties are presented. We contrast our results with those obtained for a number of other varieties generated by complex algebras of groupoids.
For the entire collection see [Zbl 1390.03005].Ordered set partitions, Garsia-Procesi modules, and rank varieties.https://zbmath.org/1459.053402021-05-28T16:06:00+00:00"Griffin, Sean T."https://zbmath.org/authors/?q=ai:griffin.sean-tSummary: We introduce a family of ideals \(I_{n,\lambda , s}\) in \(\mathbb{Q}[x_1,\dots , x_n]\) for \(\lambda\) a partition of \(k\leq n\) and an integer \(s \geq \ell (\lambda )\). This family contains both the Tanisaki ideals \(I_\lambda\) and the ideals \(I_{n,k}\) of \textit{J. Haglund} et al. [Adv. Math. 329, 851--915 (2018; Zbl 1384.05043)] as special cases. We study the corresponding quotient rings \(R_{n,\lambda , s}\) as symmetric group modules. When \(n=k\) and \(s\) is arbitrary, we recover the Garsia-Procesi modules, and when \(\lambda =(1^k)\) and \(s=k\), we recover the generalized coinvariant algebras of Haglund-Rhoades-Shimozono [loc. cit.]. We give a monomial basis for \(R_{n,\lambda , s}\) in terms of \((n,\lambda , s)\)-staircases, unifying the monomial bases studied by \textit{A. M. Garsia} and \textit{C. Procesi} [ibid. 94, No. 1, 82--138 (1992; Zbl 0797.20012)] and Haglund-Rhoades-Shimozono [loc. cit.]. We realize the \(S_n\)-module structure of \(R_{n,\lambda , s}\) in terms of an action on \((n,\lambda , s)\)-ordered set partitions. We find a formula for the Hilbert series of \(R_{n,\lambda , s}\) in terms of inversion and diagonal inversion statistics on a set of fillings in bijection with \((n,\lambda , s)\)-ordered set partitions. Furthermore, we prove an expansion of the graded Frobenius characteristic of our rings into Gessel's fundamental quasisymmetric basis. We connect our work with Eisenbud-Saltman rank varieties using results of \textit{J. Weyman} [Invent. Math. 98, No. 2, 229--245 (1989; Zbl 0717.20033)]. As an application of our results on \(R_{n,\lambda , s}\), we give a monomial basis, Hilbert series formula, and graded Frobenius characteristic formula for the coordinate ring of the scheme-theoretic intersection of a rank variety with diagonal matrices.Posets with series parallel orders and strict-double-bound graphs.https://zbmath.org/1459.052192021-05-28T16:06:00+00:00"Tashiro, Shin-ichiro"https://zbmath.org/authors/?q=ai:tashiro.shin-ichiro"Ogawa, Kenjiro"https://zbmath.org/authors/?q=ai:ogawa.kenjiro"Tsuchiya, Morimasa"https://zbmath.org/authors/?q=ai:tsuchiya.morimasaSummary: For a poset \(P= (X,\le_P)\), the strict-double-bound graph of \(P\) is the graph sDB\((P)\) on \(V(\text{sDB}(P))= X\) for which vertices \(u\) and \(v\) of sDB\((P)\) are adjacent if and only if \(u\ne v\) and there exist elements \(x\in X\) distinct from \(u\) and \(v\) such that \(x \le_P u\le_P y\) and \(x\le_P v\le_P y\). A poset \(P\) is a series parallel order if and only if it contains no induced subposet isomorphic to \(N\)-poset.
In this paper, we deal with strict-double-bound graphs of series parallel orders. In particular, we show that if \(P_3\) is contained as an induced subgraph in a strict-double-bound graph of a series parallel order, it is contained in either of \(C_4\), 3-pan, \(K_{1,3}\) or \(K_4-e\). As a consequence of this result, we can claim that a strict-double graph of a series parallel order is \(P_4\)-free. Furthermore, we study sufficient conditions for a strict-double-bound graph of a series parallel order to be an interval graph, difference graph or Meyniel graph.The fractional weak discrepancy of \((M, 2)\)-free posets.https://zbmath.org/1459.060022021-05-28T16:06:00+00:00"Choi, Jeong-Ok"https://zbmath.org/authors/?q=ai:choi.jeong-okSummary: For a finite poset \(P = (X, \preceq)\) the \textit{fractional weak discrepancy} of \(P\), denoted \(\operatorname{wd}_F(P)\), is the minimum value \(t\) for which there is a function \(f: X \longrightarrow \mathbb{R}\) satisfying (1) \(f(x) + 1 \le f(y)\) whenever \(x \prec y\) and (2) \(|f(x) - f(y)| \le t\) whenever \(x \| y\). In this paper, we determine the range of the fractional weak discrepancy of \((M, 2)\)-free posets for \(M \ge 5\), which is a problem asked in [\textit{A. Shuchat} et al., Discrete Appl. Math. 159, No. 7, 647--660 (2011; Zbl 1256.06002)]. More precisely, we showed that (1) the range of the fractional weak discrepancy of \((M, 2)\)-free interval orders is \(W = \{ \frac{r}{r+1} : r \in \mathbb{N} \cup \{ 0 \} \} \cup \{ t \in \mathbb{Q} : 1 \le t < M - 3 \}\) and (2) the range of the fractional weak discrepancy of \((M, 2)\)-free non-interval orders is \(\{ t \in \mathbb{Q} : 1 \le t < M - 3 \}\). The result is a generalization of a well-known result for semiorders and the main result for split semiorders of [loc. cit.] since the family of semiorders is the family of \((4, 2)\)-free posets.Vaught's conjecture for monomorphic theories.https://zbmath.org/1459.030392021-05-28T16:06:00+00:00"Kurilić, Miloš S."https://zbmath.org/authors/?q=ai:kurilic.milos-sSummary: A complete first order theory of a relational signature is called monomorphic iff all its models are monomorphic (i.e. have all the \(n\)-element substructures isomorphic, for each positive integer \(n\)). We show that a complete theory \(\mathcal{T}\) having infinite models is monomorphic iff it has a countable monomorphic model and confirm the Vaught conjecture for monomorphic theories. More precisely, we prove that if \(\mathcal{T}\) is a complete monomorphic theory having infinite models, then the number of its non-isomorphic countable models, \(I(\mathcal{T}, \omega)\), is either equal to 1 or to \(\mathfrak{c}\). In addition, the equality \(I(\mathcal{T}, \omega) = 1\) holds iff some countable model of \(\mathcal{T}\) is simply definable by (or, equivalently, freely interpretable in) an \(\omega\)-categorical linear order on its domain.Rényi ordering of tournaments.https://zbmath.org/1459.051002021-05-28T16:06:00+00:00"Brown, David E."https://zbmath.org/authors/?q=ai:brown.david-e"Frederickson, Bryce"https://zbmath.org/authors/?q=ai:frederickson.bryceSummary: We develop an ordering function on the class of tournament digraphs (complete antisymmetric digraphs) that is based on the Rényi \(\alpha\)-entropy. This ordering function partitions tournaments on \(n\) vertices into equivalence classes that are approximately sorted from transitive (the arc relation is transitive -- the score sequence is \((0,1,2,\dots,n-1))\) to regular (score sequence \((\frac{n-1}{2}, \dots,\frac{n-1}{2}))\). But the diversity among regular tournaments (there are for example 1123 regular tournaments on 11 vertices, and 1,495,297 regular tournaments on 13 vertices up to isomorphism) is captured to an extent.Sign-restricted matrices of 0's, 1's, and \(-1\)'s.https://zbmath.org/1459.050132021-05-28T16:06:00+00:00"Brualdi, Richard A."https://zbmath.org/authors/?q=ai:brualdi.richard-a"Dahl, Geir"https://zbmath.org/authors/?q=ai:dahl.geirSummary: We study sign-restricted matrices (SRMs), a class of rectangular \((0, \pm 1)\)-matrices generalizing the alternating sign matrices (ASMs). In an SRM each partial column sum, starting from row 1, equals 0 or 1, and each partial row sum, starting from column 1, is nonnegative. We determine the maximum number of nonzeros in SRMs and characterize the possible row and column sum vectors. Moreover, a number of results on interchange operations are shown, both for SRMs and, more generally, for \((0, \pm 1)\)-matrices. The Bruhat order on ASMs can be extended to SRMs with the result a distributive lattice. Also, we study polytopes associated with SRMs and some relates decompositions.A note on effective categoricity for linear orderings.https://zbmath.org/1459.030452021-05-28T16:06:00+00:00"Bazhenov, Nikolay"https://zbmath.org/authors/?q=ai:bazhenov.n-aSummary: We study effective categoricity for linear orderings. For a computable structure \(\mathcal {S}\), the degree of categoricity of \(\mathcal {S}\) is the least Turing degree which is capable of computing isomorphisms among arbitrary computable copies of \(\mathcal {S}\).{
}We build new examples of degrees of categoricity for linear orderings. We show that for an infinite computable ordinal \(\alpha\), every Turing degree c.e. in and above \(\mathbf {0}^{(2\alpha + 2)}\) is the degree of categoricity for some linear ordering. We obtain similar results for linearly ordered abelian groups and decidable linear orderings.
For the entire collection see [Zbl 1360.68012].