Utilitas Algorithmica (UA)

ISSN: xxxx-xxxx (print)

Utilitas Algorithmica (UA) is a premier, open-access international journal dedicated to advancing algorithmic research and its applications. Launched to drive innovation in computer science, UA publishes high-impact theoretical and experimental papers addressing real-world computational challenges. The journal underscores the vital role of efficient algorithm design in navigating the growing complexity of modern applications. Spanning domains such as parallel computing, computational geometry, artificial intelligence, and data structures, UA is a leading venue for groundbreaking algorithmic studies.

Debashish Bose1, C.P. Anil Kumar2, R. Krishnan3, Shobha Madan4
1Indian Institute of Technology Kanpur, India
2Infosys, Bangalore, India
3Institute of Mathematical Sciences, Chennai, India
4Indian Institute of Technology Kanpur, India
Abstract:

In this paper, we prove the Tiling implies Spectral part of Fuglede’s cojecture for the three interval case. Then we prove the converse Spectral implies Tiling in the case of three equal intervals and also in the case where the intervals have lengths 1/2, 1/4, 1/4. Next, we consider a set Ω ⊂ R, which is a union of n intervals. If Ω is a spectral set, we prove a structure theorem for the spectrum provided the spectrum is assumed to be contained in some lattice. The method of this proof has some implications on the Spectral implies Tiling part of Fuglede’s conjecture for three intervals. In the final step in the proof, we need a symbolic computation using Mathematica. Finally with one additional assumption we can conclude that the Spectral implies Tiling holds in this case.

Tom Sanders 1
1Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, England
Abstract:

We show that if \( A \) is a finite subset of an abelian group with additive energy at least \( c|A|^3 \), then there is a set \( \mathcal{L} \subset A \) with \( |\mathcal{L}| = O(c^{-1} \log |A|) \) such that \( |A \cap \mathrm{Span}(\mathcal{L})| = \Omega(c^{1/3} |A|) \).

Tom Sanders1
1Department of Pure Mathematics and Mathematical Statistics, University of Cambridge, Wilberforce Road, Cambridge CB3 0WA, England
Abstract:

We provide further explanation of the significance of an example in a recent paper of Wolf in the context of the problem of finding large subspaces in sumsets.

Abstract:

Lucy Slater used Bailey’s \( {}_6\psi_6 \) summation formula to derive the Bailey pairs she used to construct her famous list of 130 identities of the Rogers-Ramanujan type.

In the present paper, we apply the same techniques to Chu’s \( {}_{10}\psi_{10} \) generalization of Bailey’s formula to produce quite general Bailey pairs. Slater’s Bailey pairs are then recovered as special limiting cases of these more general pairs.

In re-examining Slater’s work, we find that her Bailey pairs are, for the most part, special cases of more general Bailey pairs containing one or more free parameters. Further, we also find new general Bailey pairs (containing one or more free parameters) which are also implied by the \( {}_6\psi_6 \) summation formula.

Slater used the Jacobi triple product identity (sometimes coupled with the quintuple product identity) to derive her infinite products. Here we also use other summation formulae (including special cases of the \( {}_6\psi_6 \) summation formula and Jackson’s \( {}_6\phi_5 \) summation formula) to derive some of our infinite products. We use the new Bailey pairs, and/or the summation methods mentioned above, to give new proofs of some general series-product identities due to Ramanujan, Andrews, and others. We also derive a new general series-product identity, one which may be regarded as a partner to one of the Ramanujan identities. We also find new transformation formulae between basic hypergeometric series, new identities of Rogers-Ramanujan type, and new false theta series identities. Some of these latter are a kind of “hybrid” in that one side of the identity consists of a basic hypergeometric series, while the other side is formed from a theta product multiplied by a false theta series. This type of identity appears to be new.

Mordechay B. Levin1
1Department of Mathematics, Bar-Ilan University, Ramat-Gan, 52900, Israel
Abstract:

