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]

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]

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]

This work firstly studies the Steiner tree problem with bounded edge-length d in which d is the ratio of the maximum edge cost to the minimum edge cost. This work analyzes the algorithm of Byrka et al. [19] and shows that the approximation ratio of d ln ⁡ 4 d + ln ⁡ 4 − 1 + ϵ for general graphs and approximation ratio of 73 ⋅ d 60 ⋅ d + 13 + ϵ for quasi-bipartite graphs. The algorithm implies approximation ratio of 1.162 + ϵ for the problem on complete graphs with edge distances 1 and 2. This finding represents an improvement upon the previous best approximation ratio of 1.25. This work then presents a combinatorial two-phase heuristic for the general Steiner tree in greedy strategy that achieves an approximation ratio of 1.4295. [ABSTRACT FROM AUTHOR]

Given a subgroup H of a group (G , +) , a (G , H , k , 1) difference family (DF) is a set F of k -subsets of G such that { f − f ′ : f , f ′ ∈ F , f ≠ f ′ , F ∈ F } = G ∖ H. Let g Z g h be the subgroup of order h in Z g h generated by g. A (Z g h , g Z g h , k , 1) -DF is called cyclic and written as a (g h , h , k , 1) -CDF. This paper shows that for h ∈ { 2 , 3 , 6 } , there exists a (g h , h , 4 , 1) -CDF if and only if g h ≡ h (mod 12) , g ⩾ 4 and (g , h) ∉ { (9 , 3) , (5 , 6) }. As a corollary, it is shown that a 1-rotational Steiner system S (2 , 4 , v) exists if and only if v ≡ 4 (mod 12) and v ≠ 28. This solves the long-standing open problem on the existence of a 1-rotational S (2 , 4 , v). As another corollary, we establish the existence of an optimal (v , 4 , 1) -optical orthogonal code with ⌊ (v − 1) / 12 ⌋ codewords for any positive integer v ≡ 1 , 2 , 3 , 4 , 6 (mod 12) and v ≠ 25. We also give applications of our results to cyclic group divisible designs with block size four and optimal cyclic 3-ary constant-weight codes with weight four and minimum distance six. [ABSTRACT FROM AUTHOR]

Pseudo-geometric designs are combinatorial designs which share the same parameters as a finite geometry design, but are not isomorphic to that design. As far as we know, many pseudo-geometric designs have been constructed by the methods of finite geometries and combinatorics. However, none of pseudo-geometric designs with the parameters S (2 , q + 1 , (q n − 1) / (q − 1)) is constructed by the approach of coding theory. In this paper, we use cyclic codes to construct pseudo-geometric designs. We firstly present a family of ternary cyclic codes from the m -sequences with Welch-type decimation d = 2 ⋅ 3 (n − 1) / 2 + 1 , and obtain some infinite family of 2-designs and a family of Steiner systems S (2 , 4 , (3 n − 1) / 2) using these cyclic codes and their duals. Moreover, the parameters of these cyclic codes and their shortened codes are also determined. Some of those ternary codes are optimal or almost optimal. Finally, we show that one of these obtained Steiner systems is inequivalent to the point-line design of the projective space PG (n − 1 , 3) and thus is a pseudo-geometric design. [ABSTRACT FROM AUTHOR]

If S is a transitive metric space, then | C | ⋅ | A | ≤ | S | for any distance- d code C and a set A , "anticode", of diameter less than d. For every Steiner S (t , k , n) system S , we show the existence of a q -ary constant-weight code C of length n , weight k (or n − k), and distance d = 2 k − t + 1 (respectively, d = n − t + 1) and an anticode A of diameter d − 1 such that the pair (C , A) attains the code–anticode bound and the supports of the codewords of C are the blocks of S (respectively, the complements of the blocks of S). We study the problem of estimating the minimum value of q for which such a code exists, and find that minimum for small values of t. [ABSTRACT FROM AUTHOR]

