Search

A Steiner quadruple system of order v + 1 with resolvable derived designs (every derived Steiner triple system of order v at a point is resolvable), abbreviated as RDSQS (v + 1) , has been used to construct a large set of Kirkman triple systems of order 3v. In this paper, an RDSQS (v + 1) is reduced to an overlarge set of Kirkman triple systems of order v with an additional property (OLKTS + (v) ), which plays the same role in constructing an LKTS(3v) as an RDSQS (v + 1) . Some recursive constructions of OLKTS + s are also established. As a result, some infinite classes of OLKTS + s and LKTSs are obtained. [ABSTRACT FROM AUTHOR]

Two resolutions of the same 3-design are said to be orthogonal when each parallel class of one resolution has at most one block in common with each parallel class of the other resolution. If a Steiner quadruple system has two mutually orthogonal resolutions, the design is called doubly resolvable and denoted by DRSQS. In this paper, we define almost doubly resolvable candelabra quadruple system and then to get a recursive construction of DRSQS, i.e., for n ≥ 16 , if there is a DRSQS(n), then there exists a DRSQS (14 n - 12) and a DRSQS (16 n - 12) . [ABSTRACT FROM AUTHOR]

Many modern day cloud hosted applications such as virtual reality, real time games require low latency data access and computation to improve response time. So it is essential to bring the computation and data storage edge servers closer to the user's geographical location to improve response times and save bandwidth. In particulars, in online gaming and on demand video services, the required application data present at cloud servers need to be placed on the edge servers to provide low latency app-functionalities. The transfer of huge amount of data from cloud server to edge server incurs high cost and time penalties. Thus, we need an efficient way to solve edge data distribution (EDD) problem which distribute the application data to the edge servers that minimizes transfer cost. In this work, we provide a refined formulation of an optimal approach to solve the EDD problem using integer linear programming (ILP) technique. Due to the time complexity limitation of the ILP approach, we propose an O(k) approximation algorithm based on network Steiner tree estimation (EDD-NSTE) for estimating solutions to dense large-scale EDD problem. The proposed approach is analyzed to be 11/6 approximation which is better than the state-of-the-art 2 approximation EDD-A approach. The experimental evaluation through simulation using real world EUA data set demonstrate that the EDD-NSTE outperform state-of-the-art approach and other representative approaches. [ABSTRACT FROM AUTHOR]

A subset of vertices of a graph G is a general position set if no triple of vertices from the set lie on a common shortest path in G. In this paper we introduce the general position polynomial as ∑ i ≥ 0 a i x i , where a i is the number of distinct general position sets of G with cardinality i. The polynomial is considered for several well-known classes of graphs and graph operations. It is shown that the polynomial is not unimodal in general, not even on trees. On the other hand, several classes of graphs, including Kneser graphs K(n, 2), with unimodal general position polynomials are presented. [ABSTRACT FROM AUTHOR]

Liu et al. (IEEE Trans Inf Theory 68:3096–3107, 2022) investigated a class of BCH codes C (q , q + 1 , δ , 1) with q = δ m a prime power and proved that the set B δ + 1 of supports of the minimum weight codewords supports a Steiner system S (3 , δ + 1 , q + 1) . In this paper, we give an equivalent formulation of B δ + 1 in terms of elementary symmetric polynomials and then construct a number of mutually disjoint Steiner systems S (3 , δ + 1 , δ m + 1) when m is even and a number of mutually disjoint G-designs G ( δ m + 1 δ + 1 , δ + 1 , δ + 1 , 3) when m is odd. In particular, the existence of three mutually disjoint Steiner systems S (3 , 5 , 4 m + 1) or three mutually disjoint G-designs G ( 4 m + 1 5 , 5 , 5 , 3) is established. [ABSTRACT FROM AUTHOR]

The optical response in a hybrid optomechanical system containing a triple quantum well (TQW) is investigated theoretically. The optomechanical cavity is driven by a strong pump field and a weak probe field. We show that multiple electromagnetically induced transparency windows and optomechanically induced transparency (OMIT) window exist simultaneously for the weak probe field due to the Jaynes–Cummings coupling and optomechanical coupling respectively. Furthermore, the system absorption spectra can be tuned by changing the system coupling strength. Especially, when two external control lasers are applied to the TQW with frequency detuning, multiple transparency windows can be illustrated and adjusted by the external fields. Therefore, via changing the external coupling fields, we can realize manipulating the OMIT transparency window, tunable group delay and switch from fast light to slow light. Such a system may be much practical for the flexibility of TQW in the quantum information processing. [ABSTRACT FROM AUTHOR]

The Steiner subratio is one of the Steiner-type ratios that show how much the weights of optimal connecting graphs in a metric space can differ. In this paper, an upper estimate for the Steiner subratio of Riemannian manifolds is obtained. [ABSTRACT FROM AUTHOR]

