EssaysinCombinatorics: CrystalsonShiftedPrimedTableaux,BigradedFibonacciNumbersand DataMiningonSocialGraphs By KIRILLPARAMONOV DISSERTATION Submittedinpartialsatisfactionoftherequirementsforthedegreeof DOCTOROFPHILOSOPHY in MATHEMATICS inthe OFFICEOFGRADUATESTUDIES ofthe UNIVERSITYOFCALIFORNIA DAVIS Approved: ProfessorAnneSchilling UniversityofCalifornia,Davis ProfessorEugeneGorsky UniversityofCalifornia,Davis ProfessorJamesSharpnack UniversityofCalifornia,Davis CommitteeinCharge 2018 -i- (cid:3) (cid:3) (cid:3) (cid:3) ProQuest Number:10822760 (cid:3) (cid:3) (cid:3) (cid:3) All rights reserved (cid:3) INFORMATION TO ALL USERS Thequality of this reproduction is dependent upon the qualityof the copy submitted. (cid:3) In the unlikely event that the authordid not send a complete manuscript and there are missing pages,these will be noted. Also, if material had to be removed, a notewill indicate the deletion. (cid:3) (cid:3) (cid:3) (cid:3) (cid:3) ProQuest 10822760 (cid:3) Published by ProQuest LLC ( 2018). Copyrightof the Dissertation is held by the Author. (cid:3) (cid:3) All rights reserved. This work is protected against unauthorized copying under Title 17, United States Code Microform Edition © ProQuest LLC. (cid:3) (cid:3) ProQuest LLC. 789 East Eisenhower Parkway P.O. Box 1346 Ann Arbor, MI 48106 - 1346 Contents Abstract v Acknowledgments vii Chapter1. Introduction 1 1.1. CrystalsandtypeC StanleySymmetricFunctions. 1 1.1.1. Schurfunctions 1 1.1.2. Stanleysymmetricfunctions 2 1.1.3. TypeAcrystalofwords 4 1.1.4. Ourcontributions 5 1.2. CoreswithdistinctpartsandbigradedFibonaccinumbers. 7 1.2.1. Simultaneouscorepartitions 7 1.2.2. Dyckpaths 9 1.2.3. Abacusdiagrams 10 1.2.4. Ourcontributions 12 1.3. EstimatinggraphletstatisticsviaLifting 14 1.3.1. Graphlets 15 1.3.2. Graphletsampling 16 1.3.3. Definitionsandnotation 16 1.3.4. Priorgraphletsamplingmethods 16 1.3.5. Ourcontributions 17 Chapter2. CrystalAnalysisoftypeC StanleySymmetricFunctions 19 2.1. Crystalisomorphism 19 2.1.1. Kras´kiewiczinsertion 19 2.1.2. Mixedinsertion 24 -ii- 2.2. Explicitcrystaloperatorsonshiftedprimedtableaux 28 2.3. ImplementationinSage 34 2.4. ProofofTheorem2.19 37 2.4.1. Preliminaries 37 2.4.2. ProofofTheorem2.19 42 2.5. ProofofTheorem2.21 47 2.5.1. Preliminaries 47 2.5.2. ProofofTheorem2.21 51 2.6. Outlook 51 Chapter3. CoreswithdistinctpartsandbigradedFibonaccinumbers 52 3.1. Simultaneouscoreswithdistinctparts. 52 3.2. Maximumsizeof(a,a+1)-coreswithdistinctparts. 54 3.3. Numberof(2k−1,2k+1)-coreswithdistinctparts. 56 3.4. GradedFibonaccinumbersand(a,as+1)-coreswithdistinctparts. 58 3.5. BouncestatisticandbigradedFibonaccinumbers. 65 Chapter4. EstimatingGraphletStatisticsviaLifting 70 4.1. Priorsamplingschemes 70 4.1.1. SubgraphRandomWalk 70 4.1.2. WaddlingRandomWalk 71 4.2. Subgraphlifting 71 4.2.1. Notation 71 4.2.2. Algorithmdescription 72 4.2.3. Orderedliftestimator 73 4.2.4. Unorderedliftestimator 74 4.2.5. Samplingastartingvertex 77 4.3. TheoreticalAnalysisofLifting 78 4.4. Experiments 81 4.4.1. RelativeErrorgivenlimitedqueries 82 -iii- 4.4.2. Variationandcorrelationofsamples 83 4.5. Supplementto”EstimatingGraphletsviaLifting” 85 4.5.1. ProofofProp. 4.1. 85 4.5.2. ProofofTheorem4.2. 85 4.5.3. ProofofTheorem4.5 85 4.6. Conclusion 86 Bibliography 88 -iv- KirillParamonov June2018 Mathematics EssaysinCombinatorics: CrystalonShiftedPrimedTableaux,bigradedFibonacciNumbersandData MiningonSocialGraphs Abstract This dissertation consists of three research projects in combinatorics, which come from three distinct branches: algebraic combinatorics, enumerative combinatorics and application of combinatorics to graph datamining. The first project explores the Schur decomposition of type C Stanley symmetric functions via crystal structure on shifted primed tableaux. We present a connection between unimodal factorizations that form type C Stanley symmetric functions, and shifted primed tableaux using Kras´kiewicz insertion. Then we present crystal operators on the set of shifted primed tableaux, which in turn allows us to find the Schur decomposition of its characteristic function (also known as P-Schur function). The class of shifted primed tableauxtogetherwithitscrystalstructurehasbeenimplementedinSage. In the second project we explore combinatorial properties of simultaneous (a,b)-cores with distinct parts. Weusethebijectionsbetween(a,b)-coresandabacusdiagramstogiveanotherproofthatthenumber of(a,a+1)-coreswithdistinctpartsistheFibonaccinumberFa+1. Wealsoprovideaproofforthenumber ofmaximal-sized(a,a+1)-coreswithdistinctparts,andfortheaveragesizeofsuchcores. Usingbijection between cores and Dyck paths, we show that the number of (2k − 1,2k + 1)-cores with distinct parts is equalto22k−2. Wethenfurthergeneralizeourideasto(a,as+1)-coreswithdistinctpartsandintroducethe q,t-Fibonacci numbers F(s)(q,t), motivated by area and bounce statistics of Dyck paths that generate q,t- a Catalan numbers. Bigraded Fibonacci numbers have nice recursive relations that turn out to be equivalent toAndrewsq-equationsrelatedtoRogers-Ramanujanidentities. Inthethirdproject,wedevelopnewmethodofestimatingthenumberofappearancesofaspecificmotif (likewedgeortriangle)inagraph. ThemethodusesHorowitz-Thompsoninverseprobabilityweightingfor thesubgraphssampledinaprocedurecalledlifting. Weintroducethreemodificationsoftheliftingestima- tor: ordered, unordered and shotgun estimators. Our method is universal and has better mixing time and -v- variance compared to other methods, which has been demonstrated both theoretically and experimentally. Themethodservesasastartingpointoffurtherdevelopmentofmachinelearningalgorithmsongraphs. -vi- Acknowledgments Firstandforemost,IwouldliketothankmyadviserAnneSchillingforherguidanceduringmyyearsin graduateschoolandforherpatienceduringmylastyear. Mycareerandresearchgoalschangeddrastically duringthelastfewyears,andIamverygratefulforhercontinuedsupport. IalsowishtothankJamesSharpnack, whointroducedmetomachinelearningresearch. Jameshelped metofindadirectiontomoveforward,hisenergyandenthusiasmfueledmylastyearintheschool. I would like to thank Eugene Gorsky for suggesting an interesting combinatorial problem, which re- sulted in Chapter 3, and for helpful discussions. I would also like to thank my co-author Graham Hawkes, whodidalotoftheoreticalworkforChapter2. I am grateful to many professors in UC Davis: Monica Vazirani, Greg Kuperberg, Fu Liu and Dan Romik for interesting courses and discussions during the first two years of the school, and for helping me with the Qualifying exam; Thomas Strohmer and Mimi Tsuruga for introducing me to Data Science; AlexanderSoshnikovforguidanceatthebeginningoftheprogram. IwouldliketothankthestaffofMathematicsDepartment,inparticularTinaDenenaandSarahDriver fortremendoushelpandsupport. Lastbutnotleast,Iwishtothankmyfellowgraduatestudents,inparticular myofficemateRobertBassett,forkeepingmesane. MyresearchwasfinanciallysupportedbyMathematicsDepartmentandNSFgrantDMS-1500050. IamverygratefulformytimeinUCDavis. IhavemetmanygreatpeoplehereandIhopeIcanmaintain aconnectionwithUCDavislongaftermygraduation. -vii- CHAPTER 1 Introduction This thesis consists of three parts, each corresponding to a single research project. Although the con- nectionbetweentheprojectsisloose, eachofthemrepresentsadifferentpartofCombinatorics: Chapter2 for Algebraic Combinatorics, Chapter 3 for Enumerative Combinatorics, and Chapter 4 for applications of CombinatoricsinDataMiningalgorithms. Chapter 2 is based on the paper “Crystal analysis of type C Stanley symmetric functions” [HPS17], written in collaboration with Graham Hawkes and Anne Schilling; Chapter 3 is based on the paper “Cores withdistinctpartsandbigradedFibonaccinumbers”[Par18],theideaofthepaperwassuggestedbyEugene Gorsky; and Chapter 4 is based on the paper “Estimating graphlet statistics via Lifting” [PS18], written in collaborationwithJamesSharpnack. Thereadercanfollowthechaptersinanyorder,dependingontheiracademicinterests. In this introductory chapter we introduce the necessary background and describe the main results of eachchaptertofollow. 1.1. CrystalsandtypeC StanleySymmetricFunctions. Chapter 2, based on the paper “Crystal analysis of typeC Stanley symmetric functions” [HPS17], has thegoaloffindingaSchurdecompositionoftypeCStanleysymmetricfunctions. Wewillstartwithgeneral theoryofsymmetricfunctions. 1.1.1. Schurfunctions. Apartitionλofnisafinitenon-increasingsequence(λ ,λ ,...,λ)ofpositive 1 2 l integers which sum up to n. Integers λ are called parts of the partition λ and n is called the size of the i partition. AYoungdiagramisafinitecollectionofboxes,orcells,arrangedinleft-justifiedrows,withrowlengths in non-decreasing order. The non-decreasing row lengths form a partition λ = (λ ,...,λ ), called a shape 1 s oftheYoungdiagram. 1 1.1. CRYSTALSANDTYPEC STANLEYSYMMETRICFUNCTIONS. AsemistandardYoungtableauT isobtainedbyfillingtheboxesoftheYoungdiagramwithpositivein- tegerssothatentriesweaklyincreasealongeachrow,andstrictlyincreasingalongeachcolumn. Theweight ofasemistandardYoungtableauwt(T)isvector(w ,w ,...),wherew countsthenumberofoccurrencesof 1 2 i thenumberiinT. A Schur function s (x) is defined to be the characteristic function of the set of all semistandard Young λ tableauxofshapeλ. Thatis, (cid:88) (cid:88) s (x ,x ,...) = xw1xw2... = xwt(T), λ 1 2 1 2 T T where the sum is taken over all semistandard Young tableau of shape λ. Here x = (x ,x ,x ,...) and 1 2 3 xv = xv1xv2xv3···. 1 2 3 Schur functions turn out to be symmetric with respect to x; moreover, they form a basis in the space of symmetric functions. Schur functions also play an important role in algebraic combinatorics and repre- sentation theory, since they represent characters of irreducible representations of the symmetric group, so they often serve as building blocks for characters of symmetric group representations. Therefore, decom- posingasymmetricfunction F intoalinearcombinationofSchurfunctionsisimportantforunderstanding representationcorrespondingtofunctionF. ThesumF(x) = (cid:80) K s (x)iscalledaSchurdecomposition. OurgoalistofindaSchurdecomposition λ λ λ oftypeC Stanleysymmetricfunctions. 1.1.2. Stanley symmetric functions. The Coxeter group of type A , denoted by S , is a finite group n n generated by {s ,...,s } subject to the quadratic relations s2 = 1 for all i ∈ I = {0,...,n − 1}, the 0 n−1 i commutationrelations sisj = sjsi provided|i− j| > 1,andthebraidrelations sisi+1si = si+1sisi+1 foralli. The Coxeter group of typeC , denoted by T , has the same generators and relations as S , except the n n n braidrelation s s s = s s s fromtypeAchangesto s s s s = s s s s intypeC. 0 1 0 1 0 1 0 1 0 1 1 0 1 0 It is often convenient to write down an element of a Coxeter group as a sequence of indices of s in i the product representation of the element. For example, the element w ∈ T with w = s s s s s s s is 3 2 1 2 0 1 0 1 represented by the word w = 2120101. A word of shortest length (cid:96) is referred to as a reduced word and (cid:96)(w) := (cid:96)isreferredasthelengthofw. ThesetofallreducedwordsoftheelementwisdenotedbyR(w). 2