Convergence analysis and error estimates for a parallel algorithm for solving the Navier-Stokes equations

Summary. This paper is concerned with the analysis of the convergence and the derivation of error estimates for a parallel algorithm which is used to solve the incompressible Navier-Stokes equations. As usual, the main idea is to split the main differential operator; this allows to consider independently the two main difficulties, namely nonlinearity and incompressibility. The results justify the observed accuracy of related numerical results. Received April 20, 2001 / Revised version received May 21, 2001 / Published online March 8, 2002 RID="*" ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="*" ID="*" Partially supported by D.G.E.S. (Spain), Proyecto PB98–1134 RID="**" ID="**" Partially supported by D.G.E.S. (Spain), Proyecto PB96–0986 RID="**" ID="**" Partially supported by D.G.E.S. (Spain) Proyecto PB96–0986     

Large Cliques in -Free Graphs

Dedicated to the memory of Paul Erdős A graph is called -free if it contains no cycle of length four as an induced subgraph. We prove that if a -free graph has n vertices and at least edges then it has a complete subgraph of vertices, where depends only on . We also give estimates on and show that a similar result does not hold for H-free graphs––unless H is an induced subgraph of . The best value of is determined for chordal graphs. Received October 25, 1999 RID="*" ID="*" Supported by OTKA grant T029074. RID="**" ID="**" Supported by TKI grant stochastics@TUB and by OTKA grant T026203.     

The Erdős–Pósa Property for Odd Cycles in Highly Connected Graphs

Dedicated to the memory of Paul Erdős In [9] Thomassen proved that a -connected graph either contains k vertex disjoint odd cycles or an odd cycle cover containing at most 2k-2 vertices, i.e. he showed that the Erdős–Pósa property holds for odd cycles in highly connected graphs. In this paper, we will show that the above statement is still valid for 576k-connected graphs which is essentially best possible. Received November 17, 1999 RID="*" ID="*" This work was supported by a post-doctoral DONET grant. RID="†" ID="†" This work was supported by an NSF-CNRS collaborative research grant. RID="‡" ID="‡" This work was performed while both authors were visiting the LIRMM, Université de Montpellier II, France.     

On Bipartite Graphs with Linear Ramsey Numbers

Dedicated to the memory of Paul Erdős We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1. Received December 1, 1999 RID="*" ID="*" Supported by NSF grant DMS-9704114 RID="**" ID="**" Supported by KBN grant 2 P03A 032 16     

Locally Well-Dominated and Locally Independent Well-Dominated Graphs

 In this article we present characterizations of locally well-dominated graphs and locally independent well-dominated graphs, and a sufficient condition for a graph to be k-locally independent well-dominated. Using these results we show that the irredundance number, the domination number and the independent domination number can be computed in polynomial time within several classes of graphs, e.g., the class of locally well-dominated graphs. Received: September 13, 2001 Final version received: May 17, 2002 RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) RID="†" ID="†" Supported by RUTCOR RID="*" ID="*" Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093) 05C75, 05C69 Acknowledgments. The authors thank the referees for valuable suggestions.     

Buyer-seller exactness in the assignment game

In the assignment game framework, we try to identify those assignment matrices in which no entry can be increased without changing the core of the game. These games will be called buyer-seller exact games and satisfy the condition that each mixed-pair coalition attains the corresponding matrix entry in the core of the game. For a given assignment game, a unique buyer-seller exact assignment game with the same core is proved to exist. In order to identify this matrix and to provide a characterization of those assignment games which are buyer-seller exact in terms of the assignment matrix, attainable upper and lower core bounds for the mixed-pair coalitions are found. As a consequence, an open question posed in Quint (1991) regarding a canonical representation of a “45^o-lattice” by means of the core of an assignment game can now be answered. Received: March 2002/Revised version: January 2003 RID="*" ID="*"  Institutional support from research grants BEC 2002-00642 and SGR2001-0029 is gratefully acknowledged RID="**" ID="**"  The authors thank the referees for their comments     

Isosceles Triangles Determined by a Planar Point Set

 It is proved that, for any ɛ>0 and n>n ₀(ɛ), every set of n points in the plane has at most triples that induce isosceles triangles. (Here e denotes the base of the natural logarithm, so the exponent is roughly 2.136.) This easily implies the best currently known lower bound, , for the smallest number of distinct distances determined by n points in the plane, due to Solymosi–Cs. Tóth and Tardos. Received: February, 2002 Final version received: September 15, 2002 RID="*" ID="*" Supported by NSF grant CCR-00-86013, PSC-CUNY Research Award 63382-00-32, and OTKA-T-032452 RID="†" ID="†" Supported by OTKA-T-030059 and AKP 2000-78-21     

A primal all-integer algorithm based on irreducible solutions

 This paper introduces an exact primal augmentation algorithm for solving general linear integer programs. The algorithm iteratively substitutes one column in a tableau by other columns that correspond to irreducible solutions of certain linear diophantine inequalities. We prove that various versions of our algorithm are finite. It is a major concern in this paper to show how the subproblem of replacing a column can be accomplished effectively. An implementation of the presented algorithms is given. Computational results for a number of hard 0/1 integer programs from the MIPLIB demonstrate the practical power of the method. Received: April 23, 2001 / Accepted: May 2002 Published online: March 21, 2003 RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="*" ID="*" Supported by grants FKZ 0037KD0099 and FKZ 2495A/0028G of the Kultusministerium of Sachsen-Anhalt. RID="#" ID="#"Supported by a Gerhard-Hess-Preis and grant WE 1462 of the Deutsche Forschungsgemeinschaft, and by the European DONET program TMR ERB FMRX-CT98-0202. Mathematics Subject Classification (1991): 90C10     

