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]