Voronoi diagrams on triangulated surfaces based on the geodesic metric play a key role in many applications of computer graphics. Previous methods of constructing such Voronoi diagrams generally depended on having an exact geodesic metric. However, exact geodesic computation is time-consuming and has high memory usage, limiting wider application of geodesic Voronoi diagrams (GVDs). In order to overcome this issue, instead of using exact methods, we reformulate a graph method based on Steiner point insertion, as an effective way to obtain geodesic distances. Further, since a bisector comprises hyperbolic and line segments, we utilize Apollonius diagrams to encode complicated structures, enabling Voronoi diagrams to encode a medial-axis surface for a dense set of boundary samples. Based on these strategies, we present an approximation algorithm for efficient Voronoi diagram construction on triangulated surfaces. We also suggest a measure for evaluating similarity of our results to the exact GVD. Although our GVD results are constructed using approximate geodesic distances, we can get GVD results similar to exact results by inserting Steiner points on triangle edges. Experimental results on many 3D models indicate the improved speed and memory requirements compared to previous leading methods. [ABSTRACT FROM AUTHOR]

We prove that with high probability G (3) (n , n - 1 + o (1)) contains a spanning Steiner triple system for n ≡ 1 , 3 (mod 6) , establishing the exponent for the threshold probability for existence of a Steiner triple system. We also prove the analogous theorem for Latin squares. Our result follows from a novel bootstrapping scheme that utilizes iterative absorption as well as the connection between thresholds and fractional expectation-thresholds established by Frankston, Kahn, Narayanan, and Park. [ABSTRACT FROM AUTHOR]

The existence of large sets of Kirkman triple systems (LKTSs) is one of the best-known open problems in combinatorial design theory. Steiner quadruple systems with resolvable derived designs (RDSQSs) play an important role in the recursive constructions of LKTSs. In this paper, we introduce a special combinatorial structure RDSQS ∗ (v) and use it to present a construction for RDSQS(4v). As a consequence, some new infinite families of LKTSs are given. [ABSTRACT FROM AUTHOR]

The paper deals with t-designs that can be partitioned into s-designs, each missing a point of the underlying set, called point-missing s-resolvable t-designs, with emphasis on their applications in constructing t-designs. The problem considered may be viewed as a generalization of overlarge sets which are defined as a partition of all the v + 1 k k-sets chosen from a (v + 1) -set X into (v + 1) mutually disjoint s- (v , k , δ) designs, each missing a different point of X. Among others, it is shown that the existence of a point-missing (t - 1) -resolvable t- (v , k , λ) design leads to the existence of a t- (v , k + 1 , λ ′) design. As a result, we derive various infinite series of 4-designs with constant index using overlarge sets of disjoint Steiner quadruple systems. These have parameters 4- (3 n , 5 , 5) , 4- (3 n + 2 , 5 , 5) and 4- (2 n + 1 , 5 , 5) , for n ≥ 2 , and were unknown until now. We also include a recursive construction of point-missing s-resolvable t-designs and its application. [ABSTRACT FROM AUTHOR]

We show that every intermediate β -transformation is topologically conjugate to a greedy β -transformation with a hole at zero, and provide a counterexample illustrating that the correspondence is not one-to-one. This characterisation is employed to (1) build a Krieger embedding theorem for intermediate β -transformation, complementing the result of Li, Sahlsten, Samuel and Steiner [22], and (2) obtain new metric and topological results on survivor sets of intermediate β -transformations with a hole at zero, extending the work of Kalle, Kong, Langeveld and Li [18]. Further, we derive a method to calculate the Hausdorff dimension of such survivor sets as well as results on certain bifurcation sets. Moreover, by taking unions of survivor sets of intermediate β -transformations one obtains an important class of sets arising in metric number theory, namely sets of badly approximable numbers in non-integer bases. We prove, under the assumption that the underlying symbolic space is of finite type, that these sets of badly approximable numbers are winning in the sense of Schmidt games, and hence have the countable intersection property, extending the results of Hu and Yu [15], Tseng [35] and Färm, Persson and Schmeling [11]. [ABSTRACT FROM AUTHOR]

A spanning tree T in a graph G is a sub-graph of G with the same vertex set as G which is a tree. In 1981, McKay proved an asymptotic result regarding the number of spanning trees in random k-regular graphs. In this paper we prove a high-dimensional generalization of McKay's result for random d-dimensional, k-regular simplicial complexes on n vertices, showing that the weighted number of simplicial spanning trees is of order (ξ d , k + o (1)) n d as n → ∞ , where ξ d , k is an explicit constant, provided k > 4 d 2 + d + 2 . A key ingredient in our proof is the local convergence of such random complexes to the d-dimensional, k-regular arboreal complex, which allows us to generalize McKay's result regarding the Kesten–McKay distribution. [ABSTRACT FROM AUTHOR]

A linear code is called a locally repairable code (LRC) with locality r if one can recover an erased code symbol by accessing at most r other code symbols. Constructions of LRCs have been widely investigated in recent years. In this paper, we give a step forward in this direction. Firstly, we propose a novel concept of perfect LRCs whose size exactly achieves the Hamming-type bound, similar to the perfect codes that achieving the Hamming bound in classical coding theory. By the parity-check matrix approach, we establish some important connections between the existence of LRCs and the existence of some subsets of finite geometry and finite fields with certain properties, respectively. By employing q-Steiner systems and sunflowers in projective geometry and difference sets in finite fields, we obtain two new constructions of perfect LRCs with flexible parameters and present several new constructions of k-optimal LRCs achieving another Hamming-type bound under the integers restriction. Moreover, for fixed q and r, the code lengths of all the q-ary r-LRCs constructed in this paper can be arbitrarily large and the code rates can asymptotically achieve the upper bound r r + 1 . [ABSTRACT FROM AUTHOR]

