Recent zbMATH articles in MSC 05Bhttps://zbmath.org/atom/cc/05B2022-09-13T20:28:31.338867ZWerkzeugBook review of: L. Lovász, Graphs and geometryhttps://zbmath.org/1491.000162022-09-13T20:28:31.338867Z"Meunier, Frédéric"https://zbmath.org/authors/?q=ai:meunier.fredericReview of [Zbl 1425.05001].Book review of: C. Ding and C. Tang, Designs from linear codeshttps://zbmath.org/1491.000322022-09-13T20:28:31.338867Z"Tonchev, Vladimir D."https://zbmath.org/authors/?q=ai:tonchev.vladimir-dReview of [Zbl 1477.94006].Enumerations of universal cycles for \(k\)-permutationshttps://zbmath.org/1491.050042022-09-13T20:28:31.338867Z"Chang, Zuling"https://zbmath.org/authors/?q=ai:chang.zuling"Xue, Jie"https://zbmath.org/authors/?q=ai:xue.jie.1|xue.jieSummary: Universal cycle for \(k\)-permutations is a cyclic arrangement in which each \(k\)-permutation appears exactly once as \(k\) consecutive elements. Enumeration problem of universal cycles for \(k\)-permutations is discussed and one new enumerating method is proposed in this paper. Accurate enumerating formulae are provided when \(k = 2, 3\).Construction of \(T_m\)-type and \(T_m\)-assisted PBIB designshttps://zbmath.org/1491.050372022-09-13T20:28:31.338867Z"Kaur, Parneet"https://zbmath.org/authors/?q=ai:kaur.parneet"Garg, Davinder Kumar"https://zbmath.org/authors/?q=ai:garg.davinder-kumarSummary: Two-associate class triangular designs have been explored greatly but the \(T_m\)-type PBIB designs \((m\geq 3)\) largely remains unexplored. The paper is written with an objective to construct a new series of \(T_m\)-type PBIB designs and to derive some more series of PBIB designs based on these PBIB designs, which we have called as \(T_m\)-assisted PBIB designs. For this, we begin by first constructing a series of \(T_m\)-type PBIB designs and then based on these designs, three series of \(T_m\)-assisted PBIB designs have been constructed. The association schemes of \(T_m\)-type and \(T_m\)-assisted PBIB designs have been discussed in their complete generalized form.New results on LR-designs and OLKTSshttps://zbmath.org/1491.050382022-09-13T20:28:31.338867Z"Xu, Juanjuan"https://zbmath.org/authors/?q=ai:xu.juanjuan"Ji, Lijun"https://zbmath.org/authors/?q=ai:ji.lijunSummary: LR-designs, introduced by \textit{J.-g. Lei} [ibid. 257, No. 1, 63--81 (2002; Zbl 1007.05026)], play an important role in the recursive constructions of large sets of Kirkman triple systems. In this paper, we mainly present some new infinite families of LR-designs and overlarge sets of Kirkman triple systems.Self-converse large sets of pure directed triple systemshttps://zbmath.org/1491.050392022-09-13T20:28:31.338867Z"Liu, Yuanyuan"https://zbmath.org/authors/?q=ai:liu.yuanyuan.1|liu.yuanyuan.2|liu.yuanyuan.3|liu.yuanyuan"Zhou, Henry"https://zbmath.org/authors/?q=ai:zhou.henry"Sun, Yuefang"https://zbmath.org/authors/?q=ai:sun.yuefang|sun.yuefang.1"Zhao, Hongtao"https://zbmath.org/authors/?q=ai:zhao.hongtaoSummary: An \(L P D T S(v, \lambda)\) is a collection of \(\frac{ 3 ( v - 2 )}{ \lambda}\) pairwise disjoint \(P D T S(v, \lambda) s\) on the same set of \(v\) elements. An \(L P D T S^\ast(v)\) is a special \(L P D T S(v, 1)\) which contains exactly \(\frac{ v - 2}{ 2}\) converse hexads of \(P D T S(v) s\). In this paper, we mainly discuss the existence of an \(L P D T S^\ast(v)\) and get the following conclusions: (1) there exists an \(L P D T S^\ast(v)\) if and only if \(v \equiv 0, 4 \bmod 6\), \(v \geq 4\) except possibly \(v = 30\). (2) There exists an \(L P D T S(v, \lambda)\) with index \(\lambda \equiv 2, 4 \bmod 6\) if and only if \(v \equiv 0, 4 \bmod 6\), \(v \geq 2 \lambda + 2\), \(v \equiv 2 \bmod \lambda\) except possibly \(v = 30\).Ryser's theorem for \(\rho\)-Latin rectangleshttps://zbmath.org/1491.050402022-09-13T20:28:31.338867Z"Bahmanian, Amin"https://zbmath.org/authors/?q=ai:bahmanian.m-aminSummary: Let \(L\) be an \(n \times n\) array whose top left \(r \times s\) subarray is filled with \(k\) different symbols, each occurring at most once in each row and at most once in each column. We find necessary and sufficient conditions that ensure the remaining cells of \(L\) can be filled such that each symbol occurs at most once in each row and at most once in each column, and each symbol occurs a prescribed number of times in \(L\). The case where the prescribed number of times each symbol occurs is \(n\) was solved by \textit{H. J. Ryser} [Proc. Am. Math. Soc. 2, 550--552 (1951; Zbl 0043.01202)], and the case \(s = n\) was settled by \textit{J. L. Goldwasser} et al. [J. Comb. Theory, Ser. A 130, 26--41 (2015; Zbl 1303.05021]. Our technique leads to a very short proof of the latter.Non-zero sum Heffter arrays and their applicationshttps://zbmath.org/1491.050412022-09-13T20:28:31.338867Z"Costa, Simone"https://zbmath.org/authors/?q=ai:costa.simone-a"Della Fiore, Stefano"https://zbmath.org/authors/?q=ai:della-fiore.stefano"Pasotti, Anita"https://zbmath.org/authors/?q=ai:pasotti.anitaSummary: In this paper we introduce a new class of partially filled arrays that, as Heffter arrays, are related to difference families, graph decompositions and biembeddings. A non-zero sum Heffter array \(\operatorname{NH}(m, n; h, k)\) is an \(m \times n\) p.f. array with entries in \(\mathbb{Z}_{2 n k + 1}\) such that: each row contains \(h\) filled cells and each column contains \(k\) filled cells; for every \(x \in \mathbb{Z}_{2 n k + 1} \setminus \{0 \} \), either \(x\) or \(- x\) appears in the array; the sum of the elements in every row and column is different from 0 (in \(\mathbb{Z}_{2 n k + 1} \)). Here first we explain the connections with relative difference families and with path decompositions of the complete multipartite graph. Then we present a complete solution for the existence problem and a constructive complete solution for the square case and for the rectangular case with no empty cells when the additional, very restrictive, property of being ``globally simple'' is required. Finally, we show how these arrays can be used to construct biembeddings of complete graphs.Latin squares with maximal partial transversals of many lengthshttps://zbmath.org/1491.050422022-09-13T20:28:31.338867Z"Evans, Anthony B."https://zbmath.org/authors/?q=ai:evans.anthony-b"Mammoliti, Adam"https://zbmath.org/authors/?q=ai:mammoliti.adam"Wanless, Ian M."https://zbmath.org/authors/?q=ai:wanless.ian-mSummary: A \textit{partial transversal} \(T\) of a Latin square \(L\) is a set of entries of \(L\) in which each row, column and symbol is represented at most once. A partial transversal is \textit{maximal} if it is not contained in a larger partial transversal. Any maximal partial transversal of a Latin square of order \(n\) has size at least \(\lceil \frac{ n}{ 2} \rceil\) and at most \(n\). We say that a Latin square is \textit{omniversal} if it possesses a maximal partial transversal of all plausible sizes and is \textit{near-omniversal} if it possesses a maximal partial transversal of all plausible sizes except one. \textit{A. B. Evans} [Australas. J. Comb. 73, Part 1, 179--199 (2019; Zbl 1411.05039)] showed that omniversal Latin squares of order \(n\) exist for any odd \(n \neq 3\). By extending this result, we show that an omniversal Latin square of order \(n\) exists if and only if \(n \notin \{3, 4 \}\) and \(n \not\equiv 2\,( \operatorname{mod} 4)\). Furthermore, we show that near-omniversal Latin squares exist for all orders \(n \equiv 2\,( \operatorname{mod} 4)\). Finally, we show that no non-trivial finite group has an omniversal Cayley table, and only 15 finite groups have a near-omniversal Cayley table. In fact, as \(n\) grows, Cayley tables of groups of order \(n\) miss a constant fraction of the plausible sizes of maximal partial transversals. In the course of proving this, we partially solve the following interesting problem in combinatorial group theory. Suppose that we have two finite subsets \(R, C \subseteq G\) of a group \(G\) such that \(| \{r c : r \in R, \,c \in C \} | = m\). How large do \(| R |\) and \(| C |\) need to be (in terms of \(m)\) to be certain that \(R \subseteq x H\) and \(C \subseteq H y\) for some subgroup \(H\) of order \(m\) in \(G\), and \(x, y \in G\)?On large set plus of disjoint incomplete Latin squareshttps://zbmath.org/1491.050432022-09-13T20:28:31.338867Z"Shen, Cong"https://zbmath.org/authors/?q=ai:shen.cong"Cao, Haitao"https://zbmath.org/authors/?q=ai:cao.haitao|cao.haitao.1An incomplete Latin square \(L\in\mathrm{ILS}(n;a_1,\ldots, a_k)\) is an \(n\times n\) array whose entries belong to an \(n\)-set \(X\), together with \(k\) pairwise disjoint \(a_i\)-subsets \(A_i\subseteq X\), with \(1\leq i\leq k\), such that: (1) each cell of \(L\) is either empty or contains an element \(L[i,j]\in X\); (2) the subarray indexed by each \(A_i\times A_i\) is empty; and (3) the elements in the \(x^\mathrm{th}\) row or \(x^\mathrm{th}\) column of \(L\) are exactly those of \(X\setminus A_i\), if \(x\in A_i\), or those of \(X\), otherwise. This array is a partitioned incomplete Latin square if \(\sum_{1\leq i\leq k}a_i=n\). In particular, \(\mathrm{PILS}(a_1^{s_1}\ldots a_t^{s_t})\) denotes the set of partitioned incomplete Latin squares with exactly \(s_i\) subsets of size \(a_i\), with \(1\leq i\leq t\). Further, two incomplete Latin squares \(L\) and \(L^\prime\) defined on the same set are disjoint if \(L[i,j]\neq L^\prime[i,j]\), for each non-empty cell \((i,j)\). A large set of disjoint incomplete Latin squares \(\mathrm{LDILS}(n+a;a)\) is a set of \(n\) pairwise disjoint \(\mathrm{ILS}(n+a;a)\) defined on the same set. Similarly, a large set of partitioned incomplete Latin squares \(\mathrm{LSPILS}(g^nu^1)\), with \(g<u\), is a set of \(g\cdot (n-1)\) pairwise disjoint \(\mathrm{PILS}(g^nu^1)\) defined on the same \((gn+u)\)-set.
In this paper, the authors introduce the concept of large set plus of disjoint incomplete Latin squares \(\mathrm{LDILS}^+(n+a;a)\). It is the union of a \(\mathrm{LDILS}(n+a;a)\), which is defined on an \((n+a)\)-set \(X\cup Y\) and an \(a\)-subset \(Y\), and a set of \(a\) Latin squares of order \(n\), which are defined on the set \(X\) and whose entries are formed by the \(a\cdot n^2\) ordered triples in \(X\times X\times X\) that are not entries in any of the previous incomplete Latin squares. It follows similarly to the known concept of large set plus of partitioned incomplete Latin squares \(\mathrm{LSPILS}^+(g^nu^1)\). Then, the authors prove that, for every non-negative integer \(a\leq n\), there exists an \(\mathrm{LDILS}^+(n+a,a)\) if and only if \((n,a)\not\in\left\{(2,1),\,(6,5)\right\}\). In addition, they make use of the existence of \(\mathrm{LDILS}^+\) to prove the existence of \(\mathrm{LSPILS}^+(g^{qn}(gu)^1)\), for all \(g\geq 1\), whenever \(q\) is a prime power with \(q\geq u+1\geq 4\), and \(n=\prod_{1\leq i\leq t} p_i^{e_i}\) is such that \(p_1,\ldots,p_t\) are distinct primes and \(e_1,\ldots,e_t\) are positive integers, with \(p_i^{e_i}\geq 4\), for all \(1\leq i\leq t\).
Reviewer: Raúl M. Falcón (Sevilla)List coloring of two matroids through reduction to partition matroidshttps://zbmath.org/1491.050442022-09-13T20:28:31.338867Z"Bérczi, Kristóf"https://zbmath.org/authors/?q=ai:berczi.kristof"Schwarcz, Tamás"https://zbmath.org/authors/?q=ai:schwarcz.tamas"Yamaguchi, Yutaro"https://zbmath.org/authors/?q=ai:yamaguchi.yutaroAuthors' abstract: In the list coloring problem for two matroids, we are given matroids \(M_1=(S,\mathcal{I}_1)\) and \(M_2=(S,\mathcal{I}_2)\) on the same ground set \(S\), and the goal is to determine the smallest number \(k\) such that, given arbitrary lists \(L_s\) of \(k\) colors for \(s\in S\), it is possible to choose a color from each list so that every monochromatic set is independent in both \(M_1\) and \(M_2\). When both \(M_1\) and \(M_2\) are partition matroids, Galvin's celebrated list coloring theorem for bipartite graphs [\textit{F. Galvin}, J. Comb. Theory, Ser. B 63, No. 1, 153--158 (1995; Zbl 0826.05026)] gives the answer. However, not much is known about the general case. One of the main open questions is to decide if there exists a constant \(c\) such that if the coloring number is \(k\) (i.e., the ground set can be partitioned into \(k\) common independent sets), then the list coloring number is at most \(c\cdot k\). In the present paper, we consider matroid classes that appear naturally in combinatorial and graph optimization problems, specifically graphic matroids, paving matroids and gammoids. We show that if both matroids are from these fundamental classes, then the list coloring number is at most twice the coloring number. The proof is based on a new approach that reduces a matroid to a partition matroid without increasing its coloring number too much and might be of independent combinatorial interest. In particular, we show that if \(M=(S,\mathcal{I})\) is a matroid in which \(S\) can be partitioned into \(k\) independent sets, then there exists a partition matroid \(N=(S,\mathcal{J})\) with \(\mathcal{J}\subseteq\mathcal{I}\) in which \(S\) can be partitioned into (A) \(k\) independent sets if \(M\) is a transversal matroid, (B) \(2k-1\) independent sets if \(M\) is a graphic matroid, (C) \(\lceil kr/(r-1)\rceil\) independent sets if \(M\) is a paving matroid of rank \(r\), and (D) \(2k-2\) independent sets if \(M\) is a gammoid. It should be emphasized that in cases (A), (B), and (D) the rank of \(N\) is the same as that of \(M\). We further extend our results to a much broader family by showing that taking direct sum, homomorphic image, or truncation of matroids from these classes results in a matroid admitting a reduction to a partition matroid with coloring number at most twice the original one.
Reviewer: Jack Koolen (Hefei)Matroids with different configurations and the same \(\mathcal{G} \)-invarianthttps://zbmath.org/1491.050452022-09-13T20:28:31.338867Z"Bonin, Joseph E."https://zbmath.org/authors/?q=ai:bonin.joseph-eSummary: From the configuration of a matroid (which records the size and rank of the cyclic flats and the containments among them, but not the sets), one can compute several much-studied matroid invariants, including the Tutte polynomial and a newer, stronger invariant, the \(\mathcal{G}\)-invariant. To gauge how much additional information the configuration contains compared to these invariants, it is of interest to have methods for constructing matroids with different configurations but the same \(\mathcal{G}\)-invariant. We offer several such constructions along with tools for developing more.The excluded minors for lattice path polymatroidshttps://zbmath.org/1491.050462022-09-13T20:28:31.338867Z"Bonin, Joseph E."https://zbmath.org/authors/?q=ai:bonin.joseph-e"Chun, Carolyn"https://zbmath.org/authors/?q=ai:chun.carolyn"Fife, Tara"https://zbmath.org/authors/?q=ai:fife.taraSummary: We find the excluded minors for the minor-closed class of lattice path polymatroids as a subclass of the minor-closed class of Boolean polymatroids. Like lattice path matroids and Boolean polymatroids, there are infinitely many excluded minors, but they fall into a small number of easily-described types.Matroids of combinatorially formal arrangements are not determined by their points and lineshttps://zbmath.org/1491.050472022-09-13T20:28:31.338867Z"Möller, Tilman"https://zbmath.org/authors/?q=ai:moller.tilmanSummary: An arrangement of hyperplanes is called formal, if the relations between the hyperplanes are generated by relations in codimension 2. Formality is not a combinatorial property, raising the question for a characterization for combinatorial formality. A sufficient condition for this is if the underlying matroid has no proper lift with the same points and lines. We present an example of a matroid with such a lift but no non-formal realization, thus showing that above condition is not necessary for combinatorial formality.On graphic elementary lifts of graphic matroidshttps://zbmath.org/1491.050482022-09-13T20:28:31.338867Z"Mundhe, Ganesh"https://zbmath.org/authors/?q=ai:mundhe.ganesh"Borse, Y. M."https://zbmath.org/authors/?q=ai:borse.y-m"Dalvi, K. V."https://zbmath.org/authors/?q=ai:dalvi.kiran-vishnupantSummary: An elementary lift of a binary matroid \(M\) that arises from a binary coextension of \(M\) can easily be obtained by applying the splitting operation on \(M\). This operation on a graphic matroid may not produce a graphic matroid. We give a method to determine the forbidden minors for the class of graphic matroids \(M\) such that the splitting of \(M\) by any set of \(k\) elements is again a graphic matroid. Using this method, we obtain such minors for \(k = 2, 3, 4\). One may compute such minors for \(k \geq 5\). As a consequence, we obtain the forbidden minors for the class of graphic matroids whose all elementary lifts obtained via binary coextensions are also graphic. There are six such graphic minors.Twist polynomials of delta-matroidshttps://zbmath.org/1491.050492022-09-13T20:28:31.338867Z"Yan, Qi"https://zbmath.org/authors/?q=ai:yan.qi"Jin, Xian'an"https://zbmath.org/authors/?q=ai:jin.xiananSummary: Recently, \textit{J. L. Gross} et al. [Eur. J. Comb. 86, Article ID 103084, 20 p. (2020; Zbl 1437.05060] introduced the partial duality polynomial of a ribbon graph and posed a conjecture that there is no orientable ribbon graph whose partial duality polynomial has only one non-constant term. We found an infinite family of counterexamples for the conjecture and showed that essentially these are the only counterexamples. This is also obtained independently by \textit{S. Chmutov} and \textit{F. Vignes-Tourneret} [Eur. J. Comb. 97, Article ID 103368, 7 p. (2021; Zbl 1469.05083)] and they posed a problem: it would be interesting to know whether the partial duality polynomial and the related conjectures would make sense for general delta-matroids. In this paper, we show that partial duality polynomials have delta-matroid analogues. We introduce the twist polynomials of delta-matroids and discuss its basic properties for delta-matroids. We give a characterization of even normal binary delta-matroids whose twist polynomials have only one term and then prove that the twist polynomial of a normal binary delta-matroid contains non-zero constant term if and only if its intersection graph is bipartite.Maximum parallel classes in 3-packingshttps://zbmath.org/1491.050502022-09-13T20:28:31.338867Z"Wei, Ruizhong"https://zbmath.org/authors/?q=ai:wei.ruizhongSummary: Define \(\beta(\rho, v, k)\) to be the maximum number of blocks in any \((v, k)\)-packing in which the maximum partial parallel classes have size \(\rho \). \textit{D. R. Stinson} [Discrete Math. 344, No. 4, Article ID 112279, 7 p. (2021; Zbl 1462.05046)] discussed \(\beta(\rho, v, 3)\) and gave some explicit constructions of \((v, 3)\)-packing using Room squares and also gave some upper bounds for \(\beta(\rho, v, 3)\). In this note, we give a new upper bound for \(\beta(\rho, v, 3)\) which shows that most 3-packings constructed in [loc. cit.] are optimal, and determines the value of \(\beta(\rho, v, 3)\) when \(v\) is relatively large.Forced perimeter in Elnitksy polygonshttps://zbmath.org/1491.050512022-09-13T20:28:31.338867Z"Tenner, Bridget E."https://zbmath.org/authors/?q=ai:tenner.bridget-eileenSummary: We study tiling-based perimeter and characterize when a given perimeter tile appears in all rhombic
tilings of an Elnitsky polygon. Regardless of where on the perimeter this tile appears, its forcing can be described
in terms of 321-patterns. We characterize the permutations with maximally many forced right-perimeter tiles,
and show that they are enumerated by the Catalan numbers.Switching 3-edge-colorings of cubic graphshttps://zbmath.org/1491.050782022-09-13T20:28:31.338867Z"Goedgebeur, Jan"https://zbmath.org/authors/?q=ai:goedgebeur.jan"Östergård, Patric R. J."https://zbmath.org/authors/?q=ai:ostergard.patric-r-jSummary: The chromatic index of a cubic graph is either 3 or 4. Edge-Kempe switching, which can be used to transform edge-colorings, is here considered for 3-edge-colorings of cubic graphs. Computational results for edge-Kempe switching of cubic graphs up to order 30 and bipartite cubic graphs up to order 36 are tabulated. Families of cubic graphs of orders \(4 n + 2\) and \(4 n + 4\) with \(2^n\) edge-Kempe equivalence classes are presented; it is conjectured that there are no cubic graphs with more edge-Kempe equivalence classes. New families of nonplanar bipartite cubic graphs with exactly one edge-Kempe equivalence class are also obtained. Edge-Kempe switching is further connected to cycle switching of Steiner triple systems, for which an improvement of the established classification algorithm is presented.A Sylvester-Gallai theorem for cubic curveshttps://zbmath.org/1491.140472022-09-13T20:28:31.338867Z"Cohen, Alex"https://zbmath.org/authors/?q=ai:cohen.alex"de Zeeuw, Frank"https://zbmath.org/authors/?q=ai:de-zeeuw.frankThe theorem of Sylvester-Gallai, a classic result of combinatorial geometry, states that for any finite set \(A\) of points in \(\mathbb{R}^2\), not contained in a line, there exists a straight line that intersects \(A\) in exactly two points. It is conjectured that for any finite point set \(A \subset \mathbb{R}^2\) that is not contained in an algebraic curve of degree \(d\) there exist a -- not necessarily irreducible -- algebraic curve of degree \(d\) that intersects \(\mathbb{P}\) in precisely \(d(d+3)/2\) points (the number of points that typically determine a curve of degree \(d\)).
This conjecture was shown to be true for \(d = 2\) by \textit{J. A. Wiseman} and \textit{P. R. Wilson} in [Discrete Comput. Geom. 3, No. 4, 295--305 (1988; Zbl 0643.51009)]. Since then, several other proofs for the case \(d = 2\) have appeared. This article adds a new proof that allows for a generalization to cubic curves and sufficiently large point sets. While details of their proof are a bit involved and complicated, the basic idea is straightforward and elegant: In the projective space of cubic curves a plane is determined by requiring the cubics to pass through seven suitably chosen points. The dual version of the original Sylvester-Gallai theorem then guarantees existence of a point in that space that leads to a solution cubic.
The authors write quite openly about the caveats of their approach and also explain reasons for some of its weak points:
\begin{itemize}
\item The point set \(A\) is required to have a cardinality of at least \(250\). This number is certainly not optimal and could be reduced. However, by using only ideas from this article, it seems impossible to get entirely rid of a restriction on the cardinality of \(A\).
\item Unlike the line and conic versions of the Sylvester-Gallai theorem, the authors cannot guarantee that the nine points determine a \emph{unique} cubic.
\item Generalization to higher degrees seem difficult. The authors outline a possible approach based on Sylvester-Gallai theorems for points and hyperplanes in higher dimensions. However, nothing seems to be known in that regard and it is entirely possible that these theorems fail to be true.
\end{itemize}
Reviewer: Hans-Peter Schröcker (Innsbruck)A method to construct all the paving matroids over a finite sethttps://zbmath.org/1491.180052022-09-13T20:28:31.338867Z"Mederos, B."https://zbmath.org/authors/?q=ai:mederos.boris"Pérez-Cabrera, I."https://zbmath.org/authors/?q=ai:perez-cabrera.i"Takane, M."https://zbmath.org/authors/?q=ai:takane.martha"Tapia Sánchez, G."https://zbmath.org/authors/?q=ai:tapia-sanchez.gustavo"Zavala, B."https://zbmath.org/authors/?q=ai:zavala.bertaPaving matroids were defined in [\textit{J. Hartmanis}, Can. J. Math. 11, 97--106 (1959; Zbl 0089.37002)] through the concept of \(d\)-partitions in number theory. Paving matroids play a significant role in computer science via greedy algorithms and the matroid oracles [\textit{C. Heunen} and \textit{V. Patta}, Appl. Categ. Struct. 26, No. 2, 205--237 (2018; Zbl 1403.18002)]. This paper aims to give a characterization of paving matroids leading to a concrete construction of their hyperplances and to an algorithm for finding them. A counterexample to a characterization of paving matroids by \textit{J. G. Oxley} [Matroid theory. 2nd ed. Oxford: Oxford University Press (2011; Zbl 1254.05002), 1.3.10] is given. A simple proof of Rota's basis conjecture [\textit{G.-C. Rota}, Mitt. Dtsch. Math.-Ver. 6, No. 2, 45--52 (1998; Zbl 1288.00005)] is given for the case of sparse-paving matroids and for the case of paving matroids of rank \(r\) on a set of cardinality \(n\leq2r\).
Reviewer: Hirokazu Nishimura (Tsukuba)Constructions of polynomially complete quasigroups of arbitrary orderhttps://zbmath.org/1491.201482022-09-13T20:28:31.338867Z"Artamonov, V. A."https://zbmath.org/authors/?q=ai:artamonov.vyacheslavovich-aleksandrovich|artamonov.vyacheslav-a"Chakrabarti, S."https://zbmath.org/authors/?q=ai:chakrabarti.subhadip|chakrabarti.sucharita|chakrabarti.sayak|chakrabarti.subhroneel|chakrabarti.soumen|chakrabarti.sukanya|chakrabarti.sayan-k|chakrabarti.satyabrata|chakrabarti.subrata-k|chakrabarti.sanjib-kumar|chakrabarti.subir-k|chakrabarti.sandip-k|chakrabarti.sadasiv|chakrabarti.saikat|chakrabarti.sulagna|chakrabarti.saswat|chakrabarti.sucheta|chakrabarti.soumya|chakrabarti.satish-chandra"Markov, V. T."https://zbmath.org/authors/?q=ai:markov.viktor-timofeevich"Pal, S. K."https://zbmath.org/authors/?q=ai:pal.swapan-kr|pal.surjya-k|pal.sayan-kumar|pal.surya-kant|pal.saibal-kumar|pal.sandip-kumar|pal.sudipta-kumar|pal.shiv-kumar|pal.sudip-kumar|pal.sankar-kr|pal.sankar-kumarThe generating and embedding ranks of hyperplanes of Grassmannianshttps://zbmath.org/1491.510052022-09-13T20:28:31.338867Z"De Bruyn, Bart"https://zbmath.org/authors/?q=ai:de-bruyn.bartSummary: Let \(H\) be a hyperplane of the Grassmannian of the \(k\)-dimensional subspaces of the projective space \(\mathrm{PG}(n,\mathbb{F}), 0 \leq k \leq n-1\), and let \(\widetilde{H}\) denote the subgeometry of the Grassmannian induced on the point set \(H\). We prove that the embedding and generating ranks of \(\widetilde{H}\) are always equal to \(\left(\begin{smallmatrix} n+1 \\ k+1 \end{smallmatrix}\right) -1\).Subspace code constructionshttps://zbmath.org/1491.510072022-09-13T20:28:31.338867Z"Cossidente, Antonio"https://zbmath.org/authors/?q=ai:cossidente.antonio"Marino, Giuseppe"https://zbmath.org/authors/?q=ai:marino.giuseppe.1"Pavese, Francesco"https://zbmath.org/authors/?q=ai:pavese.francescoSummary: We improve on the lower bound of the maximum number of planes of \(\mathrm{PG}(8,q)\) mutually intersecting in at most one point leading to the following lower bound: \(\mathcal{A}_q (9, 4; 3) \geq q^{12}+2q^8 +2q^7 +q^6 +q^5 +q^4 +1\). We also construct two new non-equivalent \((6, (q^3 -1)(q^2 +q+1), 4; 3)_q\)-constant dimension subspace orbit-codes.Twisted cubic and plane-line incidence matrix in \(\mathrm{PG}(3,q)\)https://zbmath.org/1491.510082022-09-13T20:28:31.338867Z"Davydov, Alexander A."https://zbmath.org/authors/?q=ai:davydov.alexander-a"Marcugini, Stefano"https://zbmath.org/authors/?q=ai:marcugini.stefano"Pambianco, Fernanda"https://zbmath.org/authors/?q=ai:pambianco.fernandaSummary: The point-plane, the point-line, and the plane-line incidence matrices of \(\mathrm{PG}(3,q)\) are of interest in combinatorics, finite geometry, graph theory and group theory. Some of the properties of these matrices and their submatrices are related with the interplay of orbits of points, lines and planes under the action of subgroups of \(\mathrm{PGL}(4,q)\). A remarkable particular case is the subgroup \(G\cong \mathrm{PGL}(2,q)\), viewed as the stabilizer group of the twisted cubic \(\mathscr{C}\). For this case, the study of the point-plane incidence matrix, initiated by D. Bartoli and the present authors, has attracted attention as being related to submatrices with useful applications in coding theory for the construction of multiple covering codes. In this paper, we extend our investigation to the plane-line incidence matrix apart from just one class of the line orbits, named \(\mathcal{O}_6\) in the literature. For all \(q\geq 2\), in each submatrix, the numbers of lines in any plane and planes through any line are obtained. As a tool for the present investigation, we use submatrices of incidences arising from orbits of planes and unions of line orbits, including \(\mathcal{O}_6\). For each such submatrix we determine the total number of lines from the union in any plane and the average number of planes from the orbit through any line of the union.A note on the minimum number of red lines needed to pierce the intersections of blue lineshttps://zbmath.org/1491.520142022-09-13T20:28:31.338867Z"Huicochea, Mario"https://zbmath.org/authors/?q=ai:huicochea.mario"Leaños, Jesús"https://zbmath.org/authors/?q=ai:leanos.jesus"Rivera, Luis Manuel"https://zbmath.org/authors/?q=ai:rivera.luis-manuel\textit{P. Erdős} and \textit{G. Purdy} [J. Comb. Theory, Ser. A 25, 205--210 (1978; Zbl 0422.05023)] suggested the following problem:
Problem: Let \(\mathcal{L}\) be a set of \(n\) non-concurrent blue lines and let \(\mathcal{R}\) be a set of \(m\) red lines in the real projective plane. If \(\mathcal{L} \cap \mathcal{R} = \emptyset\) and there is a line from \(\mathcal{R}\) through every intersection point of lines in \(\mathcal{L}\), how big is \(m\) in terms of \(n\)?
Before the current work, the best known bound for this problem was \(m \geq \frac{1}{3}(n- 1)\) obtained by \textit{R. Pinchasi} [Isr. J. Math. 198, 205--214 (2013; Zbl 1278.52010)]. Using mainly elementary geometric arguments, the authors improve the former result of R. Pinchasi by proving that: \[m \geq \frac{4}{11}\left( n - \frac{13}{11}\right).\]
Reviewer: Benoît Guerville-Ballé (Fukuoka)Parallel packing squares into a trianglehttps://zbmath.org/1491.520152022-09-13T20:28:31.338867Z"Januszewski, Janusz"https://zbmath.org/authors/?q=ai:januszewski.janusz"Liu, Xi"https://zbmath.org/authors/?q=ai:liu.xi"Su, Zhanjun"https://zbmath.org/authors/?q=ai:su.zhanjun"Zielonka, Łukasz"https://zbmath.org/authors/?q=ai:zielonka.lukaszThis is a paper about (parallel) packing squares into triangles. For a planar polygon \(P\) with a distinguished side (called base) denote by \(\varrho(P)\) the greatest real number \(r\) such that any collection of squares whose total area does not exceed \(r \cdot |P|\) can be packed into \(P\) in a way such that all these squares have pairwise disjoint interiors and one of the sides of each of them is parallel to the base of \(P\).\par The main result of the paper gives a simple formula for \(\varrho(T_h)\) (as a function of \(h\)) for a triangle \(T_h\) with base of length \(1\), height \(h\) and interior angles at the base of measure not exceeding \(90^o\). This covers certain already known partial results on parallel packing squares into triangles.\par The authors present also some ideas on packing squares into trapezoids.
Reviewer: Piotr Niemiec (Kraków)Constructions for regular-graph semi-Latin rectangles with block size twohttps://zbmath.org/1491.620782022-09-13T20:28:31.338867Z"Uto, N. P."https://zbmath.org/authors/?q=ai:uto.n-p"Bailey, R. A."https://zbmath.org/authors/?q=ai:bailey.rosemary-aSummary: Semi-Latin rectangles are generalizations of Latin squares and semi-Latin squares. Although they are called rectangles, the number of rows and the number of columns are not necessarily distinct. There are \(k\) treatments in each cell (row-column intersection): these constitute a block. Each treatment of the design appears a definite number of times in each row and also a definite number of times in each column (these parameters also being not necessarily distinct). When \(k=2\), the design is said to have block size two. Regular-graph semi-Latin rectangles have the additional property that the treatment concurrences between any two pairs of distinct treatments differ by at most one. Constructions for semi-Latin rectangles of this class with \(k=2\) which have \(v\) treatments, \(v/2\) rows and \(v\) columns, where \(v\) is even, are given in
[the second author and \textit{H. Monod}, Scand. J. Stat. 28, No. 2, 257--270 (2001; Zbl 0973.62061)]. These give the smallest designs when \(v\) is even. Here we give constructions for smallest designs with \(k=2\) when \(v\) is odd. These are regular-graph semi-Latin rectangles where the numbers of rows, columns and treatments are identical. Then we extend the smallest designs in each case to obtain larger designs.Representative sets and irrelevant vertices: new tools for kernelizationhttps://zbmath.org/1491.680922022-09-13T20:28:31.338867Z"Kratsch, Stefan"https://zbmath.org/authors/?q=ai:kratsch.stefan"Wahlström, Magnus"https://zbmath.org/authors/?q=ai:wahlstrom.magnusPower sum polynomials in a discrete tomography perspectivehttps://zbmath.org/1491.920822022-09-13T20:28:31.338867Z"Pagani, Silvia M. C."https://zbmath.org/authors/?q=ai:pagani.silvia-m-c"Pianta, Silvia"https://zbmath.org/authors/?q=ai:pianta.silviaSummary: For a point of the projective space \(\operatorname{PG}(n,q)\), its Rédei factor is the linear polynomial in \(n+1\) variables, whose coefficients are the point coordinates. The power sum polynomial of a subset \(S\) of \(\operatorname{PG}(n,q)\) is the sum of the \((q-1)\)-th powers of the Rédei factors of the points of \(S\). The fact that many subsets may share the same power sum polynomial offers a natural connection to discrete tomography. In this paper we deal with the two-dimensional case and show that the notion of ghost, whose employment enables to find all solutions of the tomographic problem, can be rephrased in the finite geometry context, where subsets with null power sum polynomial are called ghosts as well. In the latter case, one can add ghosts still preserving the power sum polynomial by means of the multiset sum (modulo the field characteristic). We prove some general results on ghosts in \(\operatorname{PG}(2,q)\) and compute their number in case \(q\) is a prime.
For the entire collection see [Zbl 1476.68014].A note on balanced incomplete block designs and projective geometryhttps://zbmath.org/1491.970362022-09-13T20:28:31.338867Z"Deveci, Ömür"https://zbmath.org/authors/?q=ai:deveci.omur"Shannon, Anthony G."https://zbmath.org/authors/?q=ai:shannon.anthony-grevilleSummary: This note outlines some connections between projective geometry and some designs used in clinical trials in the health sciences. The connections are not immediately obvious but they widen the scope for enrichment work at both the senior high school level and for capstone subjects at the undergraduate level.Behavior of powers of odd ordered special circulant magic squareshttps://zbmath.org/1491.970372022-09-13T20:28:31.338867Z"Rani, Narbda"https://zbmath.org/authors/?q=ai:rani.narbda"Mishra, Vinod"https://zbmath.org/authors/?q=ai:mishra.vinod-kumar(no abstract)