The research on orthogonal Steiner systems S (t , k , v) was initiated in 1968. For (t , k) ∈ { (2 , 3) , (3 , 4) } , this corresponds to orthogonal Steiner triple systems (STSs) and Steiner quadruple systems (SQSs), respectively. The existence problem of a pair of orthogonal STSs or SQSs was settled completely thirty years ago. However, for Steiner systems with t ≥ 3 and k ≥ 5 , only two small examples of orthogonal pairs were known to exist before this work. An infinite family of orthogonal Steiner systems S (3 , 5 , v) is constructed in this paper. In particular, the existence of a pair of orthogonal Steiner systems S (3 , 5 , 4 m + 1) is established for any even m ≥ 2 ; additionally a pair of orthogonal G-designs G ( 4 m + 1 5 , 5 , 5 , 3) is displayed for any odd m ≥ 3. The construction is based on the Steiner systems admitting 3-transitive automorphism groups supported by elementary symmetric polynomials. Moreover, 50 mutually orthogonal Steiner systems S (5 , 8 , 24) are shown to exist. [ABSTRACT FROM AUTHOR]

Given a partial Steiner triple system (STS) of order n , what is the order of the smallest complete STS it can be embedded into? The study of this question goes back more than 40 years. In this paper we answer it for relatively sparse STSs, showing that given a partial STS of order n with at most r ≤ ε n 2 triples, it can always be embedded into a complete STS of order n + O (r) , which is asymptotically optimal. We also obtain similar results for completions of Latin squares and other designs. This suggests a new, natural class of questions, called deficiency problems. Given a global spanning property P and a graph G , we define the deficiency def (G) of the graph G with respect to the property P to be the smallest positive integer t such that the join G ⁎ K t has property P. To illustrate this concept we consider deficiency versions of some well-studied properties, such as having a K k -decomposition, Hamiltonicity, having a triangle-factor and having a perfect matching in hypergraphs. The main goal of this paper is to propose a systematic study of these problems; thus several future research directions are also given. [ABSTRACT FROM AUTHOR]

Throughout this paper, G always denotes a group and L (G) is the lattice of all subgroups of G. If K ⊴ H ≤ G , then H / K is called a section of G ; such a section is called normal if K , H ⊴ G. We call any set Σ of normal sections of G a stratification of G provided: (i) Σ is G-closed , that is, H / K ∈ Σ whenever H / K ≃ G T / L ∈ Σ , and (ii) L / K , H / L ∈ Σ for each triple K < L < H , where H / K ∈ Σ and L ⊴ G. Now let Σ be any stratification of G. Then we write L Σ (G) to denote the set of all subgroups A of G such that A G / A G ∈ Σ. We say that a stratification Σ of G is a formation Fitting set of G provided: (i) H / (K ∩ N) ∈ Σ for every two sections H / K , H / N ∈ Σ , and (ii) H V / K ∈ Σ for every two sections H / K , V / K ∈ Σ. We prove that the set L Σ (G) forms a sublattice of L (G) for every formation Fitting set Σ of G and we also discuss some applications of sublattices of this kind. [ABSTRACT FROM AUTHOR]

Diophantine tuples are sets of positive integers with the property that the product of any two elements in the set increased by the unity is a square. In the main theorem of this paper it is shown that any Diophantine triple, the second largest element of which is between the square and four times the square of the smallest one, is uniquely extended to a Diophantine quadruple by joining an element exceeding the largest element in the triple. A similar result is obtained under the hypothesis that the two smallest elements have the form T 2 + 2 T , 4 T 4 + 8 T 3 − 4 T for some positive integer T , which we encounter as an exceptional case. The main theorem implies that the same is valid for triples with smallest elements K A 2 , 4 K A 4 ± 4 A for some positive integers A and K ∈ { 1 , 2 , 3 , 4 }. [ABSTRACT FROM AUTHOR]

Two classical results in algebraic geometry are that the branch curve of a del Pezzo surface of degree 1 can be embedded as a space sextic curve in P 3 and that every space sextic curve has exactly 120 tritangents corresponding to its odd theta characteristics. In this paper we revisit both results from the computational perspective. Specifically, we give an algorithm to construct space sextic curves that arise from blowing up P 2 at eight points and provide algorithms to compute the 120 tritangents and their Steiner system of any space sextic. Furthermore, we develop efficient inverses to the aforementioned methods. We present an algorithm to either reconstruct the original eight points in P 2 from a space sextic or certify that this is not possible. Moreover, we extend a construction of Lehavi [8] which recovers a space sextic from its tritangents and Steiner system. All algorithms in this paper have been implemented in magma. [ABSTRACT FROM AUTHOR]