We investigate the mesoscopic electron transport through multiple quantum dot systems in a T-shaped configuration and analyse the effect of the number of quantum dots on transport observables. Analytically, the expressions for the transmission probability and current have been derived, in the presence of intradot Coulomb interaction, using non-equilibrium Green function techniques. The higher-order Green functions containing the Coulomb interaction term have been decoupled using the mean-field approximation. The analytical, as well as the numerical, calculations have been presented for single, double and triple quantum dot systems in T-shaped configuration and then the results have been generalised for N number of quantum dots in the same configuration. The transport observables, such as transmission coefficient, I–V characteristics and differential conductance, have been numerically analysed. Numerical results show a systematic variation in the number of transmission spectrum peaks as the number of quantum dots side-coupled to the active dot increases. It is found that the number of the transmission probability peaks is directly related to the number of quantum dots and the peak spacings are controlled by the inter-dot coupling strength. However, the magnitude of the current is hardly affected by the increase in the number of side-coupled dots in T-shaped quantum dot systems. [ABSTRACT FROM AUTHOR]

Abraham A. Ungar investigated in 1988 the relativistic velocity addition HT ht on HT ht , which is neither commutative nor associative. Given a nearfield I F i the group HT ht Graph of all affine translations operates sharply 2-transitively on I F i . Conversely, if I T i is a sharply 2-transitive permutation group on a finite set I F i , then, according to Robert D. Carmichael, two operations can be defined on I F i such that I F i is made into a nearfield and I T i is isomorphic to the group HT ht . [Extracted from the article]

This paper studies the problem of detecting asymptomatic cases in a temporal contact network in which multiple outbreaks have occurred. We show that the key to detecting asymptomatic cases well is taking into account both individual risk and the likelihood of disease-flow along edges. We consider both aspects by formulating the asymptomatic case detection problem as a directed prize-collecting Steiner tree (Directed PCST) problem. We present an approximation-preserving reduction from this problem to the directed Steiner tree problem and obtain scalable algorithms for the Directed PCST problem on instances with more than 1.5M edges obtained from both synthetic and fine-grained hospital data. On synthetic data, we demonstrate that our detection methods significantly outperform various baselines (with a gain of 3.6 × ). We apply our method to the infectious disease prediction task by using an additional feature set that captures exposure to detected asymptomatic cases and show that our method outperforms all baselines. We further use our method to detect infection sources ("patient zero") of outbreaks that outperform baselines. We also demonstrate that the solutions returned by our approach are clinically meaningful by presenting case studies. [ABSTRACT FROM AUTHOR]

In this paper, we address the line-capacitated minimum Steiner tree problem (the Lc-MStT problem, for short), which is a variant of the (Euclidean) capacitated minimum Steiner tree problem and defined as follows. Given a set X = { r 1 , r 2 , ... , r n } of n terminals in R 2 , a demand function d : X → N and a positive integer C, we are asked to determine the location of a line l and a Steiner tree T l to interconnect these n terminals in X and at least one point located on this line l such that the total demand of terminals in each maximal subtree (of T l ) connected to the line l, where the terminals in such maximal subtree are all located at the same side of this line l, does not exceed the bound C. The objective is to minimize total weight ∑ e ∈ T l w (e) of such a Steiner tree T l among all line-capacitated Steiner trees mentioned-above, where weight w (e) = 0 if two endpoints of that edge e ∈ T l are located on the line l and otherwise weight w(e) is the Euclidean distance between two endpoints of that edge e ∈ T l . In addition, when this line l is as an input in R 2 and ∑ r ∈ X d (r) ≤ C holds, we refer to this version as the 1-line-fixed minimum Steiner tree problem (the 1Lf-MStT problem, for short). We obtain three main results. (1) Given a ρ st -approximation algorithm to solve the Euclidean minimum Steiner tree problem and a ρ 1 L f -approximation algorithm to solve the 1Lf-MStT problem, respectively, we design a (ρ st ρ 1 L f + 2) -approximation algorithm to solve the Lc-MStT problem. (2) Whenever demand of each terminal r ∈ X is less than C 2 , we provide a (ρ 1 L f + 2) -approximation algorithm to resolve the Lc-MStT problem. (3) Whenever demand of each terminal r ∈ X is at least C 2 , using the Edmonds' algorithm to solve the minimum weight perfect matching as a subroutine, we present an exact algorithm in polynomial time to resolve the Lc-MStT problem. [ABSTRACT FROM AUTHOR]

In Lin (Calc. Var. Partial Differential Equations 60:196, 2021), the first author proved the Steiner's projection inequality and the Petty projection inequality for sets of finite perimeter but didn't characterize their cases of equality. In this paper, we characterize the case of equality in the Steiner's projection inequality. Moreover, we give a new proof of the equality case in the Petty projection inequality, which was characterized by Wang (Adv. Math. 230:2457–2473, 2012). [ABSTRACT FROM AUTHOR]

