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     

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)).     

A Lower Bound for the Rectilinear Crossing Number

We give a new lower bound for the rectilinear crossing number of the complete geometric graph K_n. We prove that and we extend the proof of the result to pseudolinear drawings of K_n. Dedicated to the memory of our good friend and mentor Víctor Neumann-Lara. Received: April, 2003 Final version received: March 18, 2005     

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     

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.     

On a Hypergraph Matching Problem

Let H = (V, E) be an r-uniform hypergraph and let A matching M of H is (α, )-perfect if for each F ∈ , at least α|F| vertices of F are covered by M. Our main result is a theorem giving sufficient conditions for an r-uniform hypergraph to have a -perfect matching. As a special case of our theorem we obtain the following result. Let K(n, r) denote the complete r-uniform hypergraph with n vertices. Let t and r be fixed positive integers where t≥r≥2. Then, K(n, r) can be packed with edge-disjoint copies of K(t, r) such that each vertex is incident with only o(n ^{r ?1}) unpacked edges. This extends a result of Rödl [9].     

Orthogonal Double Covers of Complete Graphs by Caterpillars of Diameter 5

An orthogonal double cover (ODC) of the complete graph K_n by a graph G is a collection = {G_i|i = 1,2, . . . ,n} of spanning subgraphs of K_n, all isomorphic to G, with the property that every edge of K_n belongs to exactly two members of and any two distinct members of share exactly one edge. A caterpillar of diameter five is a tree arising from a path with six vertices by attaching pendant vertices to some or each of its vertices of degree two. We show that for any caterpillar of diameter five there exists an ODC of the complete graph K_n.     

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.     

Courbes nodales et ramification sauvage virtuelle

Let S be the spectrum of a discrete valuation ring of residue characteristic p>0. Let Z be a scheme separated and of finite type over S, and denote by K_c(Z,) (l≠p) the Grothendieck group of -constructible sheaves on the etale site of Z. In this article, we introduce the subgroup of virtual sheaves with virtual wild ramification zero, and we prove that this subgroup is preserved by the formalism of six operations “à la Grothendieck”.     

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.     

Fonctions plurisousharmoniques et courants positifs de type (1,1) sur une variété presque complexe

If (X, J) is an almost complex manifold, then a function u is said to be plurisubharmonic on X if it is upper semi-continuous and its restriction to every local pseudo-holomorphic curve is subharmonic. As in the complex case, it is conjectured that plurisubharmonicity is equivalent to the positivity of the (1,1)-current , (the (1,1)-current need not be closed here!). The conjecture is trivial if u is of class The result is elementary in the complex integrable case because the operator can be written as an operator with constant coefficients in complex coordinates. Hence the positivity of the current is preserved by regularising with usual convolution kernels. This is not possible in the almost complex non integrable case and the proof of the result requires a much more intrinsic study. In this chapter we prove the necessity of the positivity of the (1,1)-current . We prove also the sufficiency of the positivity in the particular case of an upper semi-continuous function f which is continuous in the complement of the singular locus f⁻¹(−∞).

---

