A Five Color Zero-Sum Generalization

Let g_zs(m, 2k) (g_zs(m, 2k+1)) be the minimal integer such that for any coloring Δ of the integers from 1, . . . , g_zs(m, 2k) by (the integers from 1 to g_zs(m, 2k+1) by ) there exist integers such that 1. there exists j_x such that Δ(x_i) ∈ for each i and ∑_i=1^m Δ(x_i) = 0 mod m (or Δ(x_i)=∞ for each i); 2. there exists j_y such that Δ(y_i) ∈ for each i and ∑_i=1^m Δ(y_i) = 0 mod m (or Δ(y_i)=∞ for each i); and 1. 2(x_m−x₁)≤y_m−x₁. In this note we show g_zs(m, 2)=5m−4 for m≥2, g_zs(m, 3)=7m+−6 for m≥4, g_zs(m, 4)=10m−9 for m≥3, and g_zs(m, 5)=13m−2 for m≥2. Supported by NSF grant DMS 0097317     

On Resolvable Multipartite G-Designs II

In this paper, it has been proved that and are factorable, where ⊗ denotes wreath product of graphs. As a consequence, a resolvable (k,n,k,2λ) multipartite –design exists for even k. These results generalize the results of Ushio on –factorizations of complete tripartite graphs.     

On the Circumference of 3-Connected Quasi-Claw-Free Graphs

A graph G is quasi-claw-free if it satisfies the property: d(x,y)=2 ⇒ there exists such that . In the paper, we prove that the circumference of a 3-connected quasi-claw-free graph G on n vertices is at least min{4δ−2,n} and G is hamiltonian if n≤5δ−5.     

Minimal Connected τ-Critical Hypergraphs

A hypergraph is τ-critical if τ(−{E})<τ() for every edge E ∈ , where τ() denotes the transversal number of . We show that if is a connected τ-critical hypergraph, then −{E} can be partitioned into τ()−1 stars of size at least two, for every edge E ∈ . An immediate corollary is that a connected τ-critical hypergraph has at least 2τ()−1 edges. This extends, in a very natural way, a classical theorem of Gallai on colour-critical graphs, and is equivalent to a theorem of Füredi on t-stable hypergraphs. We deduce a lower bound on the size of τ-critical hypergraphs of minimum degree at least two.     

A Degree Constraint for Uniquely Hamiltonian Graphs

A graph, G, is called uniquely Hamiltonian if it contains exactly one Hamilton cycle. We show that if G=(V, E) is uniquely Hamiltonian then Where #(G)=1 if G has even number of vertices and 2 if G has odd number of vertices. It follows that every n-vertex uniquely Hamiltonian graph contains a vertex whose degree is at most c log₂n+2 where c=(log₂3−1)⁻¹≈1.71 thereby improving a bound given by Bondy and Jackson [3].     

New Local Conditions for a Graph to be Hamiltonian

For a vertex w of a graph G the ball of radius 2 centered at w is the subgraph of G induced by the set M₂(w) of all vertices whose distance from w does not exceed 2. We prove the following theorem: Let G be a connected graph where every ball of radius 2 is 2-connected and d(u)+d(v)≥|M₂(w)|−1 for every induced path uwv. Then either G is hamiltonian or for some p≥2 where ∨ denotes join. As a corollary we obtain the following local analogue of a theorem of Nash-Williams: A connected r-regular graph G is hamiltonian if every ball of radius 2 is 2-connected and for each vertex w of G. Supported by the Swedish Research Council (VR)     

3-Wise Exactly 1-Intersecting Families of Sets

Let f(l, t, n) be the maximal size of a family such that any l2 sets of have an exactly t1-element intersection. If l3, it trivially comes from [8] that the optimal families are trivially intersecting (there is a t-element core contained by all the members of the family). Hence it is easy to determine Let g(l,t,n) be the maximal size of an l-wise exaclty t-intersecting family that is not trivially t-intersecting. We give upper and lower bounds which only meet in the following case: g(3, 1, n) = n^2/3(1 + o(1)).     