A complete family of functional Steiner formulas is established. As applications, an explicit representation of functional intrinsic volumes using special mixed Monge–Ampère measures and a new version of the Hadwiger theorem on convex functions are obtained. [ABSTRACT FROM AUTHOR]

A partial (n , k , t) λ -system is a pair (X , B) where X is an n-set of vertices and B is a collection of k-subsets of X called blocks such that each t-set of vertices is a subset of at most λ blocks. A sequencing of such a system is a labelling of its vertices with distinct elements of { 0 , ... , n - 1 } . A sequencing is ℓ -block avoiding or, more briefly, ℓ -good if no block is contained in a set of ℓ vertices with consecutive labels. Here we give a short proof that, for fixed k, t and λ , any partial (n , k , t) λ -system has an ℓ -good sequencing for some ℓ = Θ (n 1 / t) as n becomes large. This improves on results of Blackburn and Etzion, and of Stinson and Veitch. Our result is perhaps of most interest in the case k = t + 1 where results of Kostochka, Mubayi and Verstraëte show that the value of ℓ cannot be increased beyond Θ ((n log n) 1 / t) . A special case of our result shows that every partial Steiner triple system (partial (n , 3 , 2) 1 -system) has an ℓ -good sequencing for each positive integer ℓ ⩽ 0.0908 n 1 / 2 . [ABSTRACT FROM AUTHOR]

Let X be a simplicial complex on vertex set V. We say that X is d-representable if it is isomorphic to the nerve of a family of convex sets in R d . We define the d-boxicity of X as the minimal k such that X can be written as the intersection of kd-representable simplicial complexes. This generalizes the notion of boxicity of a graph, defined by Roberts. A missing face of X is a set τ ⊂ V such that τ ∉ X but σ ∈ X for any σ ⊊ τ . We prove that the d-boxicity of a simplicial complex on n vertices without missing faces of dimension larger than d is at most ⌊ n d / (d + 1) ⌋ . The bound is sharp: the d-boxicity of a simplicial complex whose set of missing faces form a Steiner (d , d + 1 , n) -system is exactly n d / (d + 1) . One of the main ingredients in the proof is the following bound on the representability of a complex: let V 1 , ... , V k be subsets of V such that V i ∉ X for all 1 ≤ i ≤ k , and for any missing face τ of X there is some 1 ≤ i ≤ k satisfying | τ \ V i | ≤ 1 . Then, X can be written as an intersection X = ⋂ i = 1 k X i , where, for all 1 ≤ i ≤ k , X i is a (| V i | - 1) -representable complex. In particular, X is (∑ i = 1 k (| V i | - 1)) -representable. [ABSTRACT FROM AUTHOR]

In this paper, we consider the group prize-collecting Steiner tree problem with submodular penalties (GPCST-SP problem). In this problem, we are given an undirected connected graph G = (V , E) with a pre-specified root r and a partition V = { V 0 , V 1 , ... , V k } of V with r ∈ V 0 . Assume c : E → R + is an edge cost function and p : 2 V → R + is a submodular penalty function, where R + is the set of nonnegative real numbers. For a group V i ∈ V , we say it is spanned by a tree if the tree contains at least one vertex of that group. The goal of the GPCST-SP problem is to find an r-rooted tree that minimizes the costs of the edges in the tree plus the penalty cost of the subcollection S containing these groups not spanned by the tree. Our main result is a 2I-approximation algorithm for the problem, where I = max { | V i | ∣ i = 0 , 1 , 2 , ... , k } . [ABSTRACT FROM AUTHOR]

A 3-way (v , k , t) trade T of volume m consists of three pairwise disjoint collections T 1 , T 2 and T 3 , each of m blocks of size k , such that for every t -subset of v -set V , the number of blocks containing this t -subset is the same in each T i for 1 ≤ i ≤ 3 . If any t -subset of found(T ) occurs at most once in each T i for 1 ≤ i ≤ 3 , then T is called 3-way (v , k , t) Steiner trade. We attempt to complete the spectrum S 3 s (v , k) , the set of all possible volume sizes, for 3-way (v , k , 2) Steiner trades, by applying some block designs, such as BIBDs, RBs, GDDs, RGDDs, and r × s packing grid blocks. Previously, we obtained some results about the existence some 3-way (v , k , 2) Steiner trades. In particular, we proved that there exists a 3-way (v , k , 2) Steiner trade of volume m when 12 (k − 1) ≤ m for 15 ≤ k (Rashidi and Soltankhah in Discrete Math. 339(12): 2955–2963, 2016). Now, we show that the claim is correct also for k ≤ 14 . [ABSTRACT FROM AUTHOR]

In this paper, a study on modelling energy harvesting efficiency of a quasi-zero stiffness system is presented. Mechanical characteristics of the system are identified, and the effect of its stiffness and geometry on the function describing energy potential barrier is determined. It has been shown numerically that an increase in equivalent stiffness of the quasi-zero stiffness system limits the potential barrier width. On the other hand, increased the spacing between compensating springs results in increased barrier width. Simulation results of the quasi-zero stiffness system are compared with those obtained for a triple-well system with permanent magnets. Based on mathematical models, multi-color diagrams depicting the largest Lyapunov exponent are plotted. The effect of selected values of external excitation frequency and amplitude on the efficiency of energy harvesting is determined. The rms value of time sequence is taken as a measure of the energy harvesting efficiency. Obtained numerical results are plotted as phase trajectories. [ABSTRACT FROM AUTHOR]