In [Fr2, Skr], Frolov and Skriganov showed that low discrepancy point sets in the multidimensional unit cube \([0,1)^s\) can be obtained from admissible lattices in \( \mathbb{R}^s \). In this paper, we get a similar result for the case of \( (\mathbb{F}_q((x^{-1})))^s \). Then we combine this approach with Halton’s construction of low discrepancy sequences.

Weiping Wang1, Tianming Wang1,2
1Department of Applied Mathematics, Dalian University of Technology Dalian 116024, P.R.China
2Department of Mathematics, Hainan Normal University Haikou 571158, P.R.China
Abstract:

The current paper deals with two special matrices \(T_n\) and \(W_n\) related to the Pascal, Vandermonde, and Stirling matrices. As a result, various properties of the entries of \(T_n\) and \(W_n\) are obtained, including the generating functions, recurrence relations, and explicit expressions. Some additional results are also presented.

Hao Li1, Mariusz Wozniak2
1L RI, UMR 8623, Bat. 490 Université de Paris-Sud 91405 Orsay, France
2Faculty of Applied Mathematics A G H Al. Mickiewicza 30 30-059 Krakéw, Poland
Abstract:

There are some results and many conjectures with the conclusion that a graph \(G\) contains all trees of given size \(k\). We prove some new results of this type.

Caihuan Zhang1,2, Zhizheng Zhang3,4
1 Department of Mathematics, Luoyang Teachers’ College, Luoyang 471022, P.R.China
2Department of Applied Mathematics, Dalian University of Technology, Dalian 116024, P. R. China
3Department of Mathematics, Luoyang Teachers’ College, Luoyang 471022, P.R.China
4College of Mathematics and Information Science, Henan University, Kaifeng 475001, P. R. China
Abstract:

In \([3]\), we gave a factorization of the generalized Lah matrix.In this short note, we show its another factorization. From this factorization, several interesting combinatorial identities involving the Fibonacci numbers are obtained.

Qingde Kang1, Chunping Ma2, Hongtao Zhao1
1Institute of Mathematics, Hebei Normal University, Shijiazhuang 050016, P. R. China
2Department of Applied Mathematics, North China Electric Power University, Baoding 071003, P. R. China
Abstract:

Let \(\lambda K_v\) be the complete multigraph with \(v\) vertices. Let \(G\) be a finite simple graph. A \(G\)-decomposition of \(K_v\), denoted by \(G-GD_\lambda(v)\), is a pair \((X, \mathcal{B})\) where \(X\) is the vertex set of \(K_v\) and \(\mathcal{B}\) is a collection of subgraphs of \(K_v\), called blocks, such that each block is isomorphic to \(G\) and any two distinct vertices in \(K_v\) are joined in exactly one block of \(\mathcal{B}\). In this paper, nine graphs \(G_i\) with six vertices and nine edges are discussed, and the existence of \(G_i-GD_\lambda(v)\) is given, \(1 \leq i \leq 9\).

Johannes H.Hattingh1, Andrew R.Plummer1
1Department of Mathematics and Statistics University Plaza Georgia State University Atlanta, Georgia 30303, USA
Abstract:

Let \(G = (V, E)\) be a graph. A set \(S \subseteq V\) is a restrained dominating set if every vertex not in \(S\) is adjacent to a vertex in \(S\) and to a vertex in \(V – S\). The restrained domination number of \(G\), denoted by \(\gamma_r(G)\), is the smallest cardinality of a restrained dominating set of \(G\). It is known that if \(T\) is a tree of order \(n\), then \(\gamma_r(T) \geq \left\lceil \frac{n+2}{3} \right\rceil\). In this note, we provide a simple constructive characterization of the extremal trees \(T\) of order \(n\) achieving this lower bound.

Special Issues

The Combinatorial Press Editorial Office routinely extends invitations to scholars for the guest editing of Special Issues, focusing on topics of interest to the scientific community. We actively encourage proposals from our readers and authors, directly submitted to us, encompassing subjects within their respective fields of expertise. The Editorial Team, in conjunction with the Editor-in-Chief, will supervise the appointment of Guest Editors and scrutinize Special Issue proposals to ensure content relevance and appropriateness for the journal. To propose a Special Issue, kindly complete all required information for submission;