Résume Une fonction semi-continue supérieurement u sur une variété presque complexe (X, J) est dite plurisousharmonique si la restriction à toute courbe pseudo-holomorphe locale est sous-harmonique. Comme dans le cas analytique complexe, nous conjecturons que la notion de plurisousharmonicité pour une fonction u est équivalente à la positivité du (1,1)-courant , (lequel n'est pas forcément fermé dans le cas non intégrable). La conjecture est triviale dans le cas d'une fonction u de classe Le résultat en question est élémentaire dans le cas complexe intégrable car l'opérateur s'écrit comme un opérateur à coefficients constants dans des coordonnées complexes. On peut donc facilement conserver la positivité du courant en régularisant avec des noyaux usuels. Dans le cas presque complexe non intégrable ceci ce n'est pas possible et la preuve du résultat exige un étude beaucoup plus intrinsèque. Nous montrons la nécessité de la positivité du (1,1)-courant en utilisant la théorie locale des courbes J-holomorphes. Nous montrons aussi la suffisance de la positivité dans le cas particulier d'une fonction f semi-continue supérieurement et continue en dehors du lieu singulier f⁻¹(−∞).

     

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.     

Constructions of Quad-Rooted Double Covers

A collection of spanning subgraphs of K_n is called an orthogonal double cover if (i) every edge of K_n belongs to exactly two of the G_is and (ii) any two distinct G_is intersect in exactly one edge. Chung and West [3] conjectured that there exists an orthogonal double cover of K_n for all n, in which each G_i has maximum degree 2, and proved this result for n in six of the residue classes modulo 12. In [6], Gronau, Mullin and Schellenberg solved the conjecture. In addition to solving the conjecture, they went on to consider a problem for n 5 mod 6 such that each spanning subgraph G_i consists of the vertex-disjoint union of an isolated vertex, a quadrilateral, and triangles. They proved that for any n 2 mod 3 and n {8, 11, 38, 41, 44, 47, 50, 53, 59, 62, 71, 83, 86, 89, 95, 101, 107, 113, 122, 131, 143, 146, 149, 158, 164, 167, 173, 176, 179, 218, 242, 248, 287}, there exists a quad-rooted double cover of order n. In this note, we improve their result by showing that such designs exist for any n 2 mod 3 and n {8, 11, 38, 41, 44, 50, 53, 62, 71}.     

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.     

Canonical Pattern Ramsey Numbers

A color pattern is a graph whose edges have been partitioned into color classes. A family of color patterns is a Ramsey family provided there is some sufficiently large integer N such that in any edge coloring of the complete graph K_N there is an (isomorphic) copy of at least one of the patterns from . The smallest such N is the Ramsey number of the family . The classical Canonical Ramsey theorem of Erds and Rado asserts that the family of color patterns is a Ramsey family if it consists of monochromatic, rainbow (totally multicolored) and lexically colored complete graphs. In this paper we treat the asymmetric case by studying the Ramsey number of families containing a rainbow triangle, a lexically colored complete graph and a fixed arbitrary monochromatic graph. In particular we give asymptotically tight bounds for the Ramsey number of a family consisting of rainbow and monochromatic triangle and a lexically colored K_N. Among others, we prove some canonical Ramsey results for cycles.     

Bipartite Subgraphs and Quasi-Randomness

We say that a family of graphs is p-quasi-random, 0<p<1, if it shares typical properties of the random graph G(n,p); for a definition, see below. We denote by the class of all graphs H for which and the number of not necessarily induced labeled copies of H in G_n is at most (1+o(1))p^e(H)n^v(H) imply that is p-quasi-random. In this note, we show that all complete bipartite graphs K_a,b, a,b2, belong to for all 0<p<1.Acknowledgments We would like to thank Andrew Thomason for fruitful discussions and Yoshi Kohayakawa for organizing Extended Workshop on Combinatorics in eq5 Paulo, Ubatuba, and Rio de Janeiro, where a part of this work was done. We also thank the referees for their careful work.The first author was partially supported by NSF grant INT-0072064The second author was partially supported by NSF grants DMS-9970622, DMS-0301228 and INT-0072064Final version received: October 24, 2003     

On Chow and Brauer groups of a product of Mumford curves

Let C₁,···,C_d be Mumford curves defined over a finite extension of and let X=C₁×···×C_d. We shall show the following: (1) The cycle map CH₀(X)/n → H^2d(X, μ_n^⊗d) is injective for any non-zero integer n. (2) The kernel of the canonical map CH₀(X)→Hom(Br(X),) (defined by the Brauer-Manin pairing) coincides with the maximal divisible subgroup in CH₀(X).     

Global -homotopy with <Emphasis Type="Italic">C</Emphasis><Superscript><Emphasis Type="Italic">k</Emphasis></Superscript> estimates for a family of compact,regular <Emphasis Type="Italic">q</Emphasis>-pseudoconcave CR manifolds

Let M₀ be a compact, regular q-pseudoconcave CR submanifold of a complex manifold G and - a holomorphic vector bundle on G such that dim for some fixed r<q. We prove a global homotopy formula with C^k estimates for r-cohomology of on arbitrary CR submanifold M close enough to M₀.Mathematics Subject Classification (2000):32F20, 32F10in final form: 15 October 2003     

Order and algebra isomorphisms of spaces of regular operators

If E and F are real Banach lattices and there is an algebra and order isomorphism Φ:(E) →(F) between their respective ordered Banach algebras of regular operators then there is a linear order isomorphism U:E→F such that Φ(T) =UTU⁻¹ for all T ∈ (E).