Let k , m and n be integers. In this paper, for a fixed integer μ ≠ 0 , we show that the family of Thue equation x 4 − k m n x 3 y + (k m 2 − k n 2 + 2) x 2 y 2 + k m n x y 3 + y 4 = μ , is reducible by Tzanakis's method into a system of pellian equations k V 2 − (k m 2 + 4) U 2 = − 4 μ , k Z 2 − (k n 2 − 4) U 2 = 4 μ , with any triple of integers (k , m , n) such that k > 0 , | n | ≥ 2 , | m | ≥ 2. We consider this system for any even integer k ≠ 2 □ , μ = 1 and we prove that for all integers | n | ≥ 2 and | m | ≥ 2 that are sufficiently large and have sufficiently large common divisor this system has only the trivial solutions (U , V , Z ,) = (± 1 , ± m , ± n). We also show that if k ≠ 2 □ is even, then the system has in general at most 8 solutions in positive integers. [ABSTRACT FROM AUTHOR]

Inspired by an L p Steiner formula for the L p affine surface area proved by Tatarko and Werner, we define, in analogy to the classical Steiner formula, L p -Steiner quermassintegrals. Special cases include the classical mixed volumes, the dual mixed volumes, the L p affine surface areas and the mixed L p affine surface areas. We investigate the properties of the L p -Steiner quermassintegrals in a special class of convex bodies. In particular, we show that they are rotation and reflection invariant valuations in this class of convex bodies with a certain degree of homogeneity. Such valuations seem new and have not been observed before. [ABSTRACT FROM AUTHOR]

In this paper, we show that if we have a sequence of Hadamard triples { (N n , B n , L n) } with B n ⊂ { 0 , 1 ,.. , N n − 1 } for n = 1 , 2 ,... , except an extreme case, then the associated Cantor-Moran measure μ = μ (N n , B n) = δ 1 N 1 B 1 ⁎ δ 1 N 1 N 2 B 2 ⁎ δ 1 N 1 N 2 N 3 B 3 ⁎... = μ n ⁎ μ > n with support inside [ 0 , 1 ] always admits an exponential orthonormal basis E (Λ) = { e 2 π i λ x : λ ∈ Λ } for L 2 (μ) , where Λ is obtained from suitably modifying L n. Here, μ n is the convolution of the first n Dirac measures and μ > n denotes the tail-term. We show that the completeness of E (Λ) in general depends on the "equi-positivity" of the sequence of the pull-backed tail of the Cantor-Moran measure ν > n (⋅) = μ > n ((N 1... N n) − 1 (⋅)). Such equi-positivity can be analyzed by the integral periodic zero set of the weak limit of { ν > n }. This result offers a new conceptual understanding of the completeness of exponential functions and it improves significantly many partial results studied by recent research, whose focus has been specifically on # B n ≤ 4. Using the Bourgain's example that a sum of sine can be asymptotically small, we show that, in the extreme case, there exists some Cantor-Moran measure such that the equi-positive condition fails and the Fourier transform of the associated ν > n uniformly converges on some unbounded set. [ABSTRACT FROM AUTHOR]

We investigate the dynamics of the (47171) Lempo triple system, also known by 1999 TC 36 . We derive a full 3D N -body model that takes into account the orbital and spin evolution of all bodies, which are assumed triaxial ellipsoids. We show that, for reasonable values of the shapes and rotational periods, the present best fitted orbital solution for the Lempo system is chaotic and unstable in short time-scales. The formation mechanism of this system is unknown, but the orbits can be stabilised when tidal dissipation is taken into account. The dynamics of the Lempo system is very rich, but depends on many parameters that are presently unknown. A better understanding of this systems thus requires more observations, which also need to be fitted with a complete model like the one presented here. [ABSTRACT FROM AUTHOR]

We construct a Ramsey class whose objects are Steiner systems. In contrast to the situation with general r -uniform hypergraphs, it turns out that simply putting linear orders on their sets of vertices is not enough for this purpose: one also has to strengthen the notion of subobjects used from “induced subsystems” to something we call “strongly induced subsystems”. Moreover we study the Ramsey properties of other classes of Steiner systems obtained from this class by either forgetting the order or by working with the usual notion of subsystems. This leads to a perhaps surprising induced Ramsey theorem in which designs get coloured. [ABSTRACT FROM AUTHOR]

