FORBIDDEN SUBGRAPHS IN THE NORM GRAPH

5

1

2

eb

F

5

]

OC

.

h

t

a

m

[

1

v

2

5

1

.

2

5

:1v

i

X

r

aFORBIDDENSUBGRAPHSINTHENORMGRAPHSIMEONBALLANDVALENTINAPEPEAbstract.Weshowthatthenormgraphconstructedin[11]withnverticesabout1(s 1)1/tn2 1/t+12n2 1/tedges.In[1](basedonresultsfrom[11])itwasproventhatthegraphΓ(contains2t)nocopyofKt,(t 1)!+1,thusprovingthatfors (t 1)!+1,ex(n,Kt,s)>cn2 1/t

forsomeconstantc.

In[2],itwasshownthatΓ(4)containsnocopyofK5,5,whichimprovesontheprobabilisticlowerboundofErd osandSpencer[6]forex(n,K5,5).Inthisarticle,wewillgeneralisethisresultandprovethatΓ(t)containsnocopyofKt+1,(t 1)! 1.Fort 5,thisdoesnot

2BALLANDPEPE

improvetheprobabilisticlowerboundofErd osandSpencer,

ex(n,Kt,s) cn2 (s+t 2)/(st 1).

Asfarasweareaware,itishoweverthedeterministicconstructionofagraphwithnverticescontainingnoKt+1,(t 1)! 1withthemostedges.

2.Thenormgraph

Supposethatq=ph,wherepisaprime,anddenotebyFqthe nite eldwithqelements.

iiiWewillusethefollowingpropertiesof nite elds.Foranya,b∈Fq,(a+b)p=ap+bp,

iiiforanyi∈N.Notethat(a b)p=ap bp,sinceeitherpiisoddor 1=1.Secondly,

k 1∈Fq,forallforalla∈Fqi,aq=aifandonlyifa∈Fq.FinallyN(a)=a1+q+···+q

a∈Fqk,sinceN(a)q=N(a).

LetFdenoteanarbitrary eld.WedenotebyPn(F)theprojectivespacearisingfromthe(n+1)-dimensionalvectorspaceoverF.Throughoutdimwillrefertoprojectivedimension.ApointofPn(F)(whichisaone-dimensionalsubspaceofthevectorspace)willoftenbewrittenas u ,whereuisavectorinthe(n+1)-dimensionalvectorspaceoverF.

LetΓ(t)bethegraphwithvertices(a,α)∈Fqt 1×Fq,α=0,where(a,α)isjoinedto(a′,α′)ifandonlyifN(a+a′)=αα′.ThegraphΓ(t)wasconstructedin[11],whereitwasshowntocontainnocopyofKt,t!+1.In[1]Alon,R´onyaiandSzab´oprovedthatΓ(t)containsnocopyofKt,(t 1)!+1.OuraimhereistoshowthatitalsocontainsnoKt+1,(t 1)! 1,generalizingthesameresultfort=5presentedin[2].

Let

V={(1,a) (1,aq) ··· (1,aqt 2)|a∈Fqt 1} P2t 1 1(Fqt 1).

whereP1=P1(Fq).ThesetVisthea nepartofanalgebraicvarietythatisinturnasubvarietyoftheSegrevarietyΣ=P1×P1×···×P1, t 1times

t 2Thea nepoint(1,a) (1,aq) ··· (1,aq)hascoordinatesindexedbythesubsets

ofT:={0,1,...,t 1},wheretheS-coordinateis i(aq),

i∈S

foranynon-emptysubsetSofTand

i∈Saq=1i

whenS= (see[13]).

FORBIDDENSUBGRAPHSINTHENORMGRAPH3

Letn=2t 1 1.

WeorderthecoordinatesofPn(Fqt 1)sothatifthei-thcoordinatecorrespondstothesubsetS,thenthe(n i)–thcoordinatecorrespondstothesubsetT\S.

EmbedthePn(Fqt 1)containingVasahyperplanesectionofPn+1(Fqt 1)de nedbytheequationxn+1=0.

Letβbethesymmetricbilinearformonthe(n+2)-dimensionalvectorspaceoverFqt 1de nedbyn uivn i un+1vn+1.β(u,v)=

i=0

Let⊥bede nedintheusualway,sothatgivenasubspaceΠofPn+1(Fqt 1),Π⊥isthesubspaceofPn+1(Fqt 1)de nedby

Π⊥={v|β(u,v)=0,forallu∈Π}.

Wewishtode nethesamegraphΓ(t),sothatadjacencyisgivenbythebilinearform.LetP∞=(0,0,0,...,1).LetΓ′beagraphwithvertexsetthesetofpointsonthelinesjoiningthepointsofVtoP∞obtainedusingonlyscalarsinFq,distinctfromP∞andnotcontainedinthehyperplanexn+1=0.Jointwovertices u and u′ inΓ′ifandonlyifβ(u,u′)=0.ItisasimplemattertoverifythatthegraphΓ′isisomorphictothegraphΓ(t)since ijN(a+b)=aqbq=β(u,v)+un+1vn+1,

S Ti∈S,j∈T\S

where

u=(1,a) (1,aq) ··· (1,aq

and

v=(1,b) (1,bq) ··· (1,bq

WeshallrefertoΓ′asΓ(t)fromnowon.

WerecallsomeknownpropertiesofΣanditssubvariety

V={(a,b) (aq,bq) ···(aq

andproveanewoneinTheorem2.5.Let

Theorem2.1.Σisasmoothirreduciblevariety.t 2t 2),t 2).,bqt 2)|(a,b)∈P1(Fqt 1)}Fq.

Theorem2.2.ThedimensionofΣ(asalgebraicvariety)ist 1anditsdegreeis(t 1)!.Theorem2.3.[13]AnytpointsofVareingeneralposition.

Theorem2.4.[10]Ift+1pointsspana(t 1)-dimensionalprojectivespace,thenthatspacecontainsq+1pointsofV.

4BALLANDPEPE

Theorem2.5.Ifasubspaceofcodimensiontcontainsa nitenumberofpointsofΣthenitcontainsatmost(t 1)! 2pointsofΣ.

Proof.ByTheorem2.1,Σissmooth,soitisregularateachofitspoints,i.e.,ifTPΣisthetangentspaceofΣatapointP∈Σ,thendimTPΣ=t 1.

LetΠbeasubspaceofcodimensiontcontaininga nitenumberofpointsofΣ.LetP∈Π∩Σ.Thendim TPΣ,Π n 1.Therefore,thereisahyperplaneHcontaining TPΣ,Π .

SupposethatHcontainsanothertangentspaceTRΣ,withR∈Π∩Σ.ThealgebraicvarietyH∩Σhasdimensiont 2(sinceΣisirreducible)andithastwosingularpoints,PandR.SincedimH∩Σ=t 2asanalgebraicvariety,theremustbealinearsubspaceΠ1ofcodimensiont 2inHcontainingΠandsuchthatΠ1∩H∩Σconsistsofdeg(H∩Σ) (t 1)!pointsofΣcountedwiththeirmultiplicity.SinceΠ1containsPandR,whicharesingularpointsandsowithmultiplicityatleast2,wehavethat

|Π∩Σ| |Π1∩Σ| (t 1)! 2.

SupposenowthatHdoesnotcontainanyothertangentspaceTRΣwithR∈Π∩Σ,R=P.ThentakeR∈Π∩ΣandconsiderahyperplaneH′=Hcontaining TRΣ,Π .ThenthetangentspacesofPandRwithrespecttoH∩H′∩ΣareTPΣ∩H′andTRΣ∩H,andtheybothhavedimensiont 2(aslinearspaces).

IfdimH∩H′∩Σ=t 3asanalgebraicvariety,thenPandRaretwosingularpointsofH∩H′∩Σandwecan nd,asbefore,alinearsubspaceΠ1ofcodimensiont 3inH∩H′suchthatitcontainsΠandintersectsH∩H′∩Σindeg(H∩H′∩Σ) (t 1)!points,countedwiththeirmultiplicity.SincePandRhavemultiplicityatleast2,wehave

|Π∩Σ| |Π1∩Σ| (t 1)! 2.

IfdimH∩H′∩Σ=t 2asanalgebraicvariety,thenH∩Σisreducible.Hence,wehave

H∩Σ=V1∪V2∪···∪Vr,

whereViisanirreduciblevarietyofdimensiont 2,foralli=1,...,r.Sowehave

H∩H′∩Σ=V1∪V2∪···∪Vs∪Ws+1∪Ws+2∪···∪Wr,