Search

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]

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 study the Steiner Tree problem, in which a set of terminal vertices needs to be connected in the cheapest possible way in an edge-weighted graph. This problem has been extensively studied from the viewpoint of approximation and also parameterization. In particular, on one hand Steiner Tree is known to be sansA sansP sansX -hard, and sansW [sanstwo ]-hard on the other, if parameterized by the number of nonterminals (Steiner vertices) in the optimum solution. In contrast to this, we give an efficient parameterized approximation scheme (sansE sansP sansA sansS), which circumvents both hardness results. Moreover, our methods imply the existence of a polynomial size approximate kernelization scheme (sansP sansS sansA sansK sansS) for the considered parameter. We further study the parameterized approximability of other variants of Steiner Tree, such as Directed Steiner Tree and Steiner Forest. For none of these is an sansE sansP sansA sansS likely to exist for the studied parameter. For Steiner Forest an easy observation shows that the problem is sansA sansP sansX -hard, even if the input graph contains no Steiner vertices. For Directed Steiner Tree we prove that approximating within any function of the studied parameter is sansW [sansone ]-hard. Nevertheless, we show that an sansE sansP sansA sansS exists for Unweighted Directed Steiner Tree, but a sansP sansS sansA sansK sansS does not. We also prove that there is an sansE sansP sansA sansS and a sansP sansS sansA sansK sansS for Steiner Forest if in addition to the number of Steiner vertices, the number of connected components of an optimal solution is considered to be a parameter. [ABSTRACT FROM AUTHOR]

Let Ct denote the loose cycle on t = 2s vertices, that is, the 3-uniform hypergraph obtained from a graph cycle C on s vertices by replacing each edge e =\{ u, v\} of C with the edge triple\{ u, xe, v\}, where xe is uniquely assigned to e. We will give a tight minimum degree condition that guarantees all sufficiently large 3-uniform hypergraphs on n\in tZ vertices contain n t vertex disjoint copies of Ct. [ABSTRACT FROM AUTHOR]

We prove that any Steiner triple system S, with n = v(S) sufficiently large, admits a packing by almost spanning paths that covers almost all edges. More formally, for any μ > 0, we obtain a family of (1-μ)n=3 pairwise edge-disjoint paths, with (1-μ)n vertices each, all contained in S. [ABSTRACT FROM AUTHOR]

A Berge-K4 in a triple system is a configuration with four vertices v1, v2, v3, v4 and six distinct triples {eij: 1 ≤ i < j ≤ 4} such that{ui, vj}⊂ eij for every 1 ≤ i < j ≤ 4. We denote by B the set of Berge-K4 configurations. A triple system is B -free if it does not contain any member of B . We prove that the maximum number of triples in a B -free triple system on n ≥ 6 points is obtained by the balanced complete 3-partite triple system: all triples {abc: a ϵ A, b ϵ B, c ϵ C} where A,B,C is a partition of n points with [n/3]= |A| ≤|B| ≤ |C| = n/33 [ABSTRACT FROM AUTHOR]

In the directed Steiner tree problem, we are given a digraph, nonnegative arc weights, a subset of vertices called terminals, and a special terminal called the root. The goal is to compute a minimum weight directed tree that connects each terminal to the root. We study the classical directed cut linear programming (LP) formulation which has a variable for every arc, and a constraint for every cut that separates a terminal from the root. For what instances is the directed cut LP integral? In this paper we demonstrate how the celebrated theorem of Lehman [Math. Program., 17 (1979), pp. 403-417] on minimally nonideal clutters provides a framework for deriving answers to this question. Specifically, we show that this framework yields short proofs of the optimum arborescences theorem and the integrality result for series-parallel digraphs. Furthermore, we use this framework to show that the directed cut linear program is integral for digraphs that are acyclic and have at most two nonterminal vertices. [ABSTRACT FROM AUTHOR]