Equiangular tight frames provide optimal packings of lines through the origin. We combine Steiner triple systems with Hadamard matrices to produce a new infinite family of equiangular tight frames. This in turn leads to new constructions of strongly regular graphs and distance-regular antipodal covers of the complete graph. [ABSTRACT FROM AUTHOR]

We give a classification up to equivalence of the fine group gradings by abelian groups on the Jordan pairs and triple systems of types bi-Cayley and Albert, under the assumption that the base field is algebraically closed of characteristic different from 2. The associated Weyl groups are computed. We also determine, for each fine grading on the bi-Cayley and Albert pairs, the induced grading on the exceptional simple Lie algebra given by the Tits–Kantor–Koecher construction. [ABSTRACT FROM AUTHOR]

We study the multi-budgeted version of the metric Survivable Network Design Problem (SND) (Jain, 2001), also known as Steiner Network problem, where besides the usual connectivity requirements (i.e., lower bound on the number edge-disjoint paths) between pre-specified pairs of points, we are also asked to satisfy a set of extra linear constraints (the budgets). Based on combinatorial properties of extreme point solutions of the natural LP relaxation of the problem and using the iterative method, we design new approximation algorithms with the following performance guarantee: if any edge participates in at most f ∈ N budgets, then we show how we can device an ( f + 2 , f + 2 ) bi-criteria approximation algorithm in polynomial time i.e., return a solution with cost at most ( 2 + f ) times the optimal one with a potential budget overflow bounded from above by the same factor. In other words, the approximation and budget violation guarantee we achieve is a linear function of the maximum frequency among all the edges in the budgets, as opposed to a function of the number of budgets themselves and this constitutes a strict improvement over the previous approaches. Our approach is flexible enough and we demonstrate how it can be used to provide a ( 4 , 4 ) bi-criteria algorithm for the Minimum Weighted Bounded Degree version of the SND problem in which we have the standard SND connectivity constraints and, additionally, for every vertex v in the graph we have an upper bound on the sum of the weights of the edges incident to that edge in any feasible solution. These problems, besides their obvious theoretical interest, have numerous real life applications from Cloud Computing to Optical Networking systems. [ABSTRACT FROM AUTHOR]

The family Σ r consists of all r -graphs with three edges D 1 , D 2 , D 3 such that | D 1 ∩ D 2 | = r − 1 and D 1 △ D 2 ⊆ D 3 . A generalized triangle , T r ∈ Σ r is an r -graph on { 1 , 2 , … , 2 r − 1 } with three edges D 1 , D 2 , D 3 , such that D 1 = { 1 , 2 , … , r − 1 , r } , D 2 = { 1 , 2 , … , r − 1 , r + 1 } and D 3 = { r , r + 1 , … , 2 r − 1 } . Frankl and Füredi conjectured that for all r ≥ 4 , ex ( n , Σ r ) = ex ( n , T r ) for all sufficiently large n and they also proved it for r = 3 . Later, Pikhurko showed that the conjecture holds for r = 4 . In this paper we determine ex ( n , T 5 ) and ex ( n , T 6 ) for sufficiently large n , proving the conjecture for r = 5 , 6 . [ABSTRACT FROM AUTHOR]

We consider the Steiner Multicut problem, which asks, given an undirected graph G , a collection T = { T 1 , … , T t } , T i ⊆ V ( G ) , of terminal sets of size at most p , and an integer k , whether there is a set S of at most k edges or nodes such that of each set T i at least one pair of terminals is in different connected components of G − S . We provide a dichotomy of the parameterized complexity of Steiner Multicut . For any combination of k , t , p , and the treewidth tw ( G ) as constant, parameter, or unbounded, and for all versions of the problem (edge deletion and node deletion with and without deletable terminals), we prove either that the problem is fixed-parameter tractable, W [ 1 ] -hard, or (para-) NP -complete. Our characterization includes a dichotomy for Steiner Multicut on trees as well as a polynomial time versus NP -hardness dichotomy (by restricting k , t , p , tw ( G ) to constant or unbounded). [ABSTRACT FROM AUTHOR]