The paper introduces a method for constructing 2-resolvable t-designs for t = 3 , 4 . The main idea is based on the assumption that there exists a partition of a t-design into Steiner 2-designs. A remarkable property of the method is that it enables the construction of 2-resolvable t-designs with a large variety of block sizes. For t = 4 , it is required that the Steiner 2-designs of the partition are projective planes and this case would also lead to a construction of 3-resolvable 5-designs. For instance, we show the existence of an infinite series of 3-resolvable 5-designs having N = 5 resolution classes with parameters 5- (14 + 8 m , 7 , 10 (9 + 8 m) (1 + m)) for any m ≥ 0 as a byproduct. Moreover, it turns out that the method is very effective, as it yields infinitely many 2-resolvable 3-designs. However, the question of simplicity of the constructed designs has not been yet investigated. [ABSTRACT FROM AUTHOR]

Coding theory and combinatorial t-designs have close connections and interesting interplay. One of the major approaches to the construction of combinatorial t-designs is the employment of error-correcting codes. As we all known, some t-designs have been constructed with this approach by using certain linear codes in recent years. However, only a small number of infinite families of cyclic codes holding an infinite family of 3-designs are reported in the literature. The objective of this paper is to study an infinite family of antiprimitive cyclic codes and determine their parameters. By the parameters of these codes and their dual, some infinite family of 3-designs are presented and their parameters are also explicitly determined. In particular, the complements of the supports of the minimum weight codewords in the studied cyclic code form a Steiner system. Furthermore, we show that the infinite family of cyclic codes admit 3-transitive automorphism groups. [ABSTRACT FROM AUTHOR]

Arguably, the most important open problem in the theory of q-analogs of designs is the question regarding the existence of a q-analog D of the Fano plane. As of today, it remains undecided for every single prime power order q of the base field. A point P is called an α -point of D if the derived design of D in P is a geometric spread. In 1996, Simon Thomas has shown that there always exists a non- α -point. For the binary case q = 2 , Olof Heden and Papa Sissokho have improved this result in 2016 by showing that the non- α -points must form a blocking set with respect to the hyperplanes. In this article, we show that a hyperplane consisting only of α -points implies the existence of a partition of the symplectic generalized quadrangle W(q) into spreads. As a consequence, the statement of Heden and Sissokho is generalized to all primes q and all even values of q. [ABSTRACT FROM AUTHOR]

A fundamental barrier in extremal hypergraph theory is the presence of many near-extremal constructions with very different structures. Indeed, the classical constructions due to Kostochka imply that the notorious extremal problem for the tetrahedron exhibits this phenomenon assuming Turán's conjecture. Our main result is to construct a finite family of triple systems ℳ , determine its Turán number, and prove that there are two near-extremal ℳ -free constructions that are far from each other in edit-distance. This is the first extremal result for a hypergraph family that fails to have a corresponding stability theorem. [ABSTRACT FROM AUTHOR]

The current BERT-based question answering systems use a question and a contextual text to find the answer. This causes the systems to return wrong answers or nothing if the text contains irrelevant contents with the input question. Besides, the systems haven't answered yes-no and aggregate questions yet. Besides that, the systems only concentrate on the contents of text regardless of the relationship between entities in the corpus. This systems cannot validate the answer. In this paper, we presented a solution to solve these issues by using the BERT model and the knowledge graph to enhance a question answering system. We combined content-based and linked-based information for knowledge graph representation learning and classified triples into one of three classes such as base class, derived class, or non-existent class. We then used the BERT model to build two classifiers: BERT-based text classification for content information and BERT-based triple classification for link information. The former was able to make a contextual embedding vector for representing triples that were used to classify into the three above classes. The latter generated all path instances from all meta paths of a large heterogeneous information network by running the Motif Search method of Apache Spark on a distributed environment. After creating the path instances, we produced triples from these path instances. We made content-based information by converting triples into natural language text with labels and considered them as a text classification problem. Our proposed solution outperformed other embedding methods with an average accuracy of 92.34% on benchmark datasets and the Motif Finding algorithm with an average executive time improvement of 37% on the distributed environment. [ABSTRACT FROM AUTHOR]

This paper is a continuation of the paper "Bifurcations of Steiner tree topologies in the plane," where topologies of Steiner networks of a fixed binary type are considered. Here bifurcation diagrams of binary types of Steiner minimal networks for four boundary points are constructed and some properties of such diagrams for any number of points are discussed. [ABSTRACT FROM AUTHOR]