The expansion G+ of a graph G is the 3-uniform hypergraph obtained from G by enlarging each edge of G with a new vertex disjoint from V(G) such that distinct edges are enlarged by distinct vertices. Let ex3 (n, F) denote the maximum number of edges in a 3-uniform hypergraph with n vertices not containing any copy of a 3-uniform hypergraph F. The study of ex3(n, G+) includes some well-researched problems, including the case that F consists of k disjoint edges, G is a triangle, G is a path or cycle, and G is a tree. In this paper we initiate a broader study of the behavior of ex3(n, G+). Specifically, we show ex3 (n, K s,t+) = Θ(n3-3/s) whenever t > (s -- 1)! and s ≥ 3. One of the main open problems is to determine for which graphs G the quantity ex3 (n, G+) is quadratic in n. We show that this occurs when G is any bipartite graph with Turan number o(nφ) where φ = 1+√5/2, and in particular this shows ex3 (n, G+) = O(n²) when G is the three-dimensional cube graph. [ABSTRACT FROM AUTHOR]

We construct Steiner triple systems without parallel classes for an infinite number of orders congruent to 3 (mod 6). The only previously known examples have order 15 or 21. [ABSTRACT FROM AUTHOR]

In 2009 it was established that any partial Steiner triple system of order u has an embedding of order v for each v &#8805: 2u+1 such that v = 1, 3 (mod 6), in accordance with a conjecture of Lindner. It is known that for each u ≥ 9, there exists a partial Steiner triple system of order u that does not have an embedding of order v for any v < 2u + 1, so this result is best possible in one sense. Many partial Steiner triple systems do have embeddings of orders smaller than 2u + 1, however, although little is known about when such embeddings exist. In this paper we construct embeddings of orders less than 2u+1 for partial Steiner triple systems with few triples. In particular, we show that a partial Steiner triple system of order u ≥ 62 with at most u²/50-11u/100-116/75 triples has an embedding of order v for each admissible integer v ≥ 8u+17/5. [ABSTRACT FROM AUTHOR]

A k-bar visibility representation of a digraph G assigns each vertex at most k horizontal segments in the plane so that G has an arc uv if and only if some segment for u "sees" some segment for v above it by a vertical line of sight. The (bar) visibility number b(G) of a digraph G is the least k permitting such a representation. Among other results, we show that b(G) ≤ 4 when G is a planar digraph (reducing to 3 when the underlying graph has no triangles), b(G) ≤ 2 when G is outerplanar, and b(G) ≤ (n + 10)/3 when G has n vertices. When G is the n-vertex transitive tournament, b(G) ≤ 7n/24 + 2√ n log n, improving to b(G) < 3n/14 + 42 when n is sufficiently large. Our tools include arboricity, interval number, and Steiner systems. [ABSTRACT FROM AUTHOR]

This paper focuses on the design of minimum-cost networks satisfying two technical constraints. First, the connected components should be unicyclic. Second, some given special nodes must belong to cycles. This problem is a generalization of two known problems: the perfect binary 2-matching problem and the problem of computing a minimum-weight basis of the bicircular matroid. It turns out that the problem is polynomially solvable. An exact extended linear formulation is provided. We also present a partial description of the convex hull of the incidence vectors of these Steiner networks. Polynomial-time separation algorithms are described. One of them is a generalization of the Padberg-Rao algorithm to separate blossom inequalities. [ABSTRACT FROM AUTHOR]

We consider the class of max-min and min-max optimization problems subject to a global budget constraint. We undertake a systematic algorithmic and complexity-theoretic study of such problems, which we call design problems. Every optimization problem leads to a natural design problem. Our main result uses techniques of Freund and Schapire [Games Econom. Behav., 29 (1999), pp. 79-103] from learning theory, and its generalizations, to show that for a large class of optimization problems, the design version is as easy as the optimization version. We also observe the relationship between max-min design problems and fractional packing problems. In particular, we obtain in a systematic fashion results about the fractional packing number of Steiner trees. [ABSTRACT FROM AUTHOR]

An N2 resolvable Latin square is a Latin square with no 2 × 2 subsquares that also has an orthogonal mate. In this paper we show that N2 resolvable Latin squares exist for all orders n with n ≠ 2, 4, 6, 8. [ABSTRACT FROM AUTHOR]

