LONDONMATHEMATICALSOCIETYLECTURENOTESERIES ManagingEditor:ProfessorE.Su¨li,MathematicalInstitute, WoodstockRoad,UniversityofOxford,OxfordOX26GG,UnitedKingdom Thetitlesbelowareavailablefrombooksellers,orfromCambridgeUniversityPressat www.cambridge.org/mathematics 347 Surveysincontemporarymathematics,N.YOUNG&Y.CHOI(eds) 348 Transcendentaldynamicsandcomplexanalysis,P.J.RIPPON&G.M.STALLARD(eds) 349 ModeltheorywithapplicationstoalgebraandanalysisI,Z.CHATZIDAKIS,D.MACPHERSON,A.PILLAY& A.WILKIE(eds) 350 ModeltheorywithapplicationstoalgebraandanalysisII,Z.CHATZIDAKIS,D.MACPHERSON,A.PILLAY& A.WILKIE(eds) 351 FinitevonNeumannalgebrasandmasas,A.M.SINCLAIR&R.R.SMITH 352 Numbertheoryandpolynomials,J.MCKEE&C.SMYTH(eds) 353 Trendsinstochasticanalysis,J.BLATH,P.MO¨RTERS&M.SCHEUTZOW(eds) 354 Groupsandanalysis,K.TENT(ed) 355 Non-equilibriumstatisticalmechanicsandturbulence,J.CARDY,G.FALKOVICH&K.GAWEDZKI 356 EllipticcurvesandbigGaloisrepresentations,D.DELBOURGO 357 Algebraictheoryofdifferentialequations,M.A.H.MACCALLUM&A.V.MIKHAILOV(eds) 358 Geometricandcohomologicalmethodsingrouptheory,M.R.BRIDSON,P.H.KROPHOLLER& I.J.LEARY(eds) 359 Modulispacesandvectorbundles,L.BRAMBILA-PAZ,S.B.BRADLOW,O.GARC´IA-PRADA& S.RAMANAN(eds) 360 Zariskigeometries,B.ZILBER 361 Words:Notesonverbalwidthingroups,D.SEGAL 362 Differentialtensoralgebrasandtheirmodulecategories,R.BAUTISTA,L.SALMERO´N&R.ZUAZUA 363 Foundationsofcomputationalmathematics,HongKong2008,F.CUCKER,A.PINKUS&M.J.TODD(eds) 364 Partialdifferentialequationsandfluidmechanics,J.C.ROBINSON&J.L.RODRIGO(eds) 365 Surveysincombinatorics2009,S.HUCZYNSKA,J.D.MITCHELL&C.M.RONEY-DOUGAL(eds) 366 Highlyoscillatoryproblems,B.ENGQUIST,A.FOKAS,E.HAIRER&A.ISERLES(eds) 367 Randommatrices:Highdimensionalphenomena,G.BLOWER 368 GeometryofRiemannsurfaces,F.P.GARDINER,G.GONZA´LEZ-DIEZ&C.KOUROUNIOTIS(eds) 369 Epidemicsandrumoursincomplexnetworks,M.DRAIEF&L.MASSOULIE´ 370 Theoryofp-adicdistributions,S.ALBEVERIO,A.YU.KHRENNIKOV&V.M.SHELKOVICH 371 Conformalfractals,F.PRZYTYCKI&M.URBAN´SKI 372 Moonshine:Thefirstquartercenturyandbeyond,J.LEPOWSKY,J.MCKAY&M.P.TUITE(eds) 373 Smoothness,regularityandcompleteintersection,J.MAJADAS&A.G.RODICIO 374 Geometricanalysisofhyperbolicdifferentialequations:Anintroduction,S.ALINHAC 375 Triangulatedcategories,T.HOLM,P.JØRGENSEN&R.ROUQUIER(eds) 376 Permutationpatterns,S.LINTON,N.RUSˇKUC&V.VATTER(eds) 377 AnintroductiontoGaloiscohomologyanditsapplications,G.BERHUY 378 Probabilityandmathematicalgenetics,N.H.BINGHAM&C.M.GOLDIE(eds) 379 Finiteandalgorithmicmodeltheory,J.ESPARZA,C.MICHAUX&C.STEINHORN(eds) 380 Realandcomplexsingularities,M.MANOEL,M.C.ROMEROFUSTER&C.T.CWALL(eds) 381 Symmetriesandintegrabilityofdifferenceequations,D.LEVI,P.OLVER,Z.THOMOVA& P.WINTERNITZ(eds) 382 Forcingwithrandomvariablesandproofcomplexity,J.KRAJ´ICˇEK 383 Motivicintegrationanditsinteractionswithmodeltheoryandnon-ArchimedeangeometryI,R.CLUCKERS, J.NICAISE&J.SEBAG(eds) 384 Motivicintegrationanditsinteractionswithmodeltheoryandnon-ArchimedeangeometryII,R.CLUCKERS, J.NICAISE&J.SEBAG(eds) 385 EntropyofhiddenMarkovprocessesandconnectionstodynamicalsystems,B.MARCUS,K.PETERSEN& T.WEISSMAN(eds) 386 Independence-friendlylogic,A.L.MANN,G.SANDU&M.SEVENSTER 387 GroupsStAndrews2009inBathI,C.M.CAMPBELLetal(eds) 388 GroupsStAndrews2009inBathII,C.M.CAMPBELLetal(eds) 389 Randomfieldsonthesphere,D.MARINUCCI&G.PECCATI 390 Localizationinperiodicpotentials,D.E.PELINOVSKY 391 Fusionsystemsinalgebraandtopology,M.ASCHBACHER,R.KESSAR&B.OLIVER 392 Surveysincombinatorics2011,R.CHAPMAN(ed) 393 Non-abelianfundamentalgroupsandIwasawatheory,J.COATESetal(eds) 394 Variationalproblemsindifferentialgeometry,R.BIELAWSKI,K.HOUSTON&M.SPEIGHT(eds) 395 Howgroupsgrow,A.MANN 396 Arithmeticdifferentialoperatorsoverthep-adicintegers,C.C.RALPH&S.R.SIMANCA 397 Hyperbolicgeometryandapplicationsinquantumchaosandcosmology,J.BOLTE&F.STEINER(eds) 398 Mathematicalmodelsincontactmechanics,M.SOFONEA&A.MATEI 399 Circuitdoublecoverofgraphs,C.-Q.ZHANG 400 Densespherepackings:ablueprintforformalproofs,T.HALES 401 AdoubleHallalgebraapproachtoaffinequantumSchur–Weyltheory,B.DENG,J.DU&Q.FU 402 Mathematicalaspectsoffluidmechanics,J.C.ROBINSON,J.L.RODRIGO&W.SADOWSKI(eds) 403 Foundationsofcomputationalmathematics,Budapest2011,F.CUCKER,T.KRICK,A.PINKUS& A.SZANTO(eds) 404 Operatormethodsforboundaryvalueproblems,S.HASSI,H.S.V.DESNOO&F.H.SZAFRANIEC(eds) 405 Torsors,e´talehomotopyandapplicationstorationalpoints,A.N.SKOROBOGATOV(ed) 406 Appalachiansettheory,J.CUMMINGS&E.SCHIMMERLING(eds) 407 Themaximalsubgroupsofthelow-dimensionalfiniteclassicalgroups,J.N.BRAY,D.F.HOLT& C.M.RONEY-DOUGAL 408 Complexityscience:theWarwickmaster’scourse,R.BALL,V.KOLOKOLTSOV&R.S.MACKAY(eds) 409 Surveysincombinatorics2013,S.R.BLACKBURN,S.GERKE&M.WILDON(eds) 410 Representationtheoryandharmonicanalysisofwreathproductsoffinitegroups, T.CECCHERINI-SILBERSTEIN,F.SCARABOTTI&F.TOLLI 411 Modulispaces,L.BRAMBILA-PAZ,O.GARC´IA-PRADA,P.NEWSTEAD&R.P.THOMAS(eds) 412 Automorphismsandequivalencerelationsintopologicaldynamics,D.B.ELLIS&R.ELLIS 413 Optimaltransportation,Y.OLLIVIER,H.PAJOT&C.VILLANI(eds) 414 AutomorphicformsandGaloisrepresentationsI,F.DIAMOND,P.L.KASSAEI&M.KIM(eds) 415 AutomorphicformsandGaloisrepresentationsII,F.DIAMOND,P.L.KASSAEI&M.KIM(eds) 416 Reversibilityindynamicsandgrouptheory,A.G.O’FARRELL&I.SHORT 417 Recentadvancesinalgebraicgeometry,C.D.HACON,M.MUSTAT¸A˘&M.POPA(eds) 418 TheBloch–KatoconjecturefortheRiemannzetafunction,J.COATES,A.RAGHURAM,A.SAIKIA& R.SUJATHA(eds) 419 TheCauchyproblemfornon-Lipschitzsemi-linearparabolicpartialdifferentialequations,J.C.MEYER& D.J.NEEDHAM 420 Arithmeticandgeometry,L.DIEULEFAITetal(eds) 421 O-minimalityandDiophantinegeometry,G.O.JONES&A.J.WILKIE(eds) 422 GroupsStAndrews2013,C.M.CAMPBELLetal(eds) 423 Inequalitiesforgrapheigenvalues,Z.STANIC´ 424 Surveysincombinatorics2015,A.CZUMAJetal(eds) 425 Geometry,topologyanddynamicsinnegativecurvature,C.S.ARAVINDA,F.T.FARRELL& J.-F.LAFONT(eds) 426 Lecturesonthetheoryofwaterwaves,T.BRIDGES,M.GROVES&D.NICHOLLS(eds) 427 RecentadvancesinHodgetheory,M.KERR&G.PEARLSTEIN(eds) 428 GeometryinaFre´chetcontext,C.T.J.DODSON,G.GALANIS&E.VASSILIOU 429 Sheavesandfunctionsmodulop,L.TAELMAN 430 RecentprogressinthetheoryoftheEulerandNavier–Stokesequations,J.C.ROBINSON,J.L.RODRIGO, W.SADOWSKI&A.VIDAL-LO´PEZ(eds) 431 Harmonicandsubharmonicfunctiontheoryontherealhyperbolicball,M.STOLL 432 Topicsingraphautomorphismsandreconstruction(2ndEdition),J.LAURI&R.SCAPELLATO 433 RegularandirregularholonomicD-modules,M.KASHIWARA&P.SCHAPIRA 434 Analyticsemigroupsandsemilinearinitialboundaryvalueproblems(2ndEdition),K.TAIRA 435 GradedringsandgradedGrothendieckgroups,R.HAZRAT 436 Groups,graphsandrandomwalks,T.CECCHERINI-SILBERSTEIN,M.SALVATORI&E.SAVA-HUSS(eds) 437 Dynamicsandanalyticnumbertheory,D.BADZIAHIN,A.GORODNIK&N.PEYERIMHOFF(eds) 438 Randomwalksandheatkernelsongraphs,M.T.BARLOW 439 Evolutionequations,K.AMMARI&S.GERBI(eds) 440 Surveysincombinatorics2017,A.CLAESSONetal(eds) 441 Polynomialsandthemod2SteenrodalgebraI,G.WALKER&R.M.W.WOOD 442 Polynomialsandthemod2SteenrodalgebraII,G.WALKER&R.M.W.WOOD 443 Asymptoticanalysisingeneralrelativity,T.DAUDE´,D.HA¨FNER&J.-P.NICOLAS(eds) 444 Geometricandcohomologicalgrouptheory,P.H.KROPHOLLER,I.J.LEARY,C.MART´INEZ-PE´REZ& B.E.A.NUCINKIS(eds) 445 Introductiontohiddensemi-Markovmodels,J.VANDERHOEK&R.J.ELLIOTT 446 Advancesintwo-dimensionalhomotopyandcombinatorialgrouptheory,W.METZLER& S.ROSEBROCK(eds) 447 Newdirectionsinlocallycompactgroups,P.-E.CAPRACE&N.MONOD(eds) 448 Syntheticdifferentialtopology,M.C.BUNGE,F.GAGO&A.M.SANLUIS 449 Permutationgroupsandcartesiandecompositions,C.E.PRAEGER&C.SCHNEIDER 450 Partialdifferentialequationsarisingfromphysicsandgeometry,M.BENAYEDetal(eds) 451 Topologicalmethodsingrouptheory,N.BROADDUS,M.DAVIS,J.-F.LAFONT&I.ORITZ(eds) 452 Partialdifferentialequationsinfluidmechanics,C.L.FEFFERMAN,J.C.ROBINSON&J.L.RODRIGO(eds) 453 Stochasticstabilityofdifferentialequationsinabstractspaces,K.LIU 454 Beyondhyperbolicity,M.HAGEN,R.WEBB&H.WILTON(eds) 455 GroupsStAndrews2017inBirmingham,C.M.CAMPBELLetal(eds) LondonMathematicalSocietyLectureNoteSeries:456 Surveys in Combinatorics 2019 Editedby ALLAN LO UniversityofBirmingham RICHARD MYCROFT UniversityofBirmingham GUILLEM PERARNAU UniversitatPolite`cnicadeCatalunya,Barcelona ANDREW TREGLOWN UniversityofBirmingham UniversityPrintingHouse,CambridgeCB28BS,UnitedKingdom OneLibertyPlaza,20thFloor,NewYork,NY10006,USA 477WilliamstownRoad,PortMelbourne,VIC3207,Australia 314–321,3rdFloor,Plot3,SplendorForum,JasolaDistrictCentre, NewDelhi–110025,India 79AnsonRoad,#06-04/06,Singapore079906 CambridgeUniversityPressispartoftheUniversityofCambridge. ItfurtherstheUniversity’smissionbydisseminatingknowledgeinthepursuitof education,learning,andresearchatthehighestinternationallevelsofexcellence. www.cambridge.org Informationonthistitle:www.cambridge.org/9781108740722 DOI:10.1017/9781108649094 ©CambridgeUniversityPress2019 Thispublicationisincopyright.Subjecttostatutoryexception andtotheprovisionsofrelevantcollectivelicensingagreements, noreproductionofanypartmaytakeplacewithoutthewritten permissionofCambridgeUniversityPress. Firstpublished2019 PrintedandboundinGreatBritainbyClaysLtd,ElcografS.p.A. AcataloguerecordforthispublicationisavailablefromtheBritishLibrary. ISBN978-1-108-74072-2Paperback CambridgeUniversityPresshasnoresponsibilityforthepersistenceoraccuracyof URLsforexternalorthird-partyinternetwebsitesreferredtointhispublication anddoesnotguaranteethatanycontentonsuchwebsitesis,orwillremain, accurateorappropriate. Preface The Twenty-Seventh British Combinatorial Conference is to be held at the University of Birmingham from 29th July to 2nd August 2019. The British CombinatorialCommitteehadinvitedeightdistinguishedcombinatorialiststo give survey lectures in areas of their expertise, and this volume contains the surveyarticlesonwhichtheselectureswerebased. In compiling this volume we are indebted to the authors for preparing their articles so accurately and professionally, and to the referees for their rapid responses and keen eye for detail. We would also like to thank Tom HarrisandClareDennisonatCambridgeUniversityPress.Finally,withoutthe previous efforts of editors of earlier Surveys and the guidance of the British Combinatorial Committee, the preparation of this volume would have been somewhatdaunting. This conference is organised in partnership with the Clay Mathematics Institute,theHeilbronnInstitute,theInstituteofCombinatoricsanditsAppli- cations,theLondonMathematicalSocietyandtheUniversityofBirmingham; we thank each of these organisations for their generous involvement and support. AllanLo RichardMycroft AndrewTreglown UniversityofBirmingham GuillemPerarnau UniversitatPolite`cnicadeCatalunya February2019 vii Contents Preface pagevii 1 Clique-widthforhereditarygraphclasses 1 KonradK.Dabrowski,MatthewJohnsonandDanie¨lPaulusma 2 Analyticrepresentationsoflargegraphs 57 AndrzejGrzesikandDanielKra´l’ 3 Topologicalconnectednessandindependentsetsingraphs 89 PennyHaxell 4 Expanders–howtofindthem,andwhattofindinthem 115 MichaelKrivelevich 5 Supersingularisogenygraphsincryptography 143 KristinE.LauterandChristophePetit 6 Delta-matroidsforgraphtheorists 167 IainMoffatt 7 Extremaltheoryofvertexoredgeorderedgraphs 221 Ga´borTardos 8 Somecombinatorialandgeometricconstructionsof sphericalbuildings 237 HendrikVanMaldeghemandMagaliVictoor v Clique-width for hereditary graph classes Konrad K. Dabrowski, Matthew Johnson and Dani¨el Paulusma Abstract Clique-width is a well-studied graph parameter owing to its use in understanding algorithmic tractability: if the clique-width of a graph class G is bounded by a con- stant, a wide range of problems that are NP-complete in general can be shown to be polynomial-timesolvableonG. Forthisreason,theboundednessorunboundednessof clique-widthhasbeeninvestigatedanddeterminedformanygraphclasses. Wesurvey theseresultsforhereditarygraphclasses,whicharethegraphclassesclosedundertak- inginducedsubgraphs. Wethendiscussthealgorithmicconsequencesoftheseresults, inparticularfortheColouringandGraphIsomorphismproblems. Wealsoexplain a possible strong connection between results on boundedness of clique-width and on well-quasi-orderabilitybytheinducedsubgraphrelationforhereditarygraphclasses. 1 Introduction ManydecisionproblemsareknowntobeNP-complete[84],anditisgenerallybelieved thatsuchproblemscannotbesolvedintimepolynomialintheinputsize. Formanyofthese hardproblems,placingrestrictionsontheinput(thatis,insistingthattheinputhascertain stated properties) can lead to significant changes in the computational complexity of the problem. Thisleadsonetoaskfundamentalquestions: underwhichinputrestrictionscan anNP-completeproblembesolvedinpolynomialtime,andunderwhichinputrestrictions does the problem remain NP-complete? For problems defined on graphs, we can restrict the input to some special class of graphs that have some commonality. The ultimate goal is to obtain complexity dichotomies for large families of graph problems, which tell us exactly for which graph classes a certain problem is efficiently solvable and for which it stays computationally hard. Such dichotomies may not always exist if P(cid:2)= NP [129], but ratherthansolvingproblemsonebyone,andgraphclassbygraphclass,wewanttodiscover generalpropertiesofgraphclassesfromwhichwecandeterminethetractabilityorhardness offamiliesofproblems. 1.1 Width Parameters One way to define a graph class is to use a notion of “width” and consider the set of graphsforwhichthewidthisboundedbyaconstant. Thoughitwillnotbeourfocus,let usbrieflyillustratethisideawiththemostwell-knownwidthparameter,treewidth. Atree decomposition ofagraphG=(V,E)isatreeT whosenodesaresubsetsofV andhasthe propertiesthat,foreachvinV,thetreenodesthatcontainvinduceanon-emptyconnected subgraph,and,foreachedgevwinE,thereisatleastonetreenodethatcontainsvandw. See Figure 1 for an illustration of a graph and one of its tree decompositions. The sets of verticesthatformthenodesofthetreearecalledbags andthewidthofthedecomposition isonelessthanthesizeofthelargestbag. ThetreewidthofGistheminimumwidthofits treedecompositions. Onecanthereforedefineaclassofgraphsofboundedtreewidth;that is, for some constant c, the collection of graphs that each have treewidth at most c. The exampleinFigure1hastreewidth2. Moreover,itiseasytoseethattreesformexactlythe classofgraphswithtreewidth1. Hence,thetreewidthofagraphcanbeseenasameasure thatindicateshowcloseagraphistobeingatree. Manygraphproblemscanbesolvedin 1