We study reflection positivity in the context of Hilbert space, and Krein-space theory. Our context is that of triple systems (U , J , M +) assumed to satisfy the axioms for reflection positivity (also known as Osterwalder-Schrader positivity). Applications include quantum field theory and the theory of unitary representations of Lie groups. Our analysis and classification make use of Krein space theory, and of realizations of input/output systems. We present a new and explicit classification of the case when triples (U , J , M +) constitute reflection positive systems. A key point in our analysis is a specific choice of signature operator J , and Krein space, leading then to an operator theoretic and geometric classification formula for reflection positive triples (U , J , M +) , with U assumed unitary and J -self-adjoint, and M + reflecting the choices of the associated J -positive and U -invariant subspaces. We further consider the wider setting when U is only assumed J -self-adjoint, and we demonstrate how choices of U may be characterized by specific partially defined and contractive operators E. Then the corresponding admissible subspaces M + will be realized as spaces G (X) , graph of a second linear operator X , where the possibilities for such X , as operators, are decided by a non-linear equation (in X), called the Riccati equation. Our present applications include non-commutative harmonic analysis. [ABSTRACT FROM AUTHOR]

Abstract: For each positive integer n, we construct a Steiner triple system of order with no almost parallel class; that is, with no set of disjoint triples. In fact, we construct families of -designs with an analogous property. The only previously known examples of Steiner triple systems of order congruent to without almost parallel classes were the projective triple systems of order with n odd, and 2 of the 11,084,874,829 Steiner triple systems of order 19. [Copyright &y& Elsevier]

The Turán number of hypergraphs has been studied extensively. Here we deal with a recent direction, the linear Turán number, and restrict ourselves to linear triple systems, a collection of triples on a set of points in which any two triples intersect in at most one point. For a fixed linear triple system F , the linear Turán number ex L (n , F) is the maximum number of triples in a linear triple system with n points that does not contain F as a subsystem. We initiate the study of the linear Turán number for an acyclic F. In this case ex L (n , F) is linear in n and we aim for good bounds. Since the case of trees is already difficult for graphs (Erdős–Sós conjecture), we concentrate on matchings, paths and small trees. In case of matchings, where M k is the set of k pairwise disjoint triples, we prove that for fixed k and large enough n , ex L (n , M k) = f (n , k) where f (n , k) is the maximum number of triples that can meet k − 1 points in a linear triple system on n points. This is an analogue of an old result of Erdős on hypergraph matchings. For the k -edge linear path P k we show (extending some standard path increasing methods used for graphs) that ex L (n , P k) ≤ 1. 5 k n which is probably far from best possible. Finding ex L (n , F) relates to difficult problems on Steiner triple systems and interesting even for small trees. For example, for P 4 , the path with four triples, ex L (n , P 4) ≤ 4 n 3 with equality only for disjoint union of affine planes of order 3. On the other hand, for E 4 , the tree having three pairwise disjoint triples and a fourth one meeting all of them, we have bounds only: 6 ⌊ n − 3 4 ⌋ ≤ ex L (n , E 4) ≤ 2 n. [ABSTRACT FROM AUTHOR]

This paper concentrates on mutually disjoint 2-chromatic Steiner quadruple systems of order v (briefly by SQS(v)s), meaning that the SQS(v)s are mutually disjoint and they are mutually 2-chromatic having the same two color classes. Following Phelps and Rosa's work, we study maximum sets of mutually disjoint 2-chromatic SQS(v)s by applying direct constructions for suitable collections of triple representatives of V q by utilizing automorphism groups of affine transformations in the finite fields F q for prime powers q. Our main result presents many new maximum sets of mutually disjoint 2-chromatic SQS(v)s. We also improve the lower bounds on the number of mutually disjoint SQS(v)s as a by-product. [ABSTRACT FROM AUTHOR]

Novák conjectured in 1974 that for any cyclic Steiner triple systems of order v with v ≡ 1 (mod 6) , it is always possible to choose one block from each block orbit so that the chosen blocks are pairwise disjoint. We consider the generalization of this conjecture to cyclic (v , k , λ) -designs with 1 ⩽ λ ⩽ k − 1. Superimposing multiple copies of a cyclic symmetric design shows that the generalization cannot hold for all v , but we conjecture that it holds whenever v is sufficiently large compared to k. We confirm that the generalization of the conjecture holds when v is prime and λ = 1 and also when λ ⩽ (k − 1) / 2 and v is sufficiently large compared to k. As a corollary, we show that for any k ⩾ 3 , with the possible exception of finitely many composite orders v , every cyclic (v , k , 1) -design without short orbits is generated by a (v , k , 1) -disjoint difference family. [ABSTRACT FROM AUTHOR]

