On the critical point‐arboricity graphs

In this paper, we study the critical point‐arboricity graphs. We prove two lower bounds for the number of edges of k‐critical point‐arboricity graphs. A theorem of Kronk is extended by proving that the point‐arboricity of a graph G embedded on a surface S with Euler genus g = 2, 5, 6 or g ≥ 10 is at most with equality holding iff G contains either K_2k?1 or K_2k?4 + C₅ as a subgraph. It is also proved that locally planar graphs have point‐arboricity ≤ 3 and that triangle‐free locally planar‐graphs have point‐arboricity ≤ 2. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 50–61, 2002     

On the combinatorics of the graph-complexSur la combinatoire du complexe de graphes

In their recent preprint [3] Kontsevich and Shoikhet have introduced two graph-complexes: the complex on the even (resp. odd) space in order to study the cohomology of the Lie algebra Ham₀ (resp. Ham₀^odd) of Hamiltonian vector fields vanishing at the origin on the infinite-dimensional even (resp. odd) space. We construct an isomorphism between those two graph-complexes, proving in particular that their cohomologies coincide. This solves a problem posed by Shoikhet. To cite this article: B. Lass, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 1–6     

Continuous time vertex-reinforced jump processes

 We study the continuous time integer valued process , which jumps to each of its two nearest neighbors at the rate of one plus the total time the process has previously spent at that neighbor. We show that the proportion of the time before t which this process spends at integers j converges to positive random variables V _j , which sum to one, and whose joint distribution is explicitly described. We also show Received: 19 December 2000 / Revised version: 1 November 2001 / Published online: 17 May 2002     

Topological recursive relations in H2g(ℳg,n)

We show that any degree at least g monomial in descendant or tautological classes vanishes on ℳ _g,n when g≥2. This generalizes a result of Looijenga and proves a version of Getzler’s conjecture. The method we use is the study of the relative Gromov-Witten invariants of ℙ¹ relative to two points combined with the degeneration formulas of [IP1]. Oblatum 24-X-2000 & 14-XI-2001?Published online: 18 February 2002     

Some remarks about leaf roots

Nishimura et al. [On graph powers for leaf-labeled trees, J. Algorithms 42 (2002) 69-108] define a k-leaf root of a graph G=(V_G,E_G) as a tree T=(V_T,E_T) such that the vertices of G are exactly the leaves of T and two vertices in V_G are adjacent in G if and only if their distance in T is at most k. Solving a problem posed by Niedermeier [Personal communication, May 2004] we give a structural characterization of the graphs that have a 4-leaf root. Furthermore, we show that the graphs that have a 3-leaf root are essentially the trees, which simplifies a characterization due to Dom et al. [Error compensation in leaf power problems, Algorithmica 44 (2006) 363-381. (A preliminary version appeared under the title “Error compensation in leaf root problems”, in: Proceedings of the 15th Annual International Symposium on Algorithms and Computation (ISAAC 2004), Lecture Notes in Computer Science, vol. 3341, pp. 389-401)] and also a related recognition algorithm due to Nishimura et al. [On graph powers for leaf-labeled trees, J. Algorithms 42 (2002) 69-108].     

Stochastic integration with respect to q Brownian motion

 We develop a stochastic integration with respect to a q-Brownian motion (for ), i.e. a non commutative process where the operator a _t and its adjoint fulfill the q commutation relation ; under the vacuum state expectation. We show that this process enjoys a predictable representation type property. Received: 15 February 2002 / Revised version: 25 May 2002 / Published online: 30 September 2002 Mathematics Subject Classification (2000): 60H05, 46L50, 81S25     

Recursive constructions for triangulations

Three recursive constructions are presented; two deal with embeddings of complete graphs and one with embeddings of complete tripartite graphs. All three facilitate the construction of 2) non‐isomorphic face 2‐colourable triangulations of K_n and K_n,n,n in orientable and non‐orientable surfaces for values of n lying in certain residue classes and for appropriate constants a. © 2002 John Wiley & Sons, Inc. J Graph Theory 39: 87–107, 2002     

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     

Large components in r‐edge‐colorings of Kn have diameter at most five