Vertex operator algebras,generalized doubles and dual pairs

Let V be a simple vertex operator algebra and G a finite automorphism group. Then there is a natural right G-action on the set of all inequivalent irreducible V-modules. Let be a finite set of inequivalent irreducible V-modules which is closed under the action of G. There is a finite dimensional semisimple associative algebra for a suitable 2-cocycle naturally determined by the G-action on such that and the vertex operator algebra form a dual pair on the sum of V-modules in in the sense of Howe. In particular, every irreducible V-module is completely reducible -module. Received: 10 September, 2001 / Published online: 29 April 2002 RID="*" ID="*" Supported by NSF grants and a research grant from the Committee on Research, UC Santa Cruz. RID="**" ID="**" Supported by DPST grant from government of Thailand.     

On the structure of rotation-invariant semigroups

 We generalize the notions of Girard algebras and MV-algebras by introducing rotation-invariant semigroups. Based on a geometrical characterization, we present five construction methods which result in rotation-invariant semigroups and in particular, Girard algebras and MV-algebras. We characterize divisibility of MV-algebras, and point out that integrality of Girard algebras follows from their other axioms. Received: 7 January 2002 / Revised version: 4 April 2002 / Published online: 19 December 2002 RID="*" ID="*" Supported by the National Scientific Research Fund Hungary (OTKA F/032782). Mathematics Subject Classification (2000): 20M14, 06F05 Key words or phrases: Residuated lattice – Conjunction for non-classical logics     

Error bounds for minimal energy bivariate polynomial splines

Summary. We derive error bounds for bivariate spline interpolants which are calculated by minimizing certain natural energy norms. Received March 28, 2000 / Revised version received June 23, 2000 / Published online March 8, 2002 RID="*" ID="*" Supported by the National Science Foundation under grant DMS-9870187 RID="**" ID="**" Supported by the National Science Foundation under grant DMS-9803340 and by the Army Research Office under grant DAAD-19-99-1-0160     

On the Oka principle in a Banach space,I

 Let X be a complex Banach space with a countable unconditional basis, Ω⊂X pseudoconvex open, G a complex Banach Lie group. We show that a Runge–type approximation hypothesis on X, G (which we also prove for G a solvable Lie group) implies that any holomorphic cocycle on Ω with values in G can be resolved holomorphically if it can be resolved continuously. Received: 1 March 2002 / Published online: 28 March 2003 Mathematics Subject Classification (2000): 32L05, 32E30, 46G20 RID="*" ID="*" Kedves Szímuskának. RID="*" ID="*" To my dear Wife.     

Intersecting Curves in the Plane

 We prove that for every family of n pairwise intersecting simple closed planar curves in general position, at least (4/5)n ²−O(n) points lie on more than one curve. This improves the previous lower bound of (3/4)n ²−O(n) due to Richter and Thomassen. Received: March 29, 2000 Final version received: August 30, 2001 RID="*" ID="*" Research supported in part by NSF grant DMS-9970325 Acknowledgments. I thank Bruce Richter for informing me about this problem, Gelasio Salazar for reading a preliminary version of the paper, and a Referee for useful comments. Current Address: Microsoft Research, One Microsoft Way, Redmond, WA 98052-6399, USA. e-mail: mubayi@microsoft.com 1991 Mathematics Subject Classification. 05C35, 52C10     

Homotopy equivalences of p-completed classifying spaces of finite groups

We study homotopy equivalences of p-completions of classifying spaces of finite groups. To each finite group G and each prime p, we associate a finite category ℒ _p ^c (G) with the following properties. Two p-completed classifying spaces BG _p ^∧ and BG’ _p ^∧ have the same homotopy type if and only if the associated categories ℒ _p ^c (G) and ℒ _p ^c (G’) are equivalent. Furthermore, the topological monoid Aut(BG _p ^∧) of self equivalences is determined by the self equivalences of the associated category ℒ _p ^c (G). Oblatum 5-VII-2001 & 28-VIII-2002?Published online: 8 November 2002 RID="*" ID="*"C. Broto is partially supported by DGICYT grant PB97–0203. RID="**" ID="**"R. Levi is partially supported by EPSRC grant GR/M7831. RID="***" ID="***"B. Oliver is partially supported by UMR 7539 of the CNRS.     

Simple and immune relations on countable structures

 Let 𝒜 be a computable structure and let R be a new relation on its domain. We establish a necessary and sufficient condition for the existence of a copy ℬ of 𝒜 in which the image of R (?R, resp.) is simple (immune, resp.) relative to ℬ. We also establish, under certain effectiveness conditions on 𝒜 and R, a necessary and sufficient condition for the existence of a computable copy ℬ of 𝒜 in which the image of R (?R, resp.) is simple (immune, resp.). Received: 4 February 2001 Published online: 5 November 2002 RID="*" ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899. RID="*" ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899. RID="*" ID="*" The first three authors gratefully acknowledge support of the NFS Binational Grant DMS-0075899.     

Pathwidth of Planar and Line Graphs

 We prove that for every 2-connected planar graph the pathwidth of its geometric dual is less than the pathwidth of its line graph. This implies that pathwidth(H)≤ pathwidth(H ^*)+1 for every planar triangulation H and leads us to a conjecture that pathwidth(G)≤pathwidth(G ^*)+1 for every 2-connected graph G. Received: May 8, 2001 Final version received: March 26, 2002 RID="*" ID="*" I acknowledge support by EC contract IST-1999-14186, Project ALCOM-FT (Algorithms and Complexity - Future Technologies) and support by the RFBR grant N01-01-00235. Acknowledgments. I am grateful to Petr Golovach, Roland Opfer and anonymous referee for their useful comments and suggestions.