Motivated by applications in combinatorial group testing for consecutive positives, we investigate a block sequence of a maximum packing MP(t, k, v) which contains the blocks exactly once such that the collection of all blocks together with all unions of two consecutive blocks of this sequence forms an error correcting code with minimum distance d. Such a sequence is usually called a block sequence with consecutive unions having minimum distance d, and denoted by BSCU(t, k, v∣d). In this paper, we show that the necessary conditions for the existence of BSCU(3, 4, v∣4)s of Steiner quadruple systems, namely, v Ξ 2,4 (mod 6) and v ≥ 4, are also sufficient, excepting v = 8, 10. [ABSTRACT FROM AUTHOR]

Let V be a finite set and M a collection of subsets of V. Then M is an alignment of V if and only if M is closed under taking intersections and contains both V and the empty set. If M is an alignment of V , then the elements of M are called convex sets and the pair (V,M) is called an aligned space. If S ⊆ V , then the convex hull of S is the smallest convex set that contains S. Suppose X ϵ M. Then x ϵ X is an extreme point for X if X \ {x} ϵ M. The collection of all extreme points of X is denoted by ex(X). A convex geometry on a finite set is an aligned space with the additional property that every convex set is the convex hull of its extreme points. Let G be a connected graph. A set S of vertices is g-convex if for every pair u, v of vertices in S, every vertex that belongs to some u-v geodesic (shortest path) is also in S. A set S of vertices in G is k-Steiner-convex, denoted by gk-convex, if, for every set T of k vertices of S, every vertex that belongs to some Steiner tree for T, i.e., a subtree of G of smallest size containing T, is also in S. Let R = {k1, k2,∦, kt} be a collection of positive integers such that 2 ≤ k1 < k2 < ∦ < kt. We say a set S of vertices in a connected graph is gR-convex if S is gki -convex for 1 ≤ i ≤ t. A set S of vertices of G is g3-convex if, for every pair u, v of vertices of S, distance at least 3 apart in G, every vertex that belongs to some u-v geodesic in G is also in S. A set of vertices that is both g3-convex and g3-convex is called a g33-convex set. Structural characterizations are given of those classes of graphs for which (i) the g3-convex sets, (ii) the gR-convex sets for those sets R that have minimum element 2 or 3, and (iii) the g33-convex sets form a convex geometry. [ABSTRACT FROM AUTHOR]

A well-known theorem of Nash-Williams and Tutte gives a necessary and sufficient condition for the existence of k edge-disjoint spanning trees in an undirected graph. A corollary of this theorem is that every 2k-edge-connected graph has k edge-disjoint spanning trees. We show that the splitting-off theorem of Mader in undirected graphs implies a generalization of this to finding k edge-disjoint Steiner forests in Eulerian graphs. This leads to new 2-approximation rounding algorithms for certain constrained 0-1 forest problems considered by Goemans and Williamson. These algorithms also produce approximate integer decompositions of fractional solutions. We then discuss open problems and outlets for this approach to the more general class of 0-1 skew supermodular network design problems. [ABSTRACT FROM AUTHOR]

A set of pairwise edge-disjoint triangles of an edge-colored Kn is r-color avoiding if it does not contain r monochromatic triangles, each having a different color. Let fr(n) be the maximum integer so that in every edge coloring of Kn with r colors, there is a set of fr(n) pairwise edge-disjoint triangles that is r-color avoiding. We prove that 0.1177n2(1 - o(1)) < f2(n) < 0.1424n2(1 + o(1)). The proof of the lower bound uses probabilistic arguments, fractional relaxation and some packing theorems. We also prove that fr(n)/n2 < 1/6 (1 - 0.145r-1) + o(1). In particular, for every r, if n is sufficiently large, there are edge colorings of Kn with r colors so that the removal of any o(n2) members from any Steiner triple system does not turn it r-color avoiding. [ABSTRACT FROM AUTHOR]