Reflecting on problems posed by Gyárfás [Ramsey Theory Yesterday, Today and Tomorrow, Birkhäuser, Basel, 2010, pp. 77–96] and Mubayi [Electron J Combin 9 (2002), #R42], we show in this note that every r‐edge‐coloring of K_n contains a monochromatic component of diameter at most five on at least n/(r?1) vertices. Copyright © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 337–340, 2012     

Double coverings of 2‐paths by Hamilton cycles*

A double Dudeney set in K_n is a multiset of Hamilton cycles in K_n having the property that each 2‐path in K_n lies in exactly two of the cycles. A double Dudeney set in K_n has been constructed when n ≥ 4 is even. In this paper, we construct a double Dudeney set in K_n when n ≥ 3 is odd. © 2002 Wiley Periodicals, Inc. J Combin Designs 10: 195–206, 2002; Published online in Wiley InterScience ( www.interscience.wiley.com ) DOI 10.1002/jcd.10003     

K-theoretic invariants for Floer homology

This paper defines two K-theoretic invariants, Wh ₁ and Wh ₂, for individual and one-parameter families of Floer chain complexes. The chain complexes are generated by intersection points of two Lagrangian submanifolds of a symplectic manifold, and the boundary maps are determined by holomorphic curves connecting pairs of intersection points. The paper proves that Wh ₁ and Wh ₂ do not depend on the choice of almost complex structures and are invariant under Hamiltonian deformations. The proof of this invariance uses properties of holomorphic curves, parametric gluing theorems, and a stabilization process. Submitted: April 2001, Revised: December 2001, Final version: February 2002.     

Hamilton cycles in plane triangulations

We extend Whitney's Theorem that every plane triangulation without separating triangles is hamiltonian by allowing some separating triangles. More precisely, we define a decomposition of a plane triangulation G into 4‐connected ‘pieces,’ and show that if each piece shares a triangle with at most three other pieces then G is hamiltonian. We provide an example to show that our hypothesis that each piece shares a triangle with at most three other pieces' cannot be weakened to ‘four other pieces.’ As part of our proof, we also obtain new results on Tutte cycles through specified vertices in planar graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 138–150, 2002     

Convex‐round graphs are circular‐perfect

We show a connection between two concepts that have hitherto been investigated separately, namely convex‐round graphs and circular cliques. The connections are twofold. We prove that the circular cliques are precisely the cores of convex‐round graphs; this implies that convex‐round graphs are circular‐perfect, a concept introduced recently by Zhu [10]. Secondly, we characterize maximal K_r‐free convex‐round graphs and show that they can be obtained from certain circular cliques in a simple fashion. Our proofs rely on several structural properties of convex‐round graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 182–194, 2002     

Hamiltonian cycles in n‐extendable graphs

A graph G of order at least 2n+2 is said to be n‐extendable if G has a perfect matching and every set of n independent edges extends to a perfect matching in G. We prove that every pair of nonadjacent vertices x and y in a connected n‐extendable graph of order p satisfy deg_G x+deg_G y ≥ p ? n ? 1, then either G is hamiltonian or G is isomorphic to one of two exceptional graphs. © 2002 Wiley Periodicals, Inc. J Graph Theory 40: 75–82, 2002     

Universes in metapredicative analysis

 In this paper we introduce theories of universes in analysis. We discuss a non-uniform, a uniform and a minimal variant. An analysis of the proof-theoretic bounds of these systems is given, using only methods of predicative proof-theory. It turns out that all introduced theories are of proof-theoretic strength between Γ₀ and ϕ1ɛ₀0. Received: 24 November 2000 / Revised Version: 14 June 2002 Published online: 10 October 2002 This paper is a part of the author's Ph.D. dissertation     

Two graphs without planar covers

In this note we prove that two specific graphs do not have finite planar covers. The graphs are K₇–C₄ and K_4,5–4K₂. This research is related to Negami's 1‐2‐∞ Conjecture which states “A graph G has a finite planar cover if and only if it embeds in the projective plane.” In particular, Negami's Conjecture reduces to showing that 103 specific graphs do not have finite planar covers. Previous (and subsequent) work has reduced these 103 to a few specific graphs. This paper covers 2 of the remaining cases. The sole case currently remaining is to show that K_2,2,2,1 has no finite planar cover. © 2002 Wiley Periodicals, Inc. J Graph Theory 41: 318–326, 2002     

Estimation du coefficient de régularité locale d'une trajectoire de processusEstimation of the local regularity index of a sample path

In this Note, we consider processes that satisfied a local Hölder condition with unknown coefficient γ₀. We study two families of estimators for γ₀: the first one based upon the whole sample path over [0,T_N], T_N↗∞, and the second one constructed with n observations at sampling rate δ_n, δ_n→0 and nδ_n→∞ as n→∞. For the almost sure convergence, we give the rates for these two families. To cite this article: D. Blanke, C. R. Acad. Sci. Paris, Ser. I 334 (2002) 145–148     

Some stable vector bundles with reducible theta divisor

 Let C be a curve of genus g and L a line bundle of degree 2g on C. Let M_L be the kernel of the evaluation map . We show that when L is general enough, the rank g bundle M_L and its exterior powers are stable, but admit a reducible theta divisor. Received: 16 September 2002 / Revised version: 29 October 2002 Published online: 14 February 2003 Mathematics Subject Classification (2000): 14H60     

On the number of singularities for the obstacle problem in two dimensions

We study the obstacle problem in two dimensions. On the one hand we improve a result of L.A. Caffarelli and N.M. Rivière: we state that every connected component of the interior of the coincidence set has at most N ₀ singular points, where N ₀ is only dependent on some geometric constants. Moreover, if the component is small enough, then this component has at most two singular points. On the other hand, we prove in a simple case a conjecture of D.G. Schaeffer on the generic regularity of the free boundary: for a family of obstacle problems in two dimensions continuously indexed by a parameter λ, the free boundary of the solution u_λ is analytic for almost every λ. Finally we present a new monotonicity formula for singular points. Dedicated to Henri Berestycki and Alexis Bonnet.