关于不含k-C-圈的n阶r-一致超图的若干结果

主要讨论了不含k-C-圈的n阶r-一致超图,对不同的k,分别得出了它的极大边数的一个下界,并且得出在有些情况下它的下界是最大的.另外,我们得到了Krn含k-C-圈的一个充分必要条件.     

On Ramsey numbers of uniform hypergraphs with given maximum degree

For every ?>0 and every positive integers Δ and r, there exists C=C(?,Δ,r) such that the Ramsey number, R(H,H) of any r-uniform hypergraph H with maximum degree at most Δ is at most C|V(H)|^1+?.     

Coloring mixed hypertrees

A mixed hypergraph is a triple (V,C,D) where V is its vertex set and C and D are families of subsets of V, called C-edges and D-edges, respectively. For a proper coloring, we require that each C-edge contains two vertices with the same color and each D-edge contains two vertices with different colors. The feasible set of a mixed hypergraph is the set of all k's for which there exists a proper coloring using exactly k colors. A hypergraph is a hypertree if there exists a tree such that the edges of the hypergraph induce connected subgraphs of the tree.We prove that feasible sets of mixed hypertrees are gap-free, i.e., intervals of integers, and we show that this is not true for precolored mixed hypertrees. The problem to decide whether a mixed hypertree can be colored by k colors is NP-complete in general; we investigate complexity of various restrictions of this problem and we characterize their complexity in most of the cases.     

Large Cross‐Free Sets in Steiner Triple Systems

A cross‐free set of size m in a Steiner triple system is three pairwise disjoint m‐element subsets such that no intersects all the three ‐s. We conjecture that for every admissible n there is an STS(n) with a cross‐free set of size which if true, is best possible. We prove this conjecture for the case , constructing an STS containing a cross‐free set of size 6k. We note that some of the 3‐bichromatic STSs, constructed by Colbourn, Dinitz, and Rosa, have cross‐free sets of size close to 6k (but cannot have size exactly 6k). The constructed STS shows that equality is possible for in the following result: in every 3‐coloring of the blocks of any Steiner triple system STS(n) there is a monochromatic connected component of size at least (we conjecture that equality holds for every admissible n). The analog problem can be asked for r‐colorings as well, if and is a prime power, we show that the answer is the same as in case of complete graphs: in every r‐coloring of the blocks of any STS(n), there is a monochromatic connected component with at least points, and this is sharp for infinitely many n.     

Recombination induced hypergraphs: A new approach to mutation-recombination isomorphism

Natural selection acts on genetic variation that comes from two principal sources: mutation and recombination. Because of the inherent differences between mutation and recombination, it is often assumed that they are qualitatively different ways to explore the genotype space. In this paper a new way of constructing recombination spaces is introduced and the topological features of the resulting hypergraphs are analyzed. It is shown that types which are neighbors in the point mutation space are also neighbors in the recombination space, i.e., mutation and recombination spaces are homomorphic. This implies that the shapes of the fitness functions explored by mutation and recombination are similar. However, the potential of one- and two-point recombination operators to explore the fitness landscape may differ dramatically from uniform recombination operators or mutation operators because of the limited number of recombinant types they can produce. © 1996 John Wiley & Sons, Inc.     

A Solution to a Problem of Jacobson,Kézdy and Lehel

We solve a problem proposed by Jacobson, Kézdy, and Lehel [4] concerning the existence of forbidden induced subgraph characterizations of line graphs of linear k-uniform hypergraphs with sufficiently large minimal edge-degree. Actually, we prove that for each k3 there is a finite set Z(k) of graphs such that each graph G with minimum edge-degree at least 2k²–3k+1 is the line graph of a linear k-uniform hypergraph if and only if G is a Z(k)-free graph.Acknowledgments. We thank the anonymous referees, whose suggestions helped to improve the presentation of the paper.Winter 2002/2003 DIMACS Award is gratefully acknowledged2000 Mathematics Subject Classification: 05C65 (05C75, 05C85)