Abstract: Given a graph with a cost function and a vertex subset , an internal Steiner tree is a Steiner tree that contains all the vertices in , and such that each vertex in must be an internal vertex. The internal Steiner tree problem involves finding an internal Steiner tree whose total cost is the minimum. In this paper, we first show that the internal Steiner tree problem is MAX SNP-hard. We then present a -approximation algorithm for solving the problem on complete graphs, where is an approximation ratio for the Steiner tree problem. Currently, the best-known is . Moreover, for the case where the cost of each edge is restricted to being either 1 or 2, we present a -approximation algorithm for the problem. [Copyright &y& Elsevier]

Abstract: The block graph of a Steiner triple system of order v is a strongly regular graph. For large v, every strongly regular graph with these parameters is the block graph of a Steiner triple system, but exceptions exist for small orders. An explanation for some of the exceptional graphs is here provided via the concept of switching. (Group divisible designs corresponding to) Latin squares are also treated in an analogous way. Many new strongly regular graphs are obtained by switching and by constructing graphs with prescribed automorphisms. In particular, new strongly regular graphs with the following parameters that do not come from Steiner triple systems or Latin squares are found: , , , , , and . [Copyright &y& Elsevier]

Abstract: It has been conjectured that any partial triple system of order u and index λ can be embedded in a triple system of order v and index λ whenever , is even and . This conjecture is known to hold for and for all even . Here the conjecture is proven for all remaining values of λ when . [Copyright &y& Elsevier]

Abstract: Nash-Williams and Tutte independently characterized when a graph has k edge-disjoint spanning trees; a consequence is that 2k-edge-connected graphs have k edge-disjoint spanning trees. Kriesell conjectured a more general statement: defining a set to be j-edge-connected in G if S lies in a single component of any graph obtained by deleting fewer than j edges from G, he conjectured that if S is 2k-edge-connected in G, then G has k edge-disjoint trees containing S. Lap Chi Lau proved that the conclusion holds whenever S is 24k-edge-connected in G. We improve Lauʼs result by showing that it suffices for S to be 6.5k-edge-connected in G. This and an analogous result for packing stronger objects called “S-connectors” follow from a common generalization of the Tree Packing Theorem and Hakimiʼs criterion for orientations with specified outdegrees. We prove the general theorem using submodular functions and the Matroid Union Theorem. [Copyright &y& Elsevier]

Abstract: We consider the k-Directed Steiner Forest (k-DSF) problem: Given a directed graph with edge costs, a collection of ordered node pairs, and an integer , find a minimum cost subgraph H of G that contains an st-path for (at least) k pairs . When , we get the Directed Steiner Forest (DSF) problem. The best known approximation ratios for these problems are: for k-DSF by Charikar et al. (1999) , and for DSF by Chekuri et al. (2008) . Our main result is achieving the first sub-linear in terms of approximation ratio for DSF. Specifically, we give an -approximation scheme for DSF. For k-DSF we give a simple greedy -approximation algorithm. This improves upon the best known ratio by Charikar et al. (1999) , and (almost) matches, in terms of k, the best ratio known for the undirected variant (Gupta et al., 2010 ). This algorithm uses a new structure called start-junction tree which may be of independent interest. [Copyright &y& Elsevier]

Abstract: Masbaum and Vaintrobʼs “Pfaffian matrix-tree theorem” implies that counting spanning trees of a 3-uniform hypergraph (abbreviated to 3-graph) can be done in polynomial time for a class of “3-Pfaffian” 3-graphs, comparable to and related to the class of Pfaffian graphs. We prove a complexity result for recognizing a 3-Pfaffian 3-graph and describe two large classes of 3-Pfaffian 3-graphs – one of these is given by a forbidden subgraph characterization analogous to Littleʼs for bipartite Pfaffian graphs, and the other consists of a class of partial Steiner triple systems for which the property of being 3-Pfaffian can be reduced to the property of an associated graph being Pfaffian. We exhibit an infinite set of partial Steiner triple systems that are not 3-Pfaffian, none of which can be reduced to any other by deletion or contraction of triples. We also find some necessary or sufficient conditions for the existence of a spanning tree of a 3-graph (much more succinct than can be obtained by the currently fastest polynomial-time algorithm of Gabow and Stallmann for finding a spanning tree) and a superexponential lower bound on the number of spanning trees of a Steiner triple system. [Copyright &y& Elsevier]

