Springer Monographs in Mathematics John Rhodes Pedro V. Silva Boolean Representations of Simplicial Complexes and Matroids Springer Monographs in Mathematics Moreinformationaboutthisseriesathttp://www.springer.com/series/3733 John Rhodes • Pedro V. Silva Boolean Representations of Simplicial Complexes and Matroids 123 JohnRhodes PedroV.Silva DepartmentofMathematics DepartmentofMathematics UniversityofCaliforniaatBerkeley UniversityofPorto Berkeley,CA,USA Porto,Portugal ISSN1439-7382 ISSN2196-9922 (electronic) SpringerMonographsinMathematics ISBN978-3-319-15113-7 ISBN978-3-319-15114-4 (eBook) DOI10.1007/978-3-319-15114-4 LibraryofCongressControlNumber:2015931927 Mathematics Subject Classification (2010): 03E05, 03G10, 05-00, 05B25, 05B30, 05B35, 05D15, 05E45,06-00,06A11,06A12,06B15,15B34,16Y60,51E14,55P15,55U10 SpringerChamHeidelbergNewYorkDordrechtLondon ©SpringerInternationalPublishingSwitzerland2015 Thisworkissubjecttocopyright.AllrightsarereservedbythePublisher,whetherthewholeorpartof thematerialisconcerned,specificallytherightsoftranslation,reprinting,reuseofillustrations,recitation, broadcasting,reproductiononmicrofilmsorinanyotherphysicalway,andtransmissionorinformation storageandretrieval,electronicadaptation,computersoftware,orbysimilarordissimilarmethodology nowknownorhereafterdeveloped. Theuseofgeneraldescriptivenames,registerednames,trademarks,servicemarks,etc.inthispublication doesnotimply,evenintheabsenceofaspecificstatement,thatsuchnamesareexemptfromtherelevant protectivelawsandregulationsandthereforefreeforgeneraluse. Thepublisher,theauthorsandtheeditorsaresafetoassumethattheadviceandinformationinthisbook arebelievedtobetrueandaccurateatthedateofpublication.Neitherthepublishernortheauthorsor theeditorsgiveawarranty,expressorimplied,withrespecttothematerialcontainedhereinorforany errorsoromissionsthatmayhavebeenmade. Printedonacid-freepaper SpringerInternationalPublishingAGSwitzerlandispartofSpringerScience+BusinessMedia(www. springer.com) InmemoryofGian-CarloRota Acknowledgments Both the authors thank Anne Schilling, Benjamin Steinberg, James Oxley, and StuartMargolisfortheirvaluablecomments. JohnRhodeswouldliketothankhisremarkablewife,LauraMorland,forallher loveandsupport. PedroV.SilvaisgratefultohiswifeMargaridaforherenduringsupportandfor everythingelse!Healsoacknowledgessupportfrom (cid:129) TheEuropeanRegionalDevelopmentFundthroughtheprogrammeCOMPETE and the Portuguese Government through FCT (Fundação para a Ciência e a Tecnologia)undertheprojectPEst-C/MAT/UI0144/2013 (cid:129) CNPq(Brazil)throughaBJT-Agrant(process313768/2013-7) vii Contents 1 Introduction .................................................................. 1 2 BooleanandSuperbooleanMatrices ...................................... 9 2.1 TheBooleanandtheSuperbooleanSemirings........................ 9 2.2 SuperbooleanMatrices................................................. 11 3 PosetsandLattices........................................................... 17 3.1 BasicNotions........................................................... 17 3.2 RepresentationofPosets............................................... 21 3.3 _-GeneratingSubsetsofLattices...................................... 22 3.4 TheLatticeofFlatsofaMatrix........................................ 23 3.5 MatricesVersusLattices ............................................... 24 3.6 c-Independenceandc-Rank............................................ 28 4 SimplicialComplexes........................................................ 31 4.1 TheCombinatorialPerspective........................................ 31 4.1.1 Matroids ........................................................ 32 4.1.2 Graphs .......................................................... 33 4.2 Flats..................................................................... 34 5 BooleanRepresentations.................................................... 39 5.1 SuperbooleanandBooleanRepresentations .......................... 39 5.2 TheCanonicalBooleanRepresentation............................... 41 5.3 LowDimensions........................................................ 48 5.4 LatticeRepresentations ................................................ 49 5.5 TheLatticeofLatticeRepresentations................................ 50 5.6 MinimumDegree....................................................... 58 5.7 Examples................................................................ 62 5.7.1 TheTetrahedronComplexesT3andT2 ....................... 62 5.7.2 TheFanoMatroid.............................................. 68 5.7.3 TheUniformMatroidU3;n..................................... 73 5.7.4 SteinerSystems ................................................ 80 ix