We consider the Steiner k-cut problem which generalizes both the k-cut problem and the multiway cut problem. The Steiner k-cut problem is defined as follows. Given an edge-weighted undirected graph G = (V,E), a subset of vertices X ⊆ V called terminals, and an integer k ≥ ∣X∣, the objective is to find a minimum weight set of edges whose removal results in k disconnected components, each of which contains at least one terminal. We give two approximation algorithms for the problem: a greedy (2 - ... )-approximation based on Gomory-Hu trees, and a (2 - ... )- approximation based on rounding a linear program. We use the insight from the rounding to develop an exact bidirected formulation for the global minimum cut problem (the k-cut problem with k = 2). [ABSTRACT FROM AUTHOR]

We develop an algorithm framework for isomorph-free exhaustive generation of designs admitting a group of automorphisms from a prescribed collection of pairwise nonconjugate groups, where each prescribed group has a large index relative to its normalizer in the isomorphism-inducing group. We demonstrate the practicality of the framework by producing a complete classification of the Steiner triple systems of order $21$ admitting a nontrivial automorphism group. The number of such pairwise nonisomorphic designs is $62336617$, where $958$ of the designs are anti-Pasch. We also develop consistency checking methodology for gaining confidence in the correct operation of the algorithm implementation. [ABSTRACT FROM AUTHOR]

Let M be a matroid defined by an independence oracle on ground set S, and let A ⊆ S. We present an incremental polynomial-time algorithm for enumerating all minimal (maximal) subsets of S which span (do not span) A. Special cases of these problems include the generation of bases, circuits, hyperplanes, flats of given rank, circuits through a given element, generalized Steiner trees, and multiway cuts in graphs, as well as some other applications. We also consider some tractable and NP-hard generation problems related to systems of polymatroid inequalities and (generalized) packing and spanning in matroids. [ABSTRACT FROM AUTHOR]

A Steiner quadruple system of order v, denoted by SQS(v), is a pair $(X,{\cal B}),$ where X is a v-set of points and ${\cal B}$ is a set of 4-subsets of X, called blocks, with the property that every 3-subset of X is contained in exactly one block of ${\cal B}$. An SQS(v) is resolvable if its block set can be partitioned into parallel classes. In 1987, Hartman showed that the necessary condition $v\equiv 4$ or $8\ (\rm {mod}\ 12)$ for the existence of a resolvable SQS(v) is sufficient with 23 possible exceptions. In this paper, we construct resolvable SQS(v)s for the 23 undecided orders. [ABSTRACT FROM AUTHOR]

We present the problem of constructing roads of minimum total length to interconnect highways under the constraint that the roads can intersect each highway only at one point in a designated interval which is a line segment. We present a set of optimality conditions for the problem and show how to construct a solution to meet this set of optimality conditions. [ABSTRACT FROM AUTHOR]

Binary 1-perfect codes which give rise to partitions of the n-cube are presented. The 1-perfect partitions are characterized as homomorphic images of simple algebraic structures on Fn and are constructed starting from a particular case of a structure defined in Fn. A special property (so-called well-ordering) of STS(n) is given in such a way that for this kind of STS it is possible to define the algebraic structure we need in Fn and to construct 1-perfect partitions of the n-cube. These 1-perfect partitions give us a kind of 1-perfect code for which it is easy to do the coding and decoding. Furthermore, there exists a syndrome which allows us to perform error correction. We present systematic codes of length n = 15 and we give examples of how to do the coding, decoding, and error correction. [ABSTRACT FROM AUTHOR]

A full Steiner tree T for a given set of points P is defined to be linear if all Steiner points lie on one path called the trunk of T. A (nonfull) Steiner tree is linear if it is a degeneracy of a full linear Steiner tree. Suppose P is a simple polygonal line. Roughly speaking, T is similar to P if its trunk turns to the left or right when P does. P is a left-turn (or right-turn) polygonal spiral if it always turns to the left (or right) at its vertices. P is an infinite spiral if n tends to infinity. In this paper we first prove some results on nonminimal paths and the decomposition of Steiner minimal trees, and then, based on these results, we study the case in which an infinite spiral P has a Steiner minimal tree that is linear and similar to P itself. [ABSTRACT FROM AUTHOR]