On the Intersection Problem for Steiner Triple Systems of Different Orders

A Steiner triple system of order v, or STS(v), is a pair (V, ) with V a set of v points and a set of 3-subsets of V called blocks or triples, such that every pair of distinct elements of V occurs in exactly one triple. The intersection problem for STS is to determine the possible numbers of blocks common to two Steiner triple systems STS(u), (U, ), and STS(v), (V, ), with U⊆V. The case where U=V was solved by Lindner and Rosa in 1975. Here, we let U⊂V and completely solve this question for v−u=2,4 and for v≥2u−3. supported by NSERC research grant #OGP0170220. supported by NSERC postdoctoral fellowship. supported by NSERC research grant #OGP007621.     

-Decompositions of and D v ∪P where P is a 2-Regular Subgraph of D v

In this paper, we extend the study of C₄-decompositions of the complete graph with 2-regular leaves and paddings to directed versions. Mainly, we prove that if P is a vertex-disjoint union of directed cycles in a complete digraph D_v, then and D_v∪P can be decomposed into directed 4-cycles, respectively, if and only if v(v−1)−|E(P)|≡0(mod 4) and v(v−1)+|E(P)|≡0(mod 4) where |E(P)| denotes the number of directed edges of P, and v≥8.     

The Maximum Size of 3-Wise Intersecting and 3-Wise Union Families

Let be an n-uniform hypergraph on 2n vertices. Suppose that and holds for all F₁,F₂,F₃ ∈ . We prove that the size of is at most . The second author was supported by MEXT Grant-in-Aid for Scientific Research (B) 16340027     

Largest Non-Unique Subgraphs

The reduction number r(G) of a graph G is the maximum integer m≤|E(G)| such that the graphs G−E, E⊆E(G),|E|≤m, are mutually non-isomorphic, i.e., each graph is unique as a subgraph of G. We prove that and show by probabilistic methods that r(G) can come close to this bound for large orders. By direct construction, we exhibit graphs with large reduction number, although somewhat smaller than the upper bound. We also discuss similarities to a parameter introduced by Erdős and Rényi capturing the degree of asymmetry of a graph, and we consider graphs with few circuits in some detail. Supported by a grant from the Danish Natural Science Research Council.     

Partition of Triples of Order 6k+5 into 6k+3 Optimal Packings and One Packing of Size 8k+4

A (2,3)-packing on X is a pair (X,), where is a set of 3-subsets (called blocks) of X, such that any pair of distinct points from X occurs together in at most one block. For a (6k+5)-set X, an optimal partition of triples (denoted by OPT(6k+5)) is a set of 6k+3 optimal (2,3)-packings and a (2,3)-packing of size 8k+4 on X. Etzion conjectured that there exists an OPT(6k+5) for any positive integer k. In this paper, we construct such a system for any k≥1. This complete solution is based on the known existence results of S(3,4,v)s by Hanani and that of special S(3,{4,6},6m)s by Mills. Partitionable candelabra systems also play an important role together with an OPT(11) and a holey OPT(11). Research supported by Natural Science Foundation of Universities of Jiangsu Province under Grant 05KJB110111     

A lower bound for the worst-case cubature error on spheres of arbitrary dimension

