DIMACS Series in Discrete Mathematics and Theoretical Comput(10)

Abstract. The notion of relative closure (X, Y)0 of a semi-Pfaffian couple (X, Y) was introduced by Gabrielov to give a description of the o-minimal structure generated by Pfaffian functions. In this paper, an effective bound is given for the number of con

10ANDREIGABRIELOVANDTHIERRYZELL

3.2.Boundsforfewnomialcouples.Wenowgiveexplicitboundsinthecasewherethe bersinthesemi-Pfa ancouple(X,Y)canbothbede nedK-fewnomials,i.e.bydegree1Pfa anfunctioninachainofthetype(20).In

= ,theseboundswillparticular,ifSisasemi-algebriacsetsuchthat S∩

applytoXasin(21)andtoY={x1=λ}∪···∪{xn=λ}.

Theorem19.Let(X,Y)beasemi-Pfa ancouplede nedbydegree1func-tionsinthechain(20).Then,thefollowingboundscanbeestablishedforthenumberofconnectedcomponentsof(X,Y)0.

Case1.Ifforallλ>0,XλandYλaree ectivelynon-singularofdimensionrespectivelydandk,weobtainfrom(16)thebound

(22)d

p=02q2(n+r)2/2(4n+6)q(3n+2r)qq(n+r).

Case2.IfXandYaretheunionofrespectivelyMandNbasicsets,thenumberofconnectedcomponentsof(X,Y)0isboundedby:

(23)MNn 1

p=02q2(n+r)2/2(6n+6)q(3n+2r)qq(n+r).

Proof.TheseboundsareobtainedusingtheresultsfromTheorems15and17,withα=2,β=1and =n+r,andthenboundingverybluntlythetermsβpandγp.

3.3.Closurerelativetothefrontierofafewnomialset.LetXbeasemi-Pfa anfamilysuchthatforallλ>0,thesetXλisde nedbyK-fewnomials.Byde nitionofafamily,theset XλiscontainedinthedomainofthePfa anchain,sobytheresultsof[5],thissetisasemi-Pfa ansetde nedbyfunctionsinthechain,thatis,polynomialsoflowadditivecomplexity.Moreover,theformatof XλcanbeestimatedfromtheformatofXλ.ApplyingthoseresultstogetherwiththoseofTheorem17,wecangiveestimatesforthenumberofconnectedcomponentsof(X, X)0.

Theorem20.LetXbeasemi-Pfa anfamilyinaPfa anchainoftype(20).IftheformatofXisoftheform(N,I,J,n, =n+r,α=2,β=1),thenumberofconnectedcomponentsof(X, X)isboundedby

(24)N(I+J)2N+rO(n2)(n+r)nnO(n2+nr).

Proof.Following[5],theset Xλcanbede nedusingthesamePfa anchainasXλ,usingN basicsetsandfunctionsofdegreeatmostβ ,where,underthehypothesesabove,thefollowingboundshold.

β ≤n(n+r)O(n),N ≤N(I+J)N+rO(n)N(n+r)2rO(n).

Theboundonthenumberofconnectedcomponentsfollowsreadily.

References

[1]R.BenedettiandJ.-J.Risler.RealAlgebraicandSemi-algebraicSets.Hermann,1990.

[2]L.vandenDries.TameTopologyandO-minimalStructures.LMSLectureNoteSeries

No.248.CambridgeUniversityPress,1998.

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库DIMACS Series in Discrete Mathematics and Theoretical Comput(10)在线全文阅读。