Given a bipartite graph with parts A and B having maximum degrees at most Δ A and Δ B , respectively, consider a list assignment such that every vertex in A or B is given a list of colours of size k A or k B , respectively. We prove some general sufficient conditions in terms of Δ A , Δ B , k A , k B to be guaranteed a proper colouring such that each vertex is coloured using only a colour from its list. These are asymptotically nearly sharp in the very asymmetric cases. We establish one sufficient condition in particular, where Δ A = Δ B = Δ , k A = log Δ and k B = (1 + o (1)) Δ / log Δ as Δ → ∞ . This amounts to partial progress towards a conjecture from 1998 of Krivelevich and the first author. We also derive some necessary conditions through an intriguing connection between the complete case and the extremal size of approximate Steiner systems. We show that for complete bipartite graphs these conditions are asymptotically nearly sharp in a large part of the parameter space. This has provoked the following. In the setup above, we conjecture that a proper list colouring is always guaranteed if k A ≥ Δ A ε and k B ≥ Δ B ε for any ε > 0 provided Δ A and Δ B are large enough; if k A ≥ C log Δ B and k B ≥ C log Δ A for some absolute constant C > 1 ; or if Δ A = Δ B = Δ and k B ≥ C (Δ / log Δ) 1 / k A log Δ for some absolute constant C > 0 . These are asymmetric generalisations of the above-mentioned conjecture of Krivelevich and the first author, and if true are close to best possible. Our general sufficient conditions provide partial progress towards these conjectures. [ABSTRACT FROM AUTHOR]

We introduce the concept of local spanners for planar point sets with respect to a family of regions, and prove the existence of local spanners of small size for some families. For a geometric graph G on a point set P and a region R belonging to a family R , we define G ∩ R to be the part of the graph G that is inside R (or is induced by R). A local t-spanner w.r.t R is a geometric graph G on P such that for any region R ∈ R , the graph G ∩ R is a t-spanner for K (P) ∩ R , where K (P) is the complete geometric graph on P. For any set P of n points and any constant ε > 0 , we prove that P admits local (1 + ε) -spanners of sizes O (n log 6 n) and O (n log n) w.r.t axis-parallel squares and vertical slabs, respectively. If adding Steiner points is allowed, then local (1 + ε) -spanners with O(n) edges and O (n log 2 n) edges can be obtained for axis-parallel squares and disks using O(n) Steiner points, respectively. [ABSTRACT FROM AUTHOR]

We study the generalized minimum Manhattan network (GMMN) problem: given a set P of pairs of points in the Euclidean plane R 2 , we are required to find a minimum-length geometric network which consists of axis-aligned segments and contains a shortest path in the L 1 metric (a so-called Manhattan path) for each pair in P . This problem commonly generalizes several NP-hard network design problems that admit constant-factor approximation algorithms, such as the rectilinear Steiner arborescence (RSA) problem, and it is open whether so does the GMMN problem. As a bottom-up exploration, Schnizler (2015) focused on the intersection graphs of the rectangles defined by the pairs in P , and gave a polynomial-time dynamic programming algorithm for the GMMN problem whose input is restricted so that both the treewidth and the maximum degree of its intersection graph are bounded by constants. In this paper, as the first attempt to remove the degree bound, we provide a polynomial-time algorithm for the star case, and extend it to the general tree case based on an improved dynamic programming approach. [ABSTRACT FROM AUTHOR]

Kirkman triple systems (KTSs) are among the most popular combinatorial designs and their existence has been settled a long time ago. Yet, in comparison with Steiner triple systems, little is known about their automorphism groups. In particular, there is no known congruence class representing the orders of a KTS with a number of automorphisms at least close to the number of points. We partially fill this gap by proving that whenever v ≡ 39 (mod 72), or v ≡ 4 e 48 + 3 (mod 4 e 96 ) and e ≥ 0 , there exists a KTS on v points having at least v - 3 automorphisms. This is only one of the consequences of an investigation on the KTSs with an automorphism group G acting sharply transitively on all but three points. Our methods are all constructive and yield KTSs which in many cases inherit some of the automorphisms of G, thus increasing the total number of symmetries. To obtain these results it was necessary to introduce new types of difference families (the doubly disjoint ones) and difference matrices (the splittable ones) which we believe are interesting by themselves. [ABSTRACT FROM AUTHOR]

For an ordering of the blocks of a design, the point sum of an element is the sum of the indices of blocks containing that element. Block labelling for popularity asks for the point sums to be as equal as possible. For Steiner systems of order v and strength t in general, the average point sum is O (v 2 t - 1) ; under various restrictions on block partitions of the Steiner system, the difference between the largest and smallest point sums is shown to be O (v (t + 1) / 2 log v) . Indeed for Steiner triple systems, direct and recursive constructions are given to establish that systems exist with all point sums equal for more than two thirds of the admissible orders. [ABSTRACT FROM AUTHOR]

Given an n-sided polygon P on the plane with n ≥ 4 , a quadrangulation of P is a geometric plane graph such that the boundary of the outer face is P and that each finite face is quadrilateral. Clearly, P is quadrangulatable (i.e., admits a quadrangulation) only if n is even, but there is a non-quadrangulatable even-sided polygon. Ramaswami et al. [Comp Geom 9:257–276, (1998)] proved that every n-sided polygon P with n ≥ 4 even admits a quadrangulation with at most ⌊ n - 2 4 ⌋ Steiner points, where a Steiner point for P is an auxiliary point which can be put in any position in the interior of P. In this paper, introducing the notion of the spirality of P to control a structure of P (independent of n), we estimate the number of Steiner points to quadrangulate P. [ABSTRACT FROM AUTHOR]