Abstract: We give a construction of a 2- design starting from a Steiner system and an affine plane of order n. This construction is applied to known classes of Steiner systems arising from affine and projective geometries, Denniston designs, and unitals. We also consider the extendability of these designs to 3-designs. [ABSTRACT FROM AUTHOR]

Abstract: This paper takes a significant step towards confirming a long-standing and far-reaching conjecture of Peter J. Cameron and Cheryl E. Praeger. They conjectured in 1993 that there are no non-trivial block-transitive 6-designs. We prove that the Cameron–Praeger conjecture is true for the important case of non-trivial Steiner 6-designs, i.e. for 6- designs with , except possibly when the group is with or 3, and e is an odd prime power. [Copyright &y& Elsevier]

Abstract: We define basic networks as the undirected subgraphs with minimal number of units in which the distances (geodesics, minimal path lengths) among a set of selected nodes, which we call seeds, in the original graph are conserved. The additional nodes required to draw the basic network are called connectors. We describe a heuristic strategy to find the basic networks of complex graphs. We also show how the characterization of these networks may help to obtain relevant biological information from highly complex protein–protein interaction data. [Copyright &y& Elsevier]

Abstract: We develop an idea of a local 3-edge-coloring of a cubic graph, a generalization of the usual 3-edge-coloring. We allow for an unlimited number of colors but require that the colors of two edges meeting at a vertex always determine the same third color. Local 3-edge-colorings are described in terms of colorings by points of a partial Steiner triple system such that the colors meeting at each vertex form a triple of the system. An important place in our investigation is held by the two smallest non-trivial Steiner triple systems, the Fano plane and the affine plane . For , and 6 we identify certain configurations and of lines of the Fano plane and the affine plane, respectively, and prove a theorem saying that a cubic graph admits an -coloring if and only if it admits an -coloring. Among consequences of this is the result of Holroyd and Škoviera [F. Holroyd, M. Škoviera, Colouring of cubic graphs by Steiner triple systems, J. Combin. Theory Ser. B 91 (2004) 57–66] that the edges of every bridgeless cubic graph can be colored by using points and blocks of any non-trivial Steiner triple system . Another consequence is that every bridgeless cubic graph has a proper edge-coloring by elements of any abelian group of order at least 12 such that around each vertex the group elements sum to 0. We also propose several conjectures concerning edge-coloring of cubic graphs and relate them to several well-known conjectures. In particular, we show that both the Cycle Double Cover Conjecture and the Fulkerson Conjecture can be formulated as a coloring problem in terms of known geometric configurations — the Desargues configuration and the Cremona–Richmond configuration, respectively. [Copyright &y& Elsevier]

Abstract: We give the first known examples of 6-sparse Steiner triple systems by constructing 29 such systems in the residue class 7 modulo 12, with orders ranging from 139 to 4447. We then present a recursive construction which establishes the existence of 6-sparse systems for an infinite set of orders. Observations are also made concerning existing construction methods for perfect Steiner triple systems, and we give a further example of such a system. This has order 135,859 and is only the fourteenth known. Finally, we present a uniform Steiner triple system of order 180,907. [Copyright &y& Elsevier]

Abstract: The Steiner quadruple systems of order 16 are classified up to isomorphism by means of an exhaustive computer search. The number of isomorphism classes of such designs is . Properties of the designs—including the orders of the automorphism groups and the structures of the derived Steiner triple systems of order 15—are tabulated. A consistency check based on double counting is carried out to gain confidence in the correctness of the classification. [Copyright &y& Elsevier]

Abstract: In [Z. Füredi, Turán type problems, in: Surveys in Combinatorics, Guildford, 1991, in: London Math. Soc. Lecture Note Ser., vol. 166, Cambridge Univ. Press, Cambridge, 1991, pp. 253–300, MR1161467 (93d:05072)], Füredi raised a conjecture about the maximum size of L-intersecting families. In this note, we address a variant of this conjecture. In particular, we show that for any Steiner triple system on , there exist a family of k-sets on with and such that for every the family is isomorphic to . [Copyright &y& Elsevier]

