Search

A triple system is cancellative if it does not contain three distinct sets A , B , C such that the symmetric difference of A and B is contained in C. We show that every cancellative triple system H that satisfies a particular inequality between the sizes of H and its shadow must be structurally close to the balanced blowup of some Steiner triple system. Our result contains a stability theorem for cancellative triple systems due to Keevash and Mubayi as a special case. It also implies that the boundary of the feasible region of cancellative triple systems has infinitely many local maxima, thus giving the first example showing this phenomenon. [ABSTRACT FROM AUTHOR]

This paper lies in the context of the studies of eigenfunctions of graphs having minimum cardinality of support. One of the tools is the weight‐distribution bound, a lower bound on the cardinality of support of an eigenfunction of a distance‐regular graph corresponding to a nonprincipal eigenvalue. The tightness of the weight‐distribution bound was previously shown in general for the smallest eigenvalue of a Grassmann graph. However, a characterisation of optimal eigenfunctions was not obtained. Motivated by this open problem, we consider the class of strongly regular Grassmann graphs and give the required characterisation in this case. We then show the tightness of the weight‐distribution bound for block graphs of affine designs (defined on the lines of an affine space with two lines being adjacent when intersect) and obtain a similar characterisation of optimal eigenfunctions. [ABSTRACT FROM AUTHOR]

We propose a heuristic method of using network centralities for constructing small-weight Steiner trees in this paper. The Steiner tree problem in graphs is one of the practical NP-hard combinatorial optimization problems. Given a graph and a set of vertices called terminals in the graph, the objective of the Steiner tree problem in graphs is to find a minimum weight Steiner tree that is a tree containing all the terminals. Conventional construction methods make a Steiner tree based on the shortest paths between terminals. If these shortest paths are overlapped as much as possible, we can obtain a small-weight Steiner tree. Therefore, we proposed to use network centralities to distinguish which edges should be included to make a small-weight Steiner tree. Experimental results revealed that using the vertex or the edge betweenness centralities contributes to making small-weight Steiner trees. [ABSTRACT FROM AUTHOR]