The purpose of this article is to further explore how the structure of the affine group can be used to deduce new incidence theorems, and to explore sum-product type applications of these incidence bounds, building on the recent work of Rudnev and Shkredov (On growth rate in S L 2 (F p) , the affine group and sum-product type implications, 2018. arXiv:1812.01671). We bound the energy of several systems of lines, in some cases obtaining a better energy bound than the corresponding bounds in Rudnev and Shkredov by exploiting a connection with collinear quadruples. Our motivation for seeking to generalise and improve the incidence bound from Rudnev and Shkredov comes from possible applications to sum-product problems. For example, we prove that, for any finite A ⊂ R the following superquadratic bound holds: This improves on a bound with exponent 2 that was given in Rudnev and Shkredov. We also give a threshold-beating asymmetric sum-product estimate for sets with small sum set by proving that there exists a positive constant c such that for all finite A , B ⊂ R , [ABSTRACT FROM AUTHOR]

Underwater acoustic sensor networks (UASNs) play an essential role in exploring the marine world applications in rivers, ponds, and oceans. In recent years, prominent developments have addressed and resolved the numerous issues of critical underwater applications. Routing is one of the vital problems discussed widely, and various protocols are designed to solve the routing-related issues effectively. In this paper, we propose reinforcement-learning based routing using Steiner-points to minimize energy consumption and enhance the network lifetime of UASNs. Initially, the sensor nodes form a group of three nodes and calculate the Steiner point for each such group. The isolated nodes and the Steiner points in the network are vertices of the Steiner tree, which is the routing path to be constructed dynamically by the sink node agent to travel with the assistance of AUV. The sink node agent in the unknown environment initiates the Steiner tree construction process by visiting either the isolated neighbor node or neighbor sensor node's Steiner point to collect the data from sensor nodes based on the reward function and the environmental conditions. If agent visits the isolated node, then it collects the data from that node itself. If the agent visits the Steiner point, the agent broadcasts its arrival through the beacon message and intended members of that group communicate to the agent and forwards the sensed data. The agent processes the data to remove the data's redundancy and selects the next point to be visited and constructs the Steiner tree dynamically. The performance evaluation of the proposed scheme minimized each sensor node's energy consumption and enhanced the network's lifetime. [ABSTRACT FROM AUTHOR]

The studies of the topological properties of systems have recently been extended due to a new concept of higher-order topological insulators and superconductors. Many models were proposed for two-dimensional systems on a square lattice, where corner excitations can appear; however, the problem of existence of such excitations in superconducting systems with a triangular crystal lattice is still poorly understood. Using a topological insulator in the form of a triangle with a chiral superconducting order parameter as an example, we shows that corner excitations can exist in C3-symmetric systems. In spite of a nontopological character, these excitations have energies inside the gap of the first-order edge excitation spectrum over a wide parameter range and are well localized at the corners of the system. Gapless corner excitations are shown to exist in the system at certain parameters. The application of a magnetic field in the system plane removes the triple degeneracy of the corner excitation energy and makes it possible to control the position of the minimum-energy corner excitation using a magnetic field. At the same time the fine adjustment to achieve the gapless excitations at the chosen corner can be made with changing of the magnetic field value. [ABSTRACT FROM AUTHOR]

Large sets of combinatorial designs has always been a fascinating topic in design theory. These designs form a partition of the whole space into combinatorial designs with the same parameters. In particular, a large set of block designs, whose blocks are of size k taken from an n-set, is a partition of all the k-subsets of the n-set into disjoint copies of block designs, defined on the n-set, and with the same parameters. The current most intriguing question in this direction is whether large sets of Steiner quadruple systems exist and to provide explicit constructions for those parameters for which they exist. In view of its difficulty no one ever presented an explicit construction even for one nontrivial order. Hence, we seek for related generalizations. As generalizations, to the existence question of large sets, we consider two related questions. The first one is to provide constructions for sets on Steiner systems in which each block (quadruple or a k-subset) is contained in exactly μ systems. The constructions of such systems also yield secure protocols for the generalized Russian cards problem. The second question is to provide constructions for large set of H-designs (mainly for quadruples, but also for larger block size), which have applications in threshold schemes and in quantum jump codes. We prove the existence of such systems for many parameters using orthogonal arrays, perpendicular arrays, ordered designs, sets of permutations, and one-factorizations of the complete graph. [ABSTRACT FROM AUTHOR]

An SQS(v) is said to be doubly resolvable if it has two orthogonal resolutions and denoted by DRSQS(v). In this paper, we give two new constructions, i.e., doubling construction and doubly resolvable MPCQS construction. We also give some new results of doubly resolvable SQS(v). [ABSTRACT FROM AUTHOR]

Mathematical models and the rank optimization method for current Steiner networks are presented in the work. This method is based on the nonlocal minimum condition and on the dynamical decomposition of the current Steiner network in optimized intersecting subnetworks of an equal dimension that follows from it. A computer simulation is presented that shows a sufficient effectiveness of the method in applying it in designing distributive piping networks of water- and gas-supply. [ABSTRACT FROM AUTHOR]

