Recent zbMATH articles in MSC 05Bhttps://zbmath.org/atom/cc/05B2021-04-16T16:22:00+00:00WerkzeugExpected dispersion of uniformly distributed points.https://zbmath.org/1456.600422021-04-16T16:22:00+00:00"Hinrichs, Aicke"https://zbmath.org/authors/?q=ai:hinrichs.aicke"Krieg, David"https://zbmath.org/authors/?q=ai:krieg.david"Kunsch, Robert J."https://zbmath.org/authors/?q=ai:kunsch.robert-j"Rudolf, Daniel"https://zbmath.org/authors/?q=ai:rudolf.danielSummary: The dispersion of a point set in \([0,1]^d\) is the volume of the largest axis parallel box inside the unit cube that does not intersect the point set. We study the expected dispersion with respect to a random set of \(n\) points determined by an i.i.d. sequence of uniformly distributed random variables. Depending on the number of points \(n\) and the dimension \(d\) we provide an upper and a lower bound of the expected dispersion. In particular, we show that the minimal number of points required to achieve an expected dispersion less than \(\varepsilon\in(0,1)\) depends linearly on the dimension \(d\).Alternating sign hypermatrix decompositions of Latin-like squares.https://zbmath.org/1456.050262021-04-16T16:22:00+00:00"O'Brien, Cian"https://zbmath.org/authors/?q=ai:obrien.cianSummary: To any \(n\times n\) Latin square \(L\), we may associate a unique sequence of mutually orthogonal permutation matrices \(P=P_1,P_2,\dots,P_n\) such that \(L=L(P)=\sum kP_k\). \textit{R. A. Brualdi} and \textit{G. Dahl} [ibid. 95, 116--151 (2018; Zbl 1379.05020)] described a generalisation of a Latin square, called an alternating sign hypermatrix Latin-like square (ASHL), by replacing \(P\) with an alternating sign hypermatrix (ASHM). An ASHM is an \(n\times n\times n\) \((0,1,-1)\)-hypermatrix in which the non-zero elements in each row, column, and vertical line alternate in sign, beginning and ending with 1. Since every sequence of \(n\) mutually orthogonal permutation matrices forms the planes of a unique \(n\times n\times n\) ASHM, this generalisation of Latin squares follows very naturally, with an ASHM \(A\) having corresponding ASHL \(L=L(A)=\sum k A_k\), where \(A_k\) is the \(k\)th plane of \(A\). This paper addresses open problems posed in Brualdi and Dahl's article, firstly by characterising how pairs of ASHMs with the same corresponding ASHL relate to one another and identifying the smallest dimension for which this can happen, and secondly by exploring the maximum number of times a particular integer may occur as an entry of an \(n\times n\) ASHL. A construction is given for an \(n\times n\) ASHL with the same entry occurring \(\lfloor\frac{n^2+4n-19}{2} \rfloor\) times, improving on the previous best of \(2n\).Striking patterns in natural magic squares' associated electrostatic potentials: matrices of the 4th and 5th order.https://zbmath.org/1456.050252021-04-16T16:22:00+00:00"Fahimi, Peyman"https://zbmath.org/authors/?q=ai:fahimi.peyman"Toussi, Cyrus Ahmadi"https://zbmath.org/authors/?q=ai:toussi.cyrus-ahmadi"Trump, Walter"https://zbmath.org/authors/?q=ai:trump.walter"Haddadnia, Javad"https://zbmath.org/authors/?q=ai:haddadnia.javad"Matta, Chérif F."https://zbmath.org/authors/?q=ai:matta.cherif-fSummary: A magic square is a square matrix whereby the sum of any row, column, or any one of the two principal diagonals is equal. A surrogate of this abstract mathematical construct, introduced in [\textit{P. Fahimi} and \textit{B. Jaleh}, ``The electrostatic potential at the center of associative magic squares'', Int. J. Phys. Sci. 7, 24--30 (2012; \url{doi:10.5897/IJPS11.1387})] is the ``electrostatic potential (ESP)'' that results from treating the matrix elements of the magic square as electric charges. The overarching idea is to characterize patterns associated with these matrices that can possibly be used, in the future, in reverse to generate these squares. This study focuses on squares of order 4 and 5 with 880 and 275, 305, 224 distinct (irreducible/unique) realizations, respectively. It is shown that characteristic patterns emerge from plots of the ESPs of the matrices representing the studied squares. The electrostatic potentials for natural magic squares exhibit a striking pattern of maxima and minima in all distinct 880 of the 4th order and all distinct 275, 305, 224 of the 5th order matrices. The minimum values of ESP of Dudeney groups are discussed. Equipotential points and certain constants are found among the ESP sums along horizontal and vertical lines on the square lattice. These findings may help to open a new perspective regarding magic squares unsolved problems. While mathematics often leads discovery in physics, the latter (physics) is used here to detect otherwise invisible patterns in a mathematical object such as magic squares.On the subsemigroup complex of an aperiodic Brandt semigroup.https://zbmath.org/1456.200622021-04-16T16:22:00+00:00"Margolis, Stuart"https://zbmath.org/authors/?q=ai:margolis.stuart-w"Rhodes, John"https://zbmath.org/authors/?q=ai:rhodes.john-l"Silva, Pedro V."https://zbmath.org/authors/?q=ai:silva.pedro-vSummary: We introduce the subsemigroup complex of a finite semigroup \(S\) as a (boolean representable) simplicial complex defined through chains in the lattice of subsemigroups of \(S\). We present a research program for such complexes, illustrated through the particular case of combinatorial Brandt semigroups. The results include alternative characterizations of faces and facets, asymptotical estimates on the number of facets, or establishing when the complex is pure or a matroid.Upper energy bounds for spherical designs of relatively small cardinalities.https://zbmath.org/1456.050272021-04-16T16:22:00+00:00"Boyvalenkov, Peter"https://zbmath.org/authors/?q=ai:boyvalenkov.peter-g"Delchev, Konstantin"https://zbmath.org/authors/?q=ai:delchev.konstantin"Jourdain, Matthieu"https://zbmath.org/authors/?q=ai:jourdain.matthieuSummary: We derive upper bounds for the potential energy of spherical designs of cardinality close to the Delsarte-Goethals-Seidel bound. These bounds are obtained by linear programming with use of the Hermite interpolating polynomial of the potential function in suitable nodes. Numerical computations show that the results are quite close to certain lower energy bounds confirming that spherical designs are, in a sense, energy efficient.A Poncelet criterion for special pairs of conics in \(\mathrm{PG}(2,p^m)\).https://zbmath.org/1456.510052021-04-16T16:22:00+00:00"Hungerbühler, Norbert"https://zbmath.org/authors/?q=ai:hungerbuhler.norbert"Kusejko, Katharina"https://zbmath.org/authors/?q=ai:kusejko.katharinaSummary: We study Poncelet's Theorem in finite projective planes over the field \(\mathrm{GF}(q), q = p^m\) for \(p\) an odd prime and \(m > 0\), for a particular pencil of conics. We investigate whether we can find polygons with \(n\) sides which are inscribed in one conic and circumscribed around the other, so-called Poncelet Polygons. By using suitable elements of the dihedral group for these pairs, we prove that the length \(n\) of such Poncelet Polygons is independent of the starting point. In this sense Poncelet's Theorem is valid. By using Euler's divisor sum formula for the totient function, we can make a statement about the number of different conic pairs, which carry Poncelet Polygons of length \(n\). Moreover, we will introduce polynomials whose zeros in \(\mathrm{GF}(q)\) yield information about the relation of a given pair of conics. In particular, we can decide for a given integer \(n\), whether and how we can find Poncelet \(n\)-gons for pairs of conics in the plane \(\mathrm{PG}(2,q)\).A decidability result for the halting of cellular automata on the pentagrid.https://zbmath.org/1456.681052021-04-16T16:22:00+00:00"Margenstern, Maurice"https://zbmath.org/authors/?q=ai:margenstern.mauriceSummary: In this paper, we investigate the halting problem for deterministic cellular automata on the pentagrid. We prove that the problem is decidable when the cellular automaton starts its computation from a finite configuration and when it has two states, one of them being a quiescent state.Rank functions.https://zbmath.org/1456.150012021-04-16T16:22:00+00:00"Beasley, LeRoy B."https://zbmath.org/authors/?q=ai:beasley.leroy-bA rank function on an additive monoid \(\mathcal{Q}\) is a function \(f:\mathcal{Q}\rightarrow\mathbb{N}\) such that (i) \(f(A)=0\) if and only if
\(A=0\) and (ii) \(f(A+B)\leq f(A)+f(B)\) for all \(A\) and \(B\). This paper is a short catalogue of examples of rank functions for graphs and for matrices over semirings. For example: for matrices the usual definitions of matrix rank involve rank functions which are all equivalent for matrices over a field but can differ for matrices over a semiring; for any vector space norm \(\left\Vert
~\right\Vert \) over a field \(v\longmapsto\left\lceil \left\Vert v\right\Vert \right\rceil \) is a rank function; and various covering and partition numbers in graphs are rank functions.
For the entire collection see [Zbl 1433.05003].
Reviewer: John D. Dixon (Ottawa)Three-term polynomial progressions in subsets of finite fields.https://zbmath.org/1456.110152021-04-16T16:22:00+00:00"Peluse, Sarah"https://zbmath.org/authors/?q=ai:peluse.sarahSummary: \textit{J. Bourgain} and \textit{M. C. Chang} [Isr. J. Math. 221, No. 2, 853--867 (2017; Zbl 1420.11024)] recently showed that any subset of \(\mathbb{F}_p\) of density \(\gg p^{-1/15}\) contains a nontrivial progression \(x\), \(x + y\), \(x + y^2\). We answer a question of theirs by proving that if \(P_1, P_2 \in \mathbb{Z}[y]\) are linearly independent and satisfy \(P_1(0) = P_2(0) = 0\), then any subset of \(\mathbb{F}_p\) of density \(\gg_{P_1,P_2}p^{-1/24}\) contains a nontrivial polynomial progression \(x\), \(x + P_1(y)\), \(x + P_2(y)\).Automorphisms and isomorphisms of some \(p\)-ary bent functions.https://zbmath.org/1456.941442021-04-16T16:22:00+00:00"Dempwolff, Ulrich"https://zbmath.org/authors/?q=ai:dempwolff.ulrichIn this continuation of the author's paper [Commun. Algebra 34, No. 3, 1077--1131 (2006; Zbl 1085.05019)]
on Boolean (bent) functions, \(p\)-ary bent functions are similarly investigated. EA-equivalence of (bent) functions is in general not easy to decide. Simple invariants, like algebraic degree, are usually not sufficient to decide equivalence of bent functions, stronger methods seem necessary.
In this paper, group-theoretic methods are applied to analyse equivalence of (some classes of) \(p\)-ary bent functions. For a given (bent) function \(f\) from an \(n\)-dimensional vector space \(V\) over \(\mathbb{F}_p\) to \(\mathbb{F}_p\), the author considers the group \(\mathbf{EA}(f)\) of EA automorphisms, i.e. \(\phi_{11} \in (V)\),
\(\phi_{22} \in \mathrm{GL}(\mathbb{F}_p)\), \(\phi_{12} \in \Hom(V,\mathbb{F}_p)\) and \(v\in V, w\in \mathbb{F}_p\) such that
\[ f(\phi_{11}(x)+v) = \phi_{22}(f(x)) + \phi_{12}(x) + w \quad\text{for all }x\in V. \]
The structure of this group is invariant under EA-equivalence.
As another invariant under EA-equivalence for \(p\)-ary functions, the author suggests the set \(\{v\in V, D_v^2f = 0\}\), where \(D_vf(x) = f(x+v)-f(x)\) denotes the derivative of \(f\) in direction \(v\).
In the first part, the author discusses a secondary construction of three types of (non-quadratic) bent functions \(f\), describes \(\mathbf{EA}(f)\) and as a consequence solves the equivalence problem for these types of bent functions.
In the second part of the paper, \(\mathbf{EA}(f)\) is described for Maiorana-McFarland bent functions of the form \(\mathrm{Tr}_n(xy^l)\), \(\gcd(l,p^n-1) = 1\), and the question when two such bent functions are EA-equivalent is solved.
Reviewer: Wilfried Meidl (Linz)On the structure of large sum-free sets of integers.https://zbmath.org/1456.110162021-04-16T16:22:00+00:00"Tran, Tuan"https://zbmath.org/authors/?q=ai:tran.tuan-anh|tran.tuan-duySummary: A set of integers is called sum-free if it contains no triple \((x, y, z)\) of not necessarily distinct elements with \(x + y = z\). In this paper, we provide a structural characterisation of sum-free subsets of \(\{1, 2,\ldots,n\}\) of density at least \(2/5 - c\), where \(c\) is an absolute positive constant. As an application, we derive a stability version of \textit{M.-C. Hu}'s Theorem [Proc. Am. Math. Soc. 80, 711--712 (1980; Zbl 0441.10045)] about the maximum size of a union of two sum-free sets in \(\{1, 2,\ldots,n\}\). We then use this result to show that the number of subsets of \(\{1, 2,\ldots,n\}\) which can be partitioned into two sum-free sets is \(\Theta(2^{4n/5})\), confirming a conjecture of \textit{R. Hancock} et al. [SIAM J. Discrete Math. 33, No. 1, 153--188 (2019; Zbl 1403.05094)].Construction results for strong orthogonal arrays of strength three.https://zbmath.org/1456.621662021-04-16T16:22:00+00:00"Shi, Chenlu"https://zbmath.org/authors/?q=ai:shi.chenlu"Tang, Boxin"https://zbmath.org/authors/?q=ai:tang.boxin\textit{Y. He} and \textit{B. Tang} [Biometrika 100, No. 1, 254--260 (2013; Zbl 1284.62487)] introduced strong orthogonal arrays (SOAs) as space-filling designs for computer experiments. SOAs of strength 3 are most useful, since SOAs of strength 2 are no more space filling than ordinary orthogonal arrays of strength 2 and SOAs of strength 4 or higher are prohibitively expensive. The existence of strength-three SOAs was
completely characterized in [\textit{Y. He} and \textit{B. Tang}, Ann. Stat. 42, No. 4, 1347--1360 (2014; Zbl 1306.62188)], but the construction of these arrays was not explored.
In the paper under review, 3 families of strength-three SOAs are presented. The arrays in one of these families enjoy some of the space-filling properties of strength-four SOAs. The theory of maximal designs and their doubling constructions plays a crucial role in the theoretical arguments.
Reviewer: Oleksandr Kukush (Kyïv)Decomposable twofold triple systems with non-Hamiltonian 2-block intersection graphs.https://zbmath.org/1456.050202021-04-16T16:22:00+00:00"Cameron, Rosalind A."https://zbmath.org/authors/?q=ai:cameron.rosalind-a"Pike, David A."https://zbmath.org/authors/?q=ai:pike.david-aSummary: The \(2\)-block intersection graph \((2\)-BIG) of a twofold triple system (TTS) is the graph whose vertex set is composed of the blocks of the TTS and two vertices are joined by an edge if the corresponding blocks intersect in exactly two elements. The \(2\)-BIGs are themselves interesting graphs: each component is cubic and \(3\)-connected, and a \(2\)-BIG is bipartite exactly when the TTS is decomposable to two Steiner triple systems. Any connected bipartite \(2\)-BIG with no Hamilton cycle is a further counter-example to a disproved conjecture posed by \textit{W. T. Tutte} in [Discrete Math. 1, 203--208 (1971; Zbl 0219.05075)]. Our main result is that there exists an integer \(N\) such that for all \(v\geqslant N\), if \(v\equiv 1\) or \(3\bmod{6}\) then there exists a TTS \((v)\) whose \(2\)-BIG is bipartite and connected but not Hamiltonian. Furthermore, \(13<N\leqslant 663\). Our approach is to construct a TTS \((u)\) whose \(2\)-BIG is connected bipartite and non-Hamiltonian and embed it within a TTS \((v)\) where \(v>2u\) in such a way that, after a single trade, the \(2\)-BIG of the resulting TTS \((v)\) is bipartite connected and non-Hamiltonian.The unbreakable frame matroids.https://zbmath.org/1456.050282021-04-16T16:22:00+00:00"Fife, Tara"https://zbmath.org/authors/?q=ai:fife.tara"Mayhew, Dillon"https://zbmath.org/authors/?q=ai:mayhew.dillon"Oxley, James"https://zbmath.org/authors/?q=ai:oxley.james-g"Semple, Charles"https://zbmath.org/authors/?q=ai:semple.charlesFor any graph \(G\), let \(\widetilde{G}\) be its underlying simple graph.
The authors of this paper prove that if \(M(G,\Psi)\) is a 3-connected unbreakable frame matroid
for some graph \(G\) with at least 7 vertices, none of which is isolated,
then \(\widetilde{G}\) is obtained from a complete graph by deleting the edges of a path of
length at most two.
The authors also prove that if \(H\) is a simple graph with at least 7 vertices,
then \(H = \widetilde{G}\) for some graph \(G\) for which \(M(G,\Psi)\) is a 3-connected frame matroid.
The first result generalises a characterisation of unbreakable regular matroids proved in
[\textit{S. Pfeil}, Properties of matroid connectivity. Baton Rouge, LA: Louisiana State University (PhD Thesis) (2016)].
Reviewer: Thomas Britz (Sydney)Some bounds arising from a polynomial ideal associated to any \(t\)-design.https://zbmath.org/1456.050222021-04-16T16:22:00+00:00"Martin, William J."https://zbmath.org/authors/?q=ai:martin.william-j"Stinson, Douglas R."https://zbmath.org/authors/?q=ai:stinson.douglas-rSummary: We consider ordered pairs \((X,\mathcal{B})\) where \(X\) is a finite set of size \(v\) and \(\mathcal{B}\) is some collection of \(k\)-element subsets of \(X\) such that every \(t\)-element subset of \(X\) is contained in exactly \(\lambda \) ``blocks'' \(B\in\mathcal{B}\) for some fixed \(\lambda\). We represent each block \(B\) by a zero-one vector \(\mathbf{c}_B\) of length \(v\) and explore the ideal \(\mathcal{I}(\mathcal{B})\) of polynomials in \(v\) variables with complex coefficients which vanish on the set \(\{\mathbf{c}_B\mid B\in\mathcal{B}\}\). After setting up the basic theory, we investigate two parameters related to this ideal: \(\gamma_1(\mathcal{B})\) is the smallest degree of a non-trivial polynomial in the ideal \(\mathcal{I}(\mathcal{B})\) and \(\gamma_2(\mathcal{B})\) is the smallest integer \(s\) such that \(\mathcal{I}(\mathcal{B})\) is generated by a set of polynomials of degree at most \(s\). We first prove the general bounds \(t/2<\gamma_1(\mathcal{B})\leq\gamma_2(\mathcal{B})\leq k\). Examining important families of examples, we find that, for symmetric 2-designs and Steiner systems, we have \(\gamma_2(\mathcal{B})\leq t\). But we expect \(\gamma_2(\mathcal{B})\) to be closer to \(k\) for less structured designs and we indicate this by constructing infinitely many triple systems satisfying \(\gamma_2(\mathcal{B})=k\).Mixture designs constructed using Taguchi's mixed element orthogonal arrays.https://zbmath.org/1456.621612021-04-16T16:22:00+00:00"Singh, Poonam"https://zbmath.org/authors/?q=ai:singh.poonam"Sarin, Vandana"https://zbmath.org/authors/?q=ai:sarin.vandana"Midha, Neha"https://zbmath.org/authors/?q=ai:midha.nehaSummary: This paper proposes an algorithm for generating mixture designs based on Taguchi's mixed element orthogonal arrays. The algorithm enables the construction of cost-effective and efficient mixture designs for Scheffé's canonical polynomials.Equality case in Van der Corput's inequality and collisions in multiple lattice tilings.https://zbmath.org/1456.050302021-04-16T16:22:00+00:00"Averkov, Gennadiy"https://zbmath.org/authors/?q=ai:averkov.gennadiySummary: Van der Corput's provides the sharp bound \(\text{vol} (C) \le m 2^d\) on the volume of a \(d\)-dimensional origin-symmetric convex body \(C\) that has \(2m - 1\) points of the integer lattice in its interior. For \(m = 1\), a characterization of the equality case \(\text{vol} (C) = m 2^d\) is equivalent to the well-known problem of characterizing tilings by translations of a convex body. It is rather surprising that so far, for \(m \ge 2\), no characterization of the equality case has been available, though a hint to the respective characterization problem can be found in the monograph of \textit{P. M. Gruber} and \textit{C. G. Lekkerkerker} [Geometry of numbers. 2nd ed. Elsevier (North-Holland), Amsterdam (1987; Zbl 0611.10017)]. We give an explicit characterization of the equality case for all \(m \ge 2\). Our result reveals that, the equality case for \(m \ge 2\) is more restrictive than for \(m = 1\). We also present consequences of our characterization in the context of multiple lattice tilings.Balanced semi-Latin rectangles: properties, existence and constructions for block size two.https://zbmath.org/1456.621622021-04-16T16:22:00+00:00"Uto, N. P."https://zbmath.org/authors/?q=ai:uto.n-p"Bailey, R. A."https://zbmath.org/authors/?q=ai:bailey.rosemary-aSummary: There exists a set of designs which form a subclass of semi-Latin rectangles. These designs, besides being semi-Latin rectangles, exhibit an additional property of balance, where no two distinct pairs of symbols (treatments) differ in their concurrences, that is, each pair of distinct treatments concurs a constant number of times in the design. Such a design exists for a limited set of parameter combinations. We designate it a balanced semi-Latin rectangle and give some properties and necessary conditions for its existence. Furthermore, algorithms for constructing the design for experimental situations where there are two treatments in each row-column intersection (block) are also given.Optimal design of fMRI experiments using circulant (almost-)orthogonal arrays.https://zbmath.org/1456.050242021-04-16T16:22:00+00:00"Lin, Yuan-Lung"https://zbmath.org/authors/?q=ai:lin.yuan-lung"Phoa, Frederick Kin Hing"https://zbmath.org/authors/?q=ai:phoa.frederick-kin-hing"Kao, Ming-Hung"https://zbmath.org/authors/?q=ai:kao.ming-hungSummary: Functional magnetic resonance imaging (fMRI) is a pioneering technology for studying brain activity in response to mental stimuli. Although efficient designs on these fMRI experiments are important for rendering precise statistical inference on brain functions, they are not systematically constructed. Design with circulant property is crucial for estimating a hemodynamic response function (HRF) and discussing fMRI experimental optimality. In this paper, we develop a theory that not only successfully explains the structure of a circulant design, but also provides a method of constructing efficient fMRI designs systematically. We further provide a class of two-level circulant designs with good performance (statistically optimal), and they can be used to estimate the HRF of a stimulus type and study the comparison of two HRFs. Some efficient three- and four-levels circulant designs are also provided, and we proved the existence of a class of circulant orthogonal arrays.The maximum number of Parter vertices of acyclic matrices.https://zbmath.org/1456.051032021-04-16T16:22:00+00:00"Fonseca, Amélia"https://zbmath.org/authors/?q=ai:fonseca.amelia"Mestre, Ângela"https://zbmath.org/authors/?q=ai:mestre.angela"Mohammadian, Ali"https://zbmath.org/authors/?q=ai:mohammadian.ali"Perdigão, Cecília"https://zbmath.org/authors/?q=ai:perdigao.cecilia"Torres, Maria Manuel"https://zbmath.org/authors/?q=ai:torres.maria-manuelThis manuscript deals with the maximum number of Parter vertices of a singular symmetric matrix whose underlying graph is a tree.
In this paper, all graphs are assumed to be finite, undirected and without loops or multiple edges. Let \(G\) be a graph with vertex set \(V(G)\) and edge set \(E(G)\). \(S_F(G)\) denotes the set of all the symmetric matrices \(A\) with entries in the field \(F\), whose rows and columns are indexed by \(V(G)\), such that for every two distinct vertices \(u, v \in V(G)\), the \((u,v)\)-entry of \(A\) is nonzero if and only if \((u,v) \in E(G)\). The adjacency matrix of \(G\), \(\mathcal{A}(G)\), is a \((0,1)\)-matrix in \(S_F(G)\) all of whose diagonal entries are equal \(0\). In fact, the matrices in \(S_F(G)\) can be seen as weighted adjacency matrices of \(G\). For any tree \(T\), the elements of \(S_F(T)\) are referred as acyclic matrices.
For every matrix \(A \in S_F(G)\) and subset \(X\) of \(V(G)\), the principal submatrix of \(A\) obtained by deleting the rows and columns indexed by \(X\) is denoted by \(A(X)\). Let \(G\) be a graph with \(n=|V(G)|\) and let \(A \in S_F(G)\). A vertex \(v \in V(G)\) is a Parter vertex of \(A\) if \(\eta(A(v))=\eta(A)+1\), where \(\eta(A)\) denotes the dimension of \(\ker{A}\).
In this paper, the authors are interested in the maximum number of Parter vertices of singular acyclic matrices. It is known that this number, for a singular matrix with rank \(r\) whose underlying graph has no isolated vertices, is at most \(r-1\). In addition, the maximum number of Parter vertices of \(n \times n\) singular acyclic matrices is \(2\lfloor\frac{n-1}{2}\rfloor-1\).
As a generalization, the authors prove that the number of Parter vertices of singular acyclic matrices with rank \(r\) is at most \(2\lfloor\frac{r}{2}\rfloor-1\). They also characterize the structure of trees which achieve this upper bound.
Reviewer: Juan Ramón Torregrosa Sánchez (Valencia)A \(q\)-queens problem. V: Some of our favorite pieces: queens, bishops, rooks, and nightriders.https://zbmath.org/1456.050052021-04-16T16:22:00+00:00"Chaiken, Seth"https://zbmath.org/authors/?q=ai:chaiken.seth"Hanusa, Christopher R. H."https://zbmath.org/authors/?q=ai:hanusa.christopher-r-h"Zaslavsky, Thomas"https://zbmath.org/authors/?q=ai:zaslavsky.thomasSummary: Parts I--IV [the authors, Electron. J. Comb. 21, No. 3, Research Paper P3.33, 28 p. (2014; Zbl 1298.05021); J. Algebr. Comb. 41, No. 3, 619--642 (2015; Zbl 1314.05008); Australas. J. Comb. 74, Part 2, 305--331 (2019; Zbl 1419.05015); Ars Math. Contemp. 16, No. 2, 549--561 (2019; Zbl 1416.05131)] showed that the number of ways to place \(q\) nonattacking queens or similar chess pieces on an \(n\times n\) chessboard is a quasipolynomial function of \(n\) whose coefficients are essentially polynomials in \(q\). For partial queens, which have a subset of the queen's moves, we proved complete formulas for these counting quasipolynomials for small numbers of pieces and other formulas for high-order coefficients of the general counting quasipolynomials. We found some upper and lower bounds for the periods of those quasipolynomials by calculating explicit denominators of vertices of the inside-out polytope.
Here we discover more about the counting quasipolynomials for partial queens, both familiar and strange, and the nightrider and its subpieces, and we compare our results to the empirical formulas found by Kotěšovec. We prove some of Kotěšovec's formulas and conjectures about the quasipolynomials and their high-order coefficients, and in some instances go beyond them.Flag-transitive point-primitive symmetric \((v,k,\lambda)\) designs with bounded \(k\).https://zbmath.org/1456.050232021-04-16T16:22:00+00:00"Zhang, Zhilin"https://zbmath.org/authors/?q=ai:zhang.zhilin"Yuan, Pingzhi"https://zbmath.org/authors/?q=ai:yuan.pingzhi"Zhou, Shenglin"https://zbmath.org/authors/?q=ai:zhou.shenglinAuthors' abstract: In [J. Comb. Des. 21, No. 3--4, 127--141 (2013; Zbl 1273.05028)] \textit{D. Tian} and \textit{S. Zhou} conjectured that a flag-transitive and point-primitive automorphism group of a symmetric \((v,k,\lambda)\) design must be an affine or almostsimple group. In this paper, we study this conjecture and prove that if \(k \le 10^3\) and \(G \le \Aut({\mathcal D})\) is flag-transitive and point-primitive, then \(G\) is affine or almost simple.This supports the conjecture.
Reviewer: Dean Crnković (Rijeka)On the balanced upper chromatic number of finite projective planes.https://zbmath.org/1456.050542021-04-16T16:22:00+00:00"Blázsik, Zoltán L."https://zbmath.org/authors/?q=ai:blazsik.zoltan-l"Blokhuis, Aart"https://zbmath.org/authors/?q=ai:blokhuis.aart"Miklavič, Štefko"https://zbmath.org/authors/?q=ai:miklavic.stefko"Nagy, Zoltán Lóránt"https://zbmath.org/authors/?q=ai:nagy.zoltan-lorant"Szőnyi, Tamás"https://zbmath.org/authors/?q=ai:szonyi.tamasSummary: In this paper, we study vertex colorings of hypergraphs in which all color class sizes differ by at most one (balanced colorings) and each hyperedge contains at least two vertices of the same color (rainbow-free colorings). For any hypergraph \(H\), the maximum number \(k\) for which there is a balanced rainbow-free \(k\)-coloring of \(H\) is called the balanced upper chromatic number of the hypergraph. We confirm the conjecture of \textit{G. Araujo-Pardo} et al. [ibid. 338, No. 12, 2562--2571 (2015; Zbl 1317.05046)] by determining the balanced upper chromatic number of the desarguesian projective plane \(\operatorname{PG} ( 2 , q )\) for all \(q\). In addition, we determine asymptotically the balanced upper chromatic number of several families of non-desarguesian projective planes and also provide a general lower bound for arbitrary projective planes using probabilistic methods which determines the parameter up to a multiplicative constant.Turán and Ramsey numbers in linear triple systems.https://zbmath.org/1456.050862021-04-16T16:22:00+00:00"Gyárfás, András"https://zbmath.org/authors/?q=ai:gyarfas.andras"Sárközy, Gábor N."https://zbmath.org/authors/?q=ai:sarkozy.gabor-nSummary: In this paper we study Turán and Ramsey numbers in linear triple systems, defined as 3-uniform hypergraphs in which any two triples intersect in at most one vertex.
A famous result of \textit{I. Z. Ruzsa} and \textit{E. Szemerédi} [in: Combinatorics. Combinatorial colloquium held at Keszthely, Hungary, from 28 June to 3 July 1976. Vol. I and II. Amsterdam-Oxford-New York: North-Holland Publishing Company. 939--945 (1978; Zbl 0393.05031)] is that for any fixed \(c > 0\) and large enough \(n\) the following Turán-type theorem holds. If a linear triple system on \(n\) vertices has at least \(c n^2\) edges then it contains a triangle: three pairwise intersecting triples without a common vertex. In this paper we extend this result from triangles to other triple systems, called \(s\)-configurations. The main tool is a generalization of the induced matching lemma from \(a b a\)-patterns to more general ones.
We slightly generalize \(s\)-configurations to extended \(s\)-configurations. For these we cannot prove the corresponding Turán-type theorem, but we prove that they have the weaker, Ramsey property: they can be found in any \(t\)-coloring of the blocks of any sufficiently large Steiner triple system. Using this, we show that all unavoidable configurations with at most 5 blocks, except possibly the ones containing the sail \(C_{15} \) (configuration with blocks 123, 345, 561 and 147), are \(t\)-Ramsey for any \(t \geq 1\). The most interesting one among them is the wicket, \( D_4\), formed by three rows and two columns of a \(3 \times 3\) point matrix. In fact, the wicket is 1-Ramsey in a very strong sense: all Steiner triple systems except the Fano plane must contain a wicket.Dynamics near an idempotent.https://zbmath.org/1456.370232021-04-16T16:22:00+00:00"Shaikh, Md. Moid"https://zbmath.org/authors/?q=ai:shaikh.md-moid"Patra, Sourav Kanti"https://zbmath.org/authors/?q=ai:patra.sourav-kanti"Ram, Mahesh Kumar"https://zbmath.org/authors/?q=ai:ram.mahesh-kumarSummary: \textit{N. Hindman} and \textit{I. Leader} [Semigroup Forum 59, No. 1, 33--55 (1999; Zbl 0942.22003)]
first introduced the notion of the semigroup of ultrafilters converging to zero for a dense subsemigroup of \(((0, \infty), +)\). Using the algebraic structure of the Stone-Čech compactification, \textit{M. A. Tootkaboni} and \textit{T. Vahed} [Topology Appl. 159, No. 16, 3494--3503 (2012; Zbl 1285.54017)]
generalized and extended this notion to an idempotent instead of zero, that is a semigroup of ultrafilters converging to an idempotent \(e\) for a dense subsemigroup of a semitopological semigroup \((R, +)\) and they gave the combinatorial proof of the Central Sets Theorem near \(e\). Algebraically one can define quasi-central sets near \(e\) for dense subsemigroups of \((R, +)\). In a dense subsemigroup of \((R, +)\), C-sets near \(e\) are the sets, which satisfy the conclusions of the Central Sets Theorem near \(e\). \textit{S. K. Patra} [Topology Appl. 240, 173--182 (2018; Zbl 1392.37008)]
gave dynamical characterizations of these combinatorially rich sets near zero. In this paper, we shall establish these dynamical characterizations for these combinatorially rich sets near \(e\). We also study minimal systems near \(e\) in the last section of this paper.A weakly universal cellular automaton in the heptagrid of the hyperbolic plane.https://zbmath.org/1456.681042021-04-16T16:22:00+00:00"Margenstern, Maurice"https://zbmath.org/authors/?q=ai:margenstern.mauriceSummary: In this paper, we construct a weakly universal cellular automaton (CA) in the heptagrid, the tessellation \(\{7,3\}\) that takes place in the hyperbolic plane. The CA is not rotation invariant but is truly planar. This result, under these conditions, cannot be improved for the tessellations \(\{p,3\}\) of the hyperbolic plane.Induced designs and fixed points.https://zbmath.org/1456.050212021-04-16T16:22:00+00:00"Chen, Jianfu"https://zbmath.org/authors/?q=ai:chen.jianfu"Zhou, Shenglin"https://zbmath.org/authors/?q=ai:zhou.shenglinSummary: Let \(\mathcal{D}\) be a 2-\(( v , k , 1 )\) design and \(H\) be an automorphism group of \(\mathcal{D} \). This paper studies the induced design on the fixed points of \(H\), denoted by \(\operatorname{Fix} H\). We extend the work of \textit{A. Camina} and \textit{J. Siemons} [J. Comb. Theory, Ser. A 51, No. 2, 268--276 (1989; Zbl 0675.05008)] and we also state that if there is an induced design on \(\operatorname{Fix} H\), then \(| \operatorname{Fix} H | \leq r\) in most cases, where \(r\) is the number of blocks containing a given point. Moreover, for a given \(k_0\), there exist only finitely many designs admitting an induced design on \(\operatorname{Fix} H\) with \(| \operatorname{Fix} H | > r\) and block size \(k_0\).Generalization of pinching operation to binary matroids.https://zbmath.org/1456.050292021-04-16T16:22:00+00:00"Ghorbani, Vahid"https://zbmath.org/authors/?q=ai:ghorbani.vahid"Azadi, Ghodratollah"https://zbmath.org/authors/?q=ai:azadi.ghodratollah"Azanchiler, Habib"https://zbmath.org/authors/?q=ai:azanchiler.habibSummary: In this paper, we generalize the pinching operation on two edges of graphs to binary matroids and investigate some of its basic properties. For \(n\geq 2\), the matroid that is obtained from an \(n\)-connected matroid by this operation is a \(k\)-connected matroid with \(k\in\{2,3,4\}\) or is a disconnected matroid. We find conditions to guarantee this \(k\). Moreover, we show that Eulerian binary matroids are characterized by this operation and we also provide some interesting applications of this operation.