We prove that the set of |$n$| -point configurations for which the solution to the planar Steiner problem is not unique has the Hausdorff dimension at most |$2n-1$| (as a subset of |$\mathbb{R}^{2n}$|⁠). Moreover, we show that the Hausdorff dimension of the set of |$n$| -point configurations for which at least two locally minimal trees have the same length is also at most |$2n-1$|⁠. The methods we use essentially rely upon the theory of subanalytic sets developed in [ 1 ]. Motivated by this approach, we develop a general setup for the similar problem of uniqueness of the Steiner tree where the Euclidean plane is replaced by an arbitrary analytic Riemannian manifold |$M$|⁠. In this setup, we argue that the set of configurations possessing two locally-minimal trees of the same length either has dimension equal to |$n \dim M - 1$| or has a non-empty interior. We provide an example of a two-dimensional surface for which the last alternative holds. In addition to the above-mentioned results, we study the set of |$n$| -point configurations for which there is a unique solution to the Steiner problem in |$\mathbb{R}^{d}$|⁠. We show that this set is path-connected. [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 celebrated theorem of Pippenger, and Frankl and Rödl states that every almost‐regular, uniform hypergraph H$\mathcal {H}$ with small maximum codegree has an almost‐perfect matching. We extend this result by obtaining a conflict‐free matching, where conflicts are encoded via a collection C$\mathcal {C}$ of subsets C⊆E(H)$C\subseteq E(\mathcal {H})$. We say that a matching M⊆E(H)$\mathcal {M}\subseteq E(\mathcal {H})$ is conflict‐free if M$\mathcal {M}$ does not contain an element of C$\mathcal {C}$ as a subset. Under natural assumptions on C$\mathcal {C}$, we prove that H$\mathcal {H}$ has a conflict‐free, almost‐perfect matching. This has many applications, one of which yields new asymptotic results for so‐called 'high‐girth' Steiner systems. Our main tool is a random greedy algorithm which we call the 'conflict‐free matching process'. [ABSTRACT FROM AUTHOR]

We generalize Atsuyama's result on the geometry of symmetric spaces of type EVI to the case of fields of characteristic zero. We relate the possible mutual positions of two points with the classification of balanced symplectic ternary algebras (also known as Freudenthal triple systems). [ABSTRACT FROM AUTHOR]

The Steiner (k , k ′) -eccentricity of a given k ′ -subset of a graph G is the maximum Steiner distance over all k -subsets of V (G) which contain the given k ′ -subset, an extension of standard Steiner k -eccentricity. In this paper, we mainly study the Steiner (3 , 2) -eccentricity of trees. The σ -transformation which does not increase the average Steiner (3 , 2) -eccentricity is depicted. Using σ -transformation, several lower and upper bounds for the average Steiner (3 , 2) -eccentricity of trees are given. [ABSTRACT FROM AUTHOR]

In 1991, Shalaby conjectured that any Zn, where n≡1 or 3(mod8),n≥11, admits a strong Skolem starter. In 2018, the authors fully described and explicitly constructed the infinite "cardioidal" family of strong Skolem starters. No other infinite family of these combinatorial designs was known to date. Statements regarding the products of starters, proven in this paper give a new way of generating strong or skew Skolem starters of composite orders. This approach extends our previous result by generating new infinite families of these starters that are not cardioidal. [ABSTRACT FROM AUTHOR]

Let V $V$ be a vector space over the finite field Fq ${{\mathbb{F}}}_{q}$. A q $q$‐Steiner system, or an S(t,k,V)q $S{(t,k,V)}_{q}$, is a collection ℬ ${\rm{{\mathcal B}}}$ of k $k$‐dimensional subspaces of V $V$ such that every t $t$‐dimensional subspace of V $V$ is contained in a unique element of ℬ ${\rm{{\mathcal B}}}$. A large set of q $q$‐Steiner systems, or an LS(t,k,V)q $LS{(t,k,V)}_{q}$, is a partition of the k $k$‐dimensional subspaces of V $V$ into S(t,k,V)q $S{(t,k,V)}_{q}$ systems. In the case that V $V$ has infinite dimension, the existence of an LS(t,k,V)q $LS{(t,k,V)}_{q}$ for all finite t,k $t,k$ with 1

In this paper, we prove that there is no block-transitive 4-(v, k, 1) designs and 6-(v, k, 1) designs with k divides v. [ABSTRACT FROM AUTHOR]

We abstract and study reachability preservers, a graph-theoretic primitive that has been implicit in prior work on network design. Given a directed graph G=(V,E) and a set of demand pairs P⊆VxV, a reachability preserver is a sparse subgraph H that preserves reachability between all demand pairs. Our first contribution is a series of extremal bounds on the size of reachability preservers. Our main result states that, for an n-node graph and demand pairs of the form P⊆SxV for a small node subset S, there is always a reachability preserver on O(n+√n/P//S/) edges. We additionally give a lower bound construction demonstrating that this upper bound characterizes the settings in which O(n) size reachability preservers are generally possible, in a large range of parameters. The second contribution of this paper is a new connection between extremal graph sparsification results and classical Steiner Network Design problems. Surprisingly, prior to this work, the osmosis of techniques between these two fields had been superficial. This allows us to improve the state of the art approximation algorithms for the most basic Steiner-type problem in directed graphs from the O(n0.6+ε) of Chlamatac, et al. [Approximating spanners and directed steiner forest: Upper and lower bounds, in Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, Philadelphia, 2017, pp. 534-443] (n4/7+ε). [ABSTRACT FROM AUTHOR]

In this paper, we proved that each nonlinear non-global semi-Jordan triple higher derivable mapping on a 2-torsion free triangular algebra is an additive higher derivation. As its application, we get the similar conclusion on a nest algebra or a 2-torsion free block upper triangular matrix algebra, respectively. [ABSTRACT FROM AUTHOR]

For an integer k ≥ 2 , let (P n (k)) n be the k-generalized Pell sequence which starts with 0 , ... , 0 , 1 (k terms), and each term afterwards is given by P n (k) = 2 P n − 1 (k) + P n − 2 (k) + ⋯ + P n − k (k) . In this paper, we determine all solutions of the Markov equation x 2 + y 2 + z 2 = 3 x y z , with x, y, and z being k-generalized Pell numbers. This paper continues and extends a previous work of Kafle, Srinivasan and Togbé, who found all Markov triples with Pell components. [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]

The Turán number T(n,5,3) $T(n,5,3)$ is the minimum size of a system of triples out of a base set X $X$ of n $n$ elements such that every quintuple in X $X$ contains a triple from the system. The exact values of T(n,5,3) $T(n,5,3)$ are known for n≤17 $n\le 17$. Turán conjectured that T(2m,5,3)=2m3 $T(2m,5,3)=2\left(\genfrac{}{}{0.0pt}{}{m}{3}\right)$, and no counterexamples have been found so far. If this conjecture is true, then T(2m+1,5,3)≥⌈m(m−2)(2m+1)∕6⌉ $T(2m+1,5,3)\ge \lceil m(m-2)(2m+1)\unicode{x02215}6\rceil $. We prove the matching upper bound for all n=2m+1>17 $n=2m+1\gt 17$ except n=27 $n=27$. [ABSTRACT FROM AUTHOR]

Let H$H$ be a k$k$‐uniform D$D$‐regular simple hypergraph on N$N$ vertices. Based on an analysis of the Rödl nibble, in 1997, Alon, Kim and Spencer proved that if k⩾3$k \geqslant 3$, then H$H$ contains a matching covering all but at most ND−1/(k−1)+o(1)$ND^{-1/(k-1)+o(1)}$ vertices, and asked whether this bound is tight. In this paper we improve their bound by showing that for all k>3$k > 3$, H$H$ contains a matching covering all but at most ND−1/(k−1)−η$ND^{-1/(k-1)-\eta }$ vertices for some η=Θ(k−3)>0$\eta = \Theta (k^{-3}) > 0$, when N$N$ and D$D$ are sufficiently large. Our approach consists of showing that the Rödl nibble process not only constructs a large matching but it also produces many well‐distributed 'augmenting stars' which can then be used to significantly improve the matching constructed by the Rödl nibble process. Based on this, we also improve the results of Kostochka and Rödl from 1998 and Vu from 2000 on the size of matchings in almost regular hypergraphs with small codegree. As a consequence, we improve the best known bounds on the size of large matchings in combinatorial designs with general parameters. Finally, we improve the bounds of Molloy and Reed from 2000 on the chromatic index of hypergraphs with small codegree (which can be applied to improve the best known bounds on the chromatic index of Steiner triple systems and more general designs). [ABSTRACT FROM AUTHOR]

Conformational polymorphs of organic molecular crystals represent a challenging test for quantum chemistry because they require careful balancing of the intra- and intermolecular interactions. This study examines 54 molecular conformations from 20 sets of conformational polymorphs, along with the relative lattice energies and 173 dimer interactions taken from six of the polymorph sets. These systems are studied with a variety of van der Waals-inclusive density functionals theory models; dispersion-corrected spin-component-scaled second-order Møller–Plesset perturbation theory (SCS-MP2D); and domain local pair natural orbital coupled cluster singles, doubles, and perturbative triples [DLPNO-CCSD(T)]. We investigate how delocalization error in conventional density functionals impacts monomer conformational energies, systematic errors in the intermolecular interactions, and the nature of error cancellation that occurs in the overall crystal. The density functionals B86bPBE-XDM, PBE-D4, PBE-MBD, PBE0-D4, and PBE0-MBD are found to exhibit sizable one-body and two-body errors vs DLPNO-CCSD(T) benchmarks, and the level of success in predicting the relative polymorph energies relies heavily on error cancellation between different types of intermolecular interactions or between intra- and intermolecular interactions. The SCS-MP2D and, to a lesser extent, ωB97M-V models exhibit smaller errors and rely less on error cancellation. Implications for crystal structure prediction of flexible compounds are discussed. Finally, the one-body and two-body DLPNO-CCSD(T) energies taken from these conformational polymorphs establish the CP1b and CP2b benchmark datasets that could be useful for testing quantum chemistry models in challenging real-world systems with complex interplay between intra- and intermolecular interactions, a number of which are significantly impacted by delocalization error. [ABSTRACT FROM AUTHOR]

For a connected graph G of order p and a set S ⊆ V (G) , the Steiner distance of S is the minimum number of edges in a connected subgraph of G containing S. If n is an integer, 2 ≤ n ≤ p and a vertex v ∈ V (G) , the Steiner n -eccentricity of a vertex v of G , ex n (v) , is the maximum Steiner distance of all n -subsets of V (G) containing v. The Steiner n -radius of G , rad n (G) , is the minimum Steiner n -eccentricities of all vertices in G. We give bounds on rad n (G) in terms of the order of G and the minimum degree of G for all graphs and for graphs that contain no triangles. We shall also investigate the relation between the n -radius of a graph G and its complement Ḡ. [ABSTRACT FROM AUTHOR]

We show that the base polytope PM of any paving matroid M can be systematically obtained from a hypersimplex by slicing off certain subpolytopes, namely base polytopes of lattice path matroids corresponding to panhandle-shaped Ferrers diagrams. We calculate the Ehrhart polynomials of these matroids and consequently write down the Ehrhart polynomial of PM, starting with Katzman's formula for the Ehrhart polynomial of a hypersimplex. The method builds on and generalizes Ferroni's work on sparse paving matroids. Combinatorially, our construction corresponds to constructing a uniform matroid from a paving matroid by iterating the operation of stressed-hyperplane relaxation introduced by Ferroni, Nasr and Vecchi, which generalizes the standard matroid-theoretic notion of circuit-hyperplane relaxation. We present evidence that panhandle matroids are Ehrhart positive and describe a conjectured combinatorial formula involving chain forests and Eulerian numbers from which Ehrhart positivity of panhandle matroids will follow. As an application of the main result, we calculate the Ehrhart polynomials of matroids associated with Steiner systems and finite projective planes, and show that they depend only on their design-theoretic parameters: for example, while projective planes of the same order need not have isomorphic matroids, their base polytopes must be Ehrhart equivalent. [ABSTRACT FROM AUTHOR]

Steiner triple systems (STSs) have been classified up to order 19. Earlier estimations of the number of isomorphism classes of STSs of order 21, the smallest open case, are discouraging as for classification, so it is natural to focus on the easier problem of merely counting the isomorphism classes. Computational approaches for counting STSs are here considered and lead to an algorithm that is used to obtain the number of isomorphism classes for order 21: 14,796,207,517,873,771. [ABSTRACT FROM AUTHOR]

We prove that for n \in \mathbb N and an absolute constant C, if p \geq C\log ^2 n / n and L_{i,j} \subseteq [n] is a random subset of [n] where each k\in [n] is included in L_{i,j} independently with probability p for each i, j\in [n], then asymptotically almost surely there is an order-n Latin square in which the entry in the ith row and jth column lies in L_{i,j}. The problem of determining the threshold probability for the existence of an order-n Latin square was raised independently by Johansson [ Triangle factors in random graphs , 2006], by Luria and Simkin [Random Structures Algorithms 55 (2019), pp. 926–949], and by Casselgren and Häggkvist [Graphs Combin. 32 (2016), pp. 533–542]; our result provides an upper bound which is tight up to a factor of \log n and strengthens the bound recently obtained by Sah, Sawhney, and Simkin [ Threshold for Steiner triple systems , arXiv: 2204.03964 , 2022]. We also prove analogous results for Steiner triple systems and 1-factorizations of complete graphs, and moreover, we show that each of these thresholds is at most the threshold for the existence of a 1-factorization of a nearly complete regular bipartite graph. [ABSTRACT FROM AUTHOR]

A line coloring of PG(n,q) $\text{PG}(n,q)$, the n $n$‐dimensional projective space over GF(q) $(q)$, is an assignment of colors to all lines of PG(n,q) $\text{PG}(n,q)$ so that any two lines with the same color do not intersect. The chromatic index of PG(n,q) $\text{PG}(n,q)$, denoted by χ′(PG(n,q)) $\chi ^{\prime} (\text{PG}(n,q))$, is the least number of colors for which a coloring of PG(n,q) $\text{PG}(n,q)$ exists. This paper translates the problem of determining the chromatic index of PG(n,q) $\text{PG}(n,q)$ to the problem of examining the existences of PG(3,q) $\text{PG}(3,q)$ and PG(4,q) $\text{PG}(4,q)$ with certain properties. In particular, it is shown that for any odd integer n $n$ and q∈{3,4,8,16},χ′(PG(n,q))=(qn−1)∕(q−1) $q\in \{3,4,8,16\},\chi ^{\prime} (\text{PG}(n,q))=({q}^{n}-1)\unicode{x02215}(q-1)$, which implies the existence of a parallelism of PG(n,q) $\text{PG}(n,q)$ for any odd integer n $n$ and q∈{3,4,8,16} $q\in \{3,4,8,16\}$. [ABSTRACT FROM AUTHOR]

For a connected graph G of order p and a non-empty subset S of the vertex set of G, the n-Steiner distance of S is defined to be the smallest size among all connected sub-graphs whose vertex sets contain. In this paper, we obtain the Hosoya polynomials of Steiner n-distance of some windmill graphs. Moreover, the Steiner Wiener indices of certain windmill graphs are also obtained. [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]

Recently Chase determined the maximum possible number of cliques of size t in a graph on n vertices with given maximum degree. Soon afterward, Chakraborti and Chen answered the version of this question in which we ask that the graph have m edges and fixed maximum degree (without imposing any constraint on the number of vertices). In this paper we address these problems on hypergraphs. For s-graphs with s\geq 3 a number of issues arise that do not appear in the graph case. For instance, for general s-graphs we can assign degrees to any i-subset of the vertex set with 1≤ i ≤ s 1. We establish bounds on the number of t-cliques in an s-graph H with i-degree bounded by Δ in three contexts: H has n vertices; H has m (hyper)edges; and (generalizing the previous case) H has a fixed number p of u-cliques for some u with s≤ u≤ t. When Δ is of a special form we characterize the extremal s-graphs and prove that the bounds are tight. These extremal examples are the shadows of either Steiner systems or partial Steiner systems. On the way to proving our uniqueness results, we extend results of Füredi and Griggs on uniqueness in Kruskal--Katona from the shadow case to the clique case. [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]

We consider a general metric Steiner problem, which involves finding a set S with the minimal length, such that S ∪ A is connected, where A is a given compact subset of a given complete metric space X; a solution is called the Steiner tree. Paolini, Stepanov, and Teplitskaya in 2015 provided an example of a planar Steiner tree with an infinite number of branching points connecting an uncountable set of points. We prove that such a set can have a positive Hausdorff dimension, which was an open question (the corresponding tree exhibits self-similar fractal properties). [ABSTRACT FROM AUTHOR]

The basic goal of survivable network design is to build a cheap network that maintains the connectivity between given sets of nodes despite the failure of a few edges/nodes. The connectivity augmentation problem (CAP) is arguably one of the most basic problems in this area: given a k(-edge)-connected graph G and a set of extra edges (links), select a minimum cardinality subset A of links such that adding A to G increases its edge connectivity to k+1. Intuitively, one wants to make an existing network more reliable by augmenting it with extra edges. The best known approximation factor for this NP-hard problem is 2, and this can be achieved with multiple approaches (the first such result is in [G. N. Frederickson and J\'aj\'a, SIAM J. Comput., 10 (1981), pp. 270--283]. It is known [E. A. Dinitz, A. V. Karzanov, and M. V. Lomonosov, Studies in Discrete Optimization, Nauka, Moscow, 1976, pp. 290--306] that CAP can be reduced to the case k = 1, also known as the tree augmentation problem (TAP) for odd k, and to the case k = 2, also known as the cactus augmentation problem (CacAP) for even k. Prior to the conference version of this paper [J. Byrka, F. Grandoni, and A. Jabal Ameli, STOC'20, ACM, New York, 2020, pp. 815--825], several better than 2 approximation algorithms were known for TAP, culminating with a recent 1.458 approximation [F. Grandoni, C. Kalaitzis, and R. Zenklusen, STOC'18, ACM, New York, 1918, pp. 632--645]. However, for CacAP the best known approximation was 2. In this paper we breach the 2 approximation barrier for CacAP, hence, for CAP, by presenting a polynomial-time 2 ln(4) 967 1120 + \varepsilon < 1.91 approximation. From a technical point of view, our approach deviates quite substantially from previous work. In particular, the better-than-2 approximation algorithms for TAP either exploit greedy-style algorithms or are based on rounding carefully designed LPs. We instead use a reduction to the Steiner tree problem which was previously used in parameterized algorithms [Basavaraju et al., ICALP'14, Springer, Berlin, 2014, pp. 800--811]. This reduction is not approximation preserving, and using the current best approximation factor for a Steiner tree [Byrka et al., J. ACM, 60 (2013), 6] as a black box would not be good enough to improve on 2. To achieve the latter goal, we "open the box" and exploit the specific properties of the instances of a Steiner tree arising from CacAP. In our opinion this connection between approximation algorithms for survivable network design and Steiner-type problems is interesting, and might lead to other results in the area. [ABSTRACT FROM AUTHOR]

Suppose a committee consisting of three members is tasked with matching n candidates to n different positions. However, all of the committee members disagree on the job placement for every candidate, i.e., every candidate is matched to three different positions according to three committee members. All three committee members are competitive and want to push through as many of their placements as possible. Can they find a compromise which allows each committee member to be responsible for a third of all the candidate placements? In this paper we will consider an asymptotic version of this question and several other variants of a similar problem. As an application we will consider an embedding question--which hypertrees does a large Steiner system always contain?. [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]

We prove a universal property for ∞-categories of spans in the generality of Barwick's adequate triples, explicitly describe the cocartesian fibration corresponding to the span functor, and show that the latter restricts to a selfequivalence on the class of orthogonal adequate triples, which we introduce for this purpose. As applications of the machinery we develop, we give a quick proof of Barwick's unfurling theorem, show that an orthogonal factorisation system arises from a cartesian fibration if and only if it forms an adequate triple (generalising work of Lanari), extend the description of dual (co)cartesian fibrations by Barwick, Glasman and Nardin to two-variable fibrations, explicitly describe parametrised adjoints (extending work of Torii), identify the orthofibration classifying the mapping category functor of an (∞, 2)-category (building on work of Abellán García and Stern), formally identify the unstraightenings of the identity functor on the8-category of8-categories with the (op)lax under-categories of a point, and deduce a certain naturality property of the Yoneda embedding (answering a question of Clausen). [ABSTRACT FROM AUTHOR]

Let T be a tree with vertex set V (T) = { 1 , 2 , ... , n }. The Steiner distance of a subset S ⊆ V (T) of vertices of T is defined to be the number of edges in a smallest connected subtree of T that contains all the vertices of S. The k -Steiner distance matrix D k (T) of T is the ( n k ) × ( n k ) matrix whose rows and columns are indexed by subsets of vertices of size k. The entry in the row indexed by P and column indexed by Q is equal to Steiner distance of P ∪ Q. We consider the case when k = 2 and show that rank (D 2 (T)) = 2 n − p − 1 where p is the number of pendant vertices (or leaves) in T. We construct a basis B for the row space of D 2 (T) and obtain a formula for the inverse of the nonsingular square submatrix D = D 2 (T) [ B , B ]. We also compute the determinant of D and show that its absolute value is independent of the structure of T and apply it to obtain the inertia of D 2 (T). Lastly, we determine the spectrum of 2-Steiner distance matrix of the star tree. [ABSTRACT FROM AUTHOR]

This paper revisits a combinatorial structure called the large set of ordered design ( L O D ). Among others, we introduce a novel structure called Latin matching and prove that a Latin matching of order n leads to an L O D (n − 1 ,   n ,   2 n − 1) ; thus, we obtain constructions for L O D (1 ,   2 ,   3) , L O D (2 ,   3 ,   5) , and L O D (4 ,   5 ,   9) . Moreover, we show that constructing a Latin matching of order n is at least as hard as constructing a Steiner system S (n − 2 ,   n − 1 ,   2 n − 2) ; therefore, the order of a Latin matching must be prime. We also show some applications in multiagent systems. [ABSTRACT FROM AUTHOR]

One way to study the combinatorics of finite metric spaces is to study the betweenness relation associated with the metric space. In the hypergraph metrization problem, one has to find and characterize metric betweennesses with collinear triples (or alternatively, non-degenerate triangles) that coincide with the edges of a given 3-uniform hypergraph. Metrizability of different kinds of hypergraphs was investigated in the last decades. Chen showed that Steiner triple systems are not metric, while Richmond and Richmond characterized linear betweennesses, i.e. metric betweennesses that realize the complete 3-uniform hypergraph. The latter result was also generalized to pseudometric (almost-metric) betweennesses by Beaudou et al. In this paper, we further extend this theory by characterizing the largest non-linear almost-metric betweennesses that satisfy certain hereditary properties, as well as the ones that contain a small linear number of non-degenerate triangles. [ABSTRACT FROM AUTHOR]

A set of geometric graphs is geometric-packable if it can be asymptotically packed into every sequence of drawings of the complete graph K n. For example, the set of geometric triangles is geometric-packable due to the existence of Steiner Triple Systems. When G is the 4-cycle (or 4-cycle with a chord), we show that the set of plane drawings of G is geometric-packable. In contrast, the analogous statement is false when G is nearly any other planar Hamiltonian graph (with at most 3 possible exceptions). A convex geometric graph is convex-packable if it can be asymptotically packed into the convex drawings of the complete graphs. For each planar Hamiltonian graph G , we determine whether or not a plane G is convex-packable. Many of our proofs explicitly construct these packings; in these cases, the packings exhibit a symmetry that mirrors the vertex transitivity of K n. [ABSTRACT FROM AUTHOR]

The coloring of hypergraph and its special case Steiner triple systems, STS(v), is studied extensively. But the defining set of the coloring of hypergraph even its special case STS(v), has not been explored yet. We study minimum defining set and the largest minimal defining set for 3-coloring of STS(v). We determined minimum defining set and the largest minimal defining set, for all non-isomorphic STS(v), v £ 15. Also we have found the defining number for all Steiner triple systems of order v, and some lower bounds for the size of the largest minimal defining set for all Steiner triple systems of order v, for each admissible v. [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]

With each Steiner triple system there is associated a one-parameter family of commutative, nonassociative, nonunital algebras that are by construction exact, meaning that the trace of every multiplication operator vanishes, and these algebras are shown to be Killing metrized, meaning the Killing type trace-form is nondegenerate and invariant (Frobenius), and simple, except for certain parameter values. The definition of these algebras resembles that of the Matsuo algebra of the Steiner triple system, but they are different. For a Hall triple system, the associated algebra is a primitive axial algebra for a Z / 2 Z -graded fusion law. [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]

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]

A graph profile records all possible densities of a fixed finite set of graphs. Profiles can be extremely complicated; for instance the full profile of any triple of connected graphs is not known, and little is known about hypergraph profiles. We introduce the tropicalization of graph and hypergraph profiles. Tropicalization is a well-studied operation in algebraic geometry, which replaces a variety (the set of real or complex solutions to a finite set of algebraic equations) with its "combinatorial shadow". We prove that the tropicalization of a graph profile is a closed convex cone, which still captures interesting combinatorial information. We explicitly compute these tropicalizations for arbitrary sets of complete and star hypergraphs. We show they are rational polyhedral cones even though the corresponding profiles are not even known to be semialgebraic in some of these cases. We then use tropicalization to prove strong restrictions on the power of the sums of squares method, equivalently Cauchy-Schwarz calculus, to test (which is weaker than certification) the validity of graph density inequalities. In particular, we show that sums of squares cannot test simple binomial graph density inequalities, or even their approximations. Small concrete examples of such inequalities are presented, and include the famous Blakley-Roy inequalities for paths of odd length. As a consequence, these simple inequalities cannot be written as a rational sum of squares of graph densities. [ABSTRACT FROM AUTHOR]

A commuting triple of Hilbert space operators (A , B , P) , for which the closed tetrablock 피 ¯ is a spectral set, is called a tetrablock-contraction or simply an 피 -contraction, where 피 = { (x 1 , x 2 , x 3) ∈ ℂ 3 : 1 - x 1 ⁢ z - x 2 ⁢ w + x 3 ⁢ z ⁢ w ≠ 0 ⁢ whenever ⁢ | z | ≤ 1 ⁢ and ⁢ | w | ≤ 1 } ⊂ ℂ 3 , is a polynomially convex domain which is naturally associated with the μ-synthesis problem. By applications of the theory of 피 -contractions, we obtain the following main results in this article: (i) It is well known that any number of doubly commuting isometries admit a Wold-type decomposition. Also, examples from the literature show that such decomposition does not hold in general for commuting isometries. We generalize this result to any number of doubly commuting contractions. Indeed, we present a canonical decomposition to any family of doubly commuting contractions 풰 = { T λ : λ ∈ Λ } acting on a Hilbert space ℋ and show that ℋ continues to decompose orthogonally into joint reducing subspaces of 풰 until all members of 풰 split together into unitaries and completely non-unitary (c.n.u.) contractions. Naturally, as a special case we achieve an analogous Wold decomposition for any number of doubly commuting isometries. (ii) Further, we show that a similar canonical decomposition is possible for any family of doubly commuting c.n.u. contractions, where all members jointly orthogonally decompose into pure isometries (i.e. unilateral shifts) and completely non-isometry (c.n.i.) contractions. (iii) We give an alternative proof to the canonical decomposition of an 피 -contraction and apply that to establish independently the following result due to Eschmeier: for any finitely many commuting contractions T 1 , ... , T n acting on a Hilbert space ℋ , the space ℋ admits an orthogonal decomposition ℋ = ℋ 1 ⊕ ℋ 2 , where ℋ 1 is the maximal common reducing subspace for T 1 , ... , T n such that T 1 | ℋ 1 , ... , T n | ℋ 1 are unitaries. [ABSTRACT FROM AUTHOR]

In 1971, Doyen and Vandensavel gave a special doubling construction that gives a direct construction of 2‐chromatic Steiner quadruple system of order v $v$ (SQS(v) $(v)$) for all v≡4 $v\equiv 4$ or 8(mod12) $8\,(\mathrm{mod}\,12)$. The first author presented a construction for 2‐chromatic SQSs based on 2‐chromatic candelabra quadruple systems and s $s$‐fan designs. In this paper, it is proved that a 2‐chromatic SQS(v) $(v)$ also exists if v≡10(mod12) $v\equiv 10\,(\mathrm{mod}\,12)$, or if v≡2(mod24) $v\equiv 2\,(\mathrm{mod}\,24)$. [ABSTRACT FROM AUTHOR]

Let S be a set of vertices of a connected graph G. The Steiner distance of S is the minimum size among all connected subgraphs of G containing the vertices of S. The sum of all Steiner distances on sets of size k is called the Steiner k-Wiener index. We obtain formulae for bounds on the Steiner–Wiener index of graphs in terms of chromatic number, vertex connectivity and independence number. Also, we obtain bounds for 4-cycle free graphs. [ABSTRACT FROM AUTHOR]

Set-optimization has attracted increasing interest in the last years, as for instance uncertain multiobjective optimization problems lead to such problems with a set-valued objective function. Thereby, from a practical point of view, most of all the so-called set approach is of interest. However, optimality conditions for these problems, for instance using directional derivatives, are still very limited. The key aspect for a useful directional derivative is the definition of a useful set difference for the evaluation of the numerator in the difference quotient. We present here a new set difference which avoids the use of a convex hull and which applies to arbitrary convex sets, and not to strictly convex sets only. The new set difference is based on the new concept of generalized Steiner sets. We introduce the Banach space of generalized Steiner sets as well as an embedding of convex sets in this space using Steiner points. In this Banach space we can easily define a difference and a directional derivative. We use the latter for new optimality conditions for set optimization. Numerical examples illustrate the new concepts. [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]

A Kirkman triple system of order v, KTS(v), is a resolvable Steiner triple system on v elements. In this paper, we investigate an open problem posed by Doug Stinson, namely the existence of KTS(v) which contain as a subdesign a Steiner triple system of order u, an STS(u). We present several different constructions for designs of this form. As a consequence, we completely settle the extremal case v=2u+1, for which a list of possible exceptions had remained for close to 30 years. Our new constructions also provide the first infinite classes for the more general problem. We reduce the other maximal case v=2u+3 to (at present) three possible exceptions. In addition, we obtain results for other cases of the form v=2u+w and also near v=3u. Our primary method introduces a new type of Kirkman frame which contains group divisible design subsystems. These subsystems can occur with different configurations, and we use two different varieties in our constructions. [ABSTRACT FROM AUTHOR]