After the departure of Kotzig and Rosa, the leadership of the seminar was assumed by Juraj Bosák, originally a student of Kotzig, later his long-time collaborator, and an active member of the seminar from its very beginnings. Kotzig and Bosák were among the first to present lectures at a graph theory conference (with Kotzig delivering the first talk in 1963, in Smolenice, Slovakia). Many young Slovak mathematicians benefited from these contacts, and had Kotizig and Rosa not left, the development of graph theory in Slovakia at the international level may have been delayed by many years. The Beginning of the Seminar (Early 1960s) The Bratislava graph theory seminar was established through the initiative of the Slovak mathematician Anton Kotzig, who prior to founding the seminar was (among his other activities) the rector of the University of Economics in Bratislava from 1952 to 1958. [Extracted from the article]

The Steiner forest problem asks for a minimum weight forest that spans a given number of terminal sets. We propose new cut- and flow-based integer linear programming formulations for the problem which yield stronger linear programming bounds than the two previous strongest formulations: The directed cut formulation (Balakrishnan et al. in Oper Res 37(5):716–740, 1989; Chopra and Rao in Math Prog 64(1):209–229, 1994) and the advanced flow formulation by Magnanti and Raghavan (Networks 45:61–79, 2005). We further introduce strengthening constraints and provide an example where the integrality gap of our models is 1.5. In an experimental evaluation, we show that the linear programming bounds of the new formulations are indeed strong on practical instances and that the related branch-and-cut algorithm outperforms algorithms based on the previous formulations. [ABSTRACT FROM AUTHOR]

The aim of this paper is to make a connection between design theory and algebraic geometry/commutative algebra. In particular, given any Steiner System S(t, n, v) we associate two ideals, in a suitable polynomial ring, defining a Steiner configuration of points and its Complement. We focus on the latter, studying its homological invariants, such as Hilbert Function and Betti numbers. We also study symbolic and regular powers associated to the ideal defining a Complement of a Steiner configuration of points, finding its Waldschmidt constant, regularity, bounds on its resurgence and asymptotic resurgence. We also compute the parameters of linear codes associated to any Steiner configuration of points and its Complement. [ABSTRACT FROM AUTHOR]

A t- (v , k , λ) design is a pair (X , B) , where X is a v-element set and B is a set of k-subsets of X, called blocks, with the property that every t-subset of X is contained in exactly λ blocks. A t- (v , k , λ) design (X , B) is said to be (s , μ) -resolvable if B can be partitioned into B 1 | ⋯ | B c such that each (X , B i) is an s- (v , k , μ) design, further, if each (X , B i) is also (r , ν) -resolvable, then such an (s , μ) -resolvable t-design is called (s , μ) (r , ν) -doubly resolvable. In 1980, Hartman constructed a (2, 3)(1, 1)-doubly resolvable 3-(v, 4, 1) design for v ∈ { 20 , 32 , 44 , 68 , 80 , 104 } and a (2, 3)-resolvable 3- (2 7 , 4 , 1) design. In this paper, we construct (2, 3)(1, 1)-doubly resolvable 3- (2 2 n + 1 , 4 , 1) designs for all positive integers n. [ABSTRACT FROM AUTHOR]

Storage architectures ranging from minimum bandwidth regenerating encoded distributed storage systems to declustered-parity RAIDs can employ dense partial Steiner systems to support fast reads, writes, and recovery of failed storage units. To enhance performance, popularities of the data items should be taken into account to make frequencies of accesses to storage units as uniform as possible. A combinatorial model ranks items by popularity and assigns data items to elements in a dense partial Steiner system so that the sums of ranks of the elements in each block are as equal as possible. By developing necessary conditions in terms of independent sets, we demonstrate that certain Steiner systems must have a much larger difference between the largest and smallest block sums than is dictated by an elementary lower bound. In contrast, we also show that certain dense partial S (t , t + 1 , v) designs can be labeled to realize the elementary lower bound. Furthermore, we prove that for every admissible order v, there is a Steiner triple system (S(2, 3, v)) whose largest difference in block sums is within an additive constant of the lower bound. [ABSTRACT FROM AUTHOR]

In a recent work, Jungnickel, Magliveras, Tonchev, and Wassermann derived an overexponential lower bound on the number of nonisomorphic resolvable Steiner triple systems (STS) of order v, where v = 3 k , and 3-rank v - k . We develop an approach to generalize this bound and estimate the number of isomorphism classes of resolvable STS (v) of 3-rank v - k - 1 for an arbitrary v of form 3 k T , where T is congruent to 1 or 3 modulo 6. [ABSTRACT FROM AUTHOR]

A famous theorem of Kirkman says that there exists a Steiner triple system of order n if and only if n ≡ 1,3 mod 6. In 1973, Erdős conjectured that one can find so-called 'sparse' Steiner triple systems. Roughly speaking, the aim is to have at most j−3 triples on every set of j points, which would be best possible. (Triple systems with this sparseness property are also referred to as having high girth.) We prove this conjecture asymptotically by analysing a natural generalization of the triangle removal process. Our result also solves a problem posed by Lefmann, Phelps and Rödl as well as Ellis and Linial in a strong form, and answers a question of Krivelevich, Kwan, Loh and Sudakov. Moreover, we pose a conjecture which would generalize the Erdős conjecture to Steiner systems with arbitrary parameters and provide some evidence for this. [ABSTRACT FROM AUTHOR]