Abstract: It is known that the Horton starters can be used to construct uniform one-factorizations of the complete graph. Of primary interest is the cycle structure of such one-factorizations. In this paper we give some general conditions for the existence of k-cycles, then specialize this to the cases , completely characterizing the four-cycle case. We also show that for each even and any positive integer N there exists a uniform one-factorization in some large enough complete graph containing at least N k-cycles. [Copyright &y& Elsevier]

Abstract: A Steiner triple system of order (briefly STS) consists of a -element set X and a collection of 3-element subsets of X, called blocks, such that every pair of distinct points in X is contained in a unique block. A large set of disjoint STS (briefly LSTS) is a partition of all 3-subsets (triples) of X into STS. In 1983–1984, Lu Jiaxi first proved that there exists an LSTS for any or with six possible exceptions and a definite exception . In 1989, Teirlinck solved the existence of LSTS for the remaining six orders. Since their proof is very complicated, it is much desired to find a simple proof. For this purpose, we give a new proof which is mainly based on the 3-wise balanced designs and partitionable candelabra systems. [Copyright &y& Elsevier]

We prove that for n>3 every STS(n) has both an orientable and a nonorientable embedding in which the triples of the STS(n) appear as triangular faces and there is just one additional large face. We also obtain detailed results about the possible automorphisms of such embeddings. [Copyright &y& Elsevier]

Let q be 2m with m≥1. We construct a family of dual hyperovals over GF(q) inside the 2n-1-dimensional projective space PG(GF(qn)×GF(qn)). [Copyright &y& Elsevier]

In Adv. Geom. 3 (2003) 245, a class of d-dimensional dual hyperovals is constructed starting from a subset X of PG(d,2) with certain properties. In this paper, a criterion for X to provide a d-dimensional dual hyperoval is given in terms of some functions. Based on this, we describe such subsets, and show that there are exactly two isomorphism classes of d-dimensional dual hyperovals arising from those subsets and that a similar statement holds for those of the associated Steiner systems S(3,4,2d+1). [Copyright &y& Elsevier]

Let S be a Steiner triple system and G a cubic graph. We say that G is S-colourable if its edges can be coloured so that at each vertex the incident colours form a triple of S. We show that if S is a projective system PG(n,2), n&ges;2, then G is S-colourable if and only if it is bridgeless, and that every bridgeless cubic graph has an S-colouring for every Steiner triple system of order greater than 3. We establish a condition on a cubic graph with a bridge which ensures that it fails to have an S-colouring if S is an affine system, and we conjecture that this is the only obstruction to colouring any cubic graph with any non-projective system of order greater than 3. [Copyright &y& Elsevier]

Any partial Steiner triple system of order u can be embedded in a Steiner triple system of order v if v≡1,3 (mod 6) and v&ges;3u−2. [Copyright &y& Elsevier]

Orthogonal quadruple systems are defined and investigated. Orthogonal quadruple systems with an additional nesting property are shown to provide a new construction of 3-frames F(3,4,n{2}) (Design Codes Cryptogr. 4 (1994) 5). Constructions for pairs of nested orthogonal quadruple systems are provided. Applications to 2-resolvable Steiner quadruple systems and highly nonlinear functions are discussed. [Copyright &y& Elsevier]

Two Steiner triple systems (STS) are orthogonal if their sets of triples are disjoint, and two disjoint pairs of points defining intersecting triples in one system fail to do so in the other. In 1994, it was shown (Canad. J. Math. 46(2) (1994) 239–252) that there exist a pair of orthogonal Steiner triple systems of order v for all v≡1,3 (mod 6), with v&ges;7, v≠9. In this paper we show that there exist three pairwise orthogonal Steiner triple systems of order v for all v≡1 (mod 6), with v&ges;19 and for all v≡3 (mod 6), with v&ges;27 with only 24 possible exceptions. [Copyright &y& Elsevier]

A Steiner triple system (STS(v)) is said to be 3-balanced if every 3-colouring of it is equitable; that is, if the cardinalities of the colour classes differ by at most one. A 3-colouring, φ, of an STS(v) is unique if there is no other way of 3-colouring the STS(v) except possibly by permuting the colours of φ. We show that for every admissible v&ges;25, there exists a 3-balanced STS(v) with a unique 3-colouring and an STS(v) which has a unique, non-equitable 3-colouring. [Copyright &y& Elsevier]