This paper is concerned with numerical integration on the unit sphere S^r of dimension r≥2 in the Euclidean space ℝ^r+1. We consider the worst-case cubature error, denoted by E(Q_m;H^s(S^r)), of an arbitrary m-point cubature rule Q_m for functions in the unit ball of the Sobolev space H^s(S^r), where s>, and show that The positive constant c_s,r in the estimate depends only on the sphere dimension r≥2 and the index s of the Sobolev space H^s(S^r). This result was previously only known for r=2, in which case the estimate is order optimal. The method of proof is constructive: we construct for each Q_m a `bad' function f_m, that is, a function which vanishes in all nodes of the cubature rule and for which Our proof uses a packing of the sphere S^r with spherical caps, as well as an interpolation result between Sobolev spaces of different indices.     

A Note on a Packing Problem in Transitive Tournaments

Let TT_n be a transitive tournament on n vertices. We show that for any directed acyclic graph G of order n and of size not greater than two directed graphs isomorphic to G are arc disjoint subgraphs of TT_n. Moreover, this bound is generally the best possible. The research partially supported by KBN grant 2 P03A 016 18     

On the existence of a crepant resolution of some moduli spaces of sheaves on an abelian surface

Let J be an abelian surface with a generic ample line bundle . For n≥1, the moduli space M_J(2,0,2n) of (1)-semistable sheaves F of rank 2 with Chern classes c₁(F)=0, c₂(F)=2n is a singular projective variety, endowed with a holomorphic symplectic structure on the smooth locus. In this paper, we show that there does not exist a crepant resolution of M_J(2,0,2n) for n≥2. This certainly implies that there is no symplectic desingularization of M_J(2,0,2n) for n≥2. Jaeyoo Choy was partially supported by KRF 2003-070-C00001 Young-Hoon Kiem was partially supported by a KOSEF grant R01-2003-000-11634-0.     

Reconstructing under Group Actions

We give a bound on the reconstructibility of an action GX in terms of the reconstructibility of a the action NX, where N is a normal subgroup of G, and the reconstructibility of the quotient G/N. We also show that if the action GX is locally finite, in the sense that every point is either in an orbit by itself or has finite stabilizer, then the reconstructibility of GX is at most the reconstructibility of G. Finally, we give some applications to geometric reconstruction problems.     

Alternating Paths along Axis-Parallel Segments

It is shown that for a set S of n pairwise disjoint axis-parallel line segments in the plane there is a simple alternating path of length . This bound is best possible in the worst case. In the special case that the n pairwise disjoint axis-parallel line segments are protruded (that is, if the intersection point of the lines through every two nonparallel segments is not visible from both segments), there is a simple alternating path of length n. Work on this paper was partially supported by National Science Foundation grants CCR-0049093 and IIS-0121562. A preliminary version of this paper has appeared in the Proceedings of the 8th International Workshop on Algorithms and Data Structures (Ottawa, ON, 2003), vol. 2748 of Lecture Notes on Computer Science, Springer, Berlin, 2003, pp. 389–400.     

Extremal Problems for Imbalanced Edges

Albertson [2] has introduced the imbalance of an edge e=uv in a graph G as |d_G(u)−d_G(v)|. If for a graph G of order n and size m the minimum imbalance of an edge of G equals d, then our main result states that with equality if and only if G is isomorphic to We also prove best-possible upper bounds on the number of edges uv of a graph G such that |d_G(u)−d_G(v)|≥d for some given d.     

Consistent Cycles in Graphs and Digraphs

Let Γ be a finite digraph and let G be a subgroup of the automorphism group of Γ. A directed cycle of Γ is called G-consistent whenever there is an element of G whose restriction to is the 1-step rotation of . Consistent cycles in finite arc-transitive graphs were introduced by J. H. Conway in his public lectures at the Second British Combinatorial Conference in 1971. He observed that the number of G-orbits of G-consistent cycles of an arc-transitive group G is precisely one less than the valency of the graph. In this paper, we give a detailed proof of this result in a more general setting of arbitrary groups of automorphisms of graphs and digraphs. Supported in part by ``Ministrstvo za šolstvo, znanost in šport Republike Slovenije', bilateral project BI-USA/04-05/38.     

Large Vertex-Disjoint Cycles in a Bipartite Graph

Let s≥2 and k be two positive integers. Let G=(V ₁,V ₂;E) be a bipartite graph with |V ₁|=|V ₂|=n≥s k and the minimum degree at least (s−1)k+1. When s=2 and n >2k, it is proved in [5] that G contains k vertex-disjoint cycles. In this paper, we show that if s≥3, then G contains k vertex-disjoint cycles of length at least 2s. Received: March 2, 1998 Revised: October 26, 1998