Hey, everybody, welcome to the last session of the first day of Cloud Native SecurityCon. I expected around a plosh for that. Yeah, I expected there. You got the right idea. Yeah, I know it's the last session of the day. Thank you all for coming. There's just too many of it. There's like three less people. I just go around and we just have a conversation instead of doing this talk. But there's just enough of y'all do the talk. I do have stickers up here. So if you want this logo sticker, the shiny one, or one that says get guardian. Come up and get them afterward. Take as many as you want because I got to haul them back with me if I don't get rid of them. But let's jump in. So I'm Dwayne. I live in Chicago. I flew out here for this. I've been a developer advocate since about 2016. I used to work for a company called Pantheon. That guy over there did as well. This guy's just walking in. Hit me up on Twitter or Mastodon and MC Dwayne. I'm on Mastodon and social. But if you look at my Twitter, it directs you to the Mastodon social. Happy to talk about anything tech, but I'll also talk about improv and punk rock, rock and roll in general, karaoke. If anybody wants to do karaoke later, let me know. I work for a company called Get Guardian. Anybody here know Get Guardian? Awesome. We are secret management, our secret detection and remediation primarily. So if people hard coded their secrets, that's what we're helping people with. But we're also a platform helping people do other things like Icy vulnerability. Later this year you'll see more and more stuff from our platform around static code analysis. But I'm not here to talk about any of that. I'm here to talk to you about something that actually I'm passionate about. I'm not that deep into security. You've seen and heard from a lot of experts here today. A lot of people have been doing security for 20 plus years. That's not me. Instead, I got a crash course in this stuff over the last six months of my life and that's what inspired this talk. So what does good security actually look like? I think it looks like this. Yeah, absolutely. This is, I'm not worried the alarms are gonna go off at three in the morning. I'm not worried my perimeter's been breached. Good security means I can go camping and not worry about the house burning down. It means I go to my favorite concerts and not have to leave before the main act or the encore because alarm bell went off.  Look at look on those kids' faces. They are so happy to have their parents home. That's what good security looks like to me. Because all technology has a human cost associated. Whether we admit it or not, we can talk about S bombs till the cows come home. We can talk about automation. But at the end of the day, it is human beings doing this stuff. So what does bad security look like if good security looks like that? Well, I'll invoke Tolstoy here. All happy families are alike, but each unhappy family is unhappy in its own way. But there are some commonalities. We've all lived through Apache vlog for Shell.  It's very old at this point, 2021. But Uber from last year, who remembers this? It was a 19 year old kid in the lapsus group. Pwned Uber just cause he could. He got another Slack channel even bragged, hey, I own this thing now because you left your passwords in PowerShell scripts. They didn't believe him. So he went to the New York Times and that's how we found out about it. Just kid causing trouble. And then who fell victim to this? Who has circle CI in their infrastructure somewhere? Probably not anymore. Waking up on January 12th to have all your tokens just revoked. I don't know, fourth was when the revoke happened. Like that affected my company. All of a sudden the system just wasn't there anymore because there wasn't able to access it because hey, we got compromised. We just had to rotate this stuff. Still ongoing investigation. The full scope of this still isn't known. Who all has affected what customers with circles that have been affected? Still a mystery. But we can all agree, there's a pretty unhappy people overall because they're dealing with this. And these are 24 hour shifts of figuring out what to do and dealing with really, really unhappy customers. And security teams are really outnumbered out there. Alec Trice said it very succinctly. In the best of organizations, developers outnumber security teams 100 to one. That is 100 developers to one little security alarm over there. Just put in that perspective what that actually looks like. Again, this is the best of organizations. So what do we do? We just shift left. Let's make everyone wear the security hat. That's I think the fear of shifting left. Like what shifting left is supposed to mean is a little bit different than how I think a lot of people interpret it, especially from the gut reaction of developers who are like, okay, it's one more thing on my plate. You're okay, I got to do one more thing to implement. One more API to worry about. One more dashboard. One more, and I'm already fighting Kubernetes full time because man, everybody loves Kubernetes. It's only seven hours in the day. So from the dev perspective, like I can't just focus on that. And from the business perspective, who's paying for this stuff? Business perspective I think looks like this to security. I think it's getting better as more executives and more boards know what like S-bombs are thanks to presidential executive order. But security is simply looks like that. Hey, we got breach. Let's focus on security. Hey, everything else slowed down. Let's speed it back up. And let's go through that vicious cycle until, well, that's where we're at. And sure, there's a tool for that somewhere. One of these does something. We're on there somewhere, I think.  Who has ever read Through the Looking Glass? If you haven't read Alice Wonderland and Through the Looking Glass, read them, they're tremendously good books.  It's wonderful, wonderful, mathematic nonsense. But it's true. We have to run as fast as we can just to stay where we are at. And anywhere else, we gotta run twice that fast. That's exhausting. And that's why I think the industry has such crazy high turnover. That's why everyone's like 90% of people in America are looking for another job right now. This is why, I think, in part. And I think everyone that just saw all of that and was processing it, is thinking in their head, well, would it be nice if there was just a group of really nice people that just would help me with all of this? Well, there is. It's called OWASP. Who here is a member of OWASP? Yay! You probably didn't even need to come to this talk. Who here is familiar with OWASP? Yeah, more hands. Who here could explain OWASP to an audience? Well, that's what I'm doing, literally, so that I hope I can do it. OWASP stands for the Open Web Application Security Project. Started over 20 years ago. In fact, this is the 20th year. 21st year, depending on when you count dates and how all that. But anyway, there are a nice group of people that do nice things. They have a mission no more insecure software. But as we saw from one of the keynotes, there's no such thing as secure software. All softwares insecure. But if you set out the mission of like, hey, we gotta stop insecure software, that's a good mission. Cause that is a non-stop mission. And why not get there? It's a journey, not a, hey, we'll one day reach a peak. If you go read their mission statement, it's really well thought out. They argued a lot in meetings over this, I'm sure, for years, but they got to this. I'm not gonna read it out loud. It's pretty long. But you read this, you go to their website, you find this, and then I think everyone I've talked to that has hit their website says this. Yeah, but what do I do with this? This is a great website and all. How do I navigate this thing? Even Mark, Julie Chowley, give me just a second. Mark Chirpre, Cherfies, Mark Cherfies, sorry about that. Said in an interview last year, he was one of the founders of OWASP. Said, the organization has become a Byzantine labyrinth that new people cannot navigate. And that's one of the reasons he stepped away. I don't think it's that bad. I think it breaks down to like, hey, they do these five things. And all these five things are really, really deep. And that's like why I think people get confused. So I'm gonna break these down and then talk about how to get started from where you're sitting. So first is projects. This is the thing they're known for. The big one they're known for is their top 10. We'll get to that in a bit. But basically a project is just an open source repo you can contribute to or go pull code from or go look at, go examine. Volunteers built it. Some of those people are experts. Been doing this for 20 some years. New stuff comes in all the time. I just updated this and I'm not 100% sure these numbers are right. But I just updated this yesterday or Monday. 250 total projects in any conceivable state. And 157 in a usable state. What do I mean by usable? They're in one of these states. Flagship projects, production projects, there's no production projects right now. But that's something they invented in October of 2021. I don't know, October 2022. Say nobody knows what flagship means. So we're gonna make a whole new category called production ready projects, production projects. And we'll move flagship projects over there once they qualify in. We're in January of 2023. So far nothing's qualified in because it's the crazy giant list of things you have to check off. And even top 10 doesn't qualify at the moment. A Zap doesn't qualify because of all the bugs. But we'll get to that later. Lab projects. And then incubator projects. Then there's a whole bunch of others that don't qualify on anything like that. So there's 18 flagship projects currently. These have some kind of serious strategic value. If you're gonna start anywhere, start with these flagship projects. Just roll through them and say, hey, could I use this? But that's still putting a lot of weight on you. We'll get to that later. 34 lab projects. Labs aren't quite flagships. They're being worked on. They have a website.  But they're not quite ready for me like, this is what OWASP is known for. But they still have a lot of value. But some of these are very specific to languages like Python and whatnot. Then you have incubators. These are on the way to be in lab. A lot more of them. If you're gonna go make an impact in an open source organization, this is where I would direct you first. All of these have pull requests that are waiting to happen. All of these have beginner friendly. They need documentation like crazy. Developments underway. And then there's a whole bunch that just don't fit in there. So that's the first way that they organize them is by projects. Or categories, I should say. Categories. Then they also organize them by types. So you can go and say, hey, I wanna work on a tool or I need a tool or I don't look at documentation. And they laundry list it this way as well without much explanation. And you might notice, fun fact, these numbers add up to more than 157. And remember I said earlier there's 157 in the usable state. Why is that? I don't know. I wish someone could explain that to me. If you know the answer to that, please have a conversation with me afterward. But this is the state of OASP right now. But they said, hey, I recognize this is a problem. We need to make it more usable for everyone at home. So this is the software development lifecycle in their opinion. If you go look at it, it's a nice map, interactive. You can say, all right, I am at the design phase. Those four projects might help me out. I'll go investigate there first. This is on their website. You can go play around with it. Along the way of building this, they invented the CRE, the common requirement enumeration. OASP CRE became a project into itself like everything else. Open CRE.org. If you don't visit any other website after this, put this like third on your list. But it's a way to very quickly see, hey, I have a high level concern, a high level topic I need to drill into, quick way to see INST and CWEs and all the other acronyms. They strung it together in one nice resource for you. So that's the first way. I think you can start thinking about OASP as projects. It's a lot of them. There's a lot there. But it's a good way in. Maybe the better way in is getting involved in the community. And don't worry about the global history, 20-year history of projects. And just go talk to people. Chapter's all over the world. And just like we're here in Seattle, you can just go hang out with people. This is what it looks like in Paris. Back in October, this was in the GetGuardian offices. GetGuardians based in Paris. But this is the OASP meetup in Paris. Who here lives in Seattle? One person. Yeah, you got lunch and lunch. Coming up on this coming Wednesday. It's online, so everyone in the room can join in. In fact, a lot of the community meetups are online. Or some of them are, I should say. It used to be a lot more, but then they've slowly been transitioning. I was going to the Ottawa chapters for a while, but then they stopped doing them online. But it's people you can go talk to about security stuff. Just other security nerds. They also hold events.  Next big one is in Dublin in two weeks. A whole bunch of training, but the APSEC day is in, the next big APSEC day, I should say, is in Ireland. Education or training? You can just Google or DuckDuckGo or U.gov or whatever you want to use. Search for OASP education or training. You're going to run into a list like this and you're going to find, wow, there's a lot of resources because every good-hearted soul who I wish more people knew about this probably started a project at one time and started trying to train people on that specific topic. But there's one word they partner with and I'm not here to sell you on them. But Secure Flag is awesome. Just flat-out stated. They have a partnership with OASP. OASP membership is really cheap. It's 500 bucks for a lifetime or 50 bucks a year to be a full-blown member of OASP.  And you can go take dozens, I think 100, I forget the exact number, it's over 100 types of trainings on here. Like full-on capture of the flag events, the whole community exists around this alone.  But along the way, you learn all about how to cryptography in Java or secure authentication in Java. I don't know why I picked Java when I made this, but I think Java was on my mind. They also make a lot of publications and resources out there. A lot of these cross over with projects and that's where they come from. But there are also our physical books you can buy. Are they up to date? I don't know how time works. So maybe, yeah, so they do a lot. And you're probably still thinking, like, all right, what do I do with this? I could go spend four hours of my life digging through the projects, hoping to hit on something. I think there are four ways in that are really, really simple and actually practical day to day. First is top 10. Who here knows or heard of or even looked up ever or saw a reference somewhere, they all lost top 10. Every hand in the room. Almost every hand in the room. Some people are asleep, that's fine. It's the end of the day. 10 types of attacks going on in the world. Vulnerabilities out in the world. I say type 10 types of attacks. They don't say that, that's me. But that's a good way to think about it. Like, all right, I'm worried about my app being secure. What are the top ways I know I should secure it? Well, it's top 10 list. Every year it changes. They haven't come out with the 2022 list yet. Coming out later this year. I'm actually really curious to where cryptographic failures will fall this year if it goes up. It's gone up every year. It's been on the list. Broken access control. It's gonna probably stay at the top. But this is gonna be me saying this. The top eight are based on industry data. The last two are based on surveys of members. Saying, hey, what should else be on this list? So server side request forgery isn't by data, one of the biggest threats in the world, but all the members said, hey, this should be on the list. People should know about this. So it's not just a list and like, hey, good luck. It's a project. There's a repo for this. It goes really deep. I think the most important part of it is this one. How to prevent. There's a whole section. So if you're building an application and you're thinking, hey, how do I secure this thing? Go to the top 10. Go to how to prevent for every single one. Run through it. May just make a checklist. I'm a big believer that the best security tool ever invented is Excel spreadsheets because you can make a checklist. Real easy. Did we do it or not? Is the box checked? Make a big check box. It's probably somebody already did that with this. Probably just Google that. So that's top 10. Won't spend any more time on that. Cheat sheets. Man, I love cheat sheets. Cheat sheet series at OWASP.org. This is the one you should definitely visit if you don't visit anything else.  This is a website for you that can walk in and say, hey, tell me about Kubernetes security. And while you're talking to them, you can slowly Google or get to the OWASP cheat sheet and then a quick scan over the page like, OK, I understand how this works now. It's a bare bones, like as fast as you can go, as fast as you can read it, overview of all the issues known. Is it complete and 100% thorough? No. Is it good enough to make you sound like an expert in 10 minutes? Yes. Should you do this on the regular? Probably not, but this is a good way to start. If you've just taken a course in something and like, all right, I need a cheat sheet to hang out with me to remind me of the key things. They already wrote one for you. That's my point. So cheat sheets, definitely look them up. The goats, the goats are great. Goats are not the greatest of all time. Maybe they are, but deliberately insecure applications.  There you did it. There's a bunch of them. Pie, goat, lab projects, wrong secrets is awesome. I'm a very big fan of that one. We've done a whole webinar with them, with the maintainer. And it's how not to store your secrets. How specifically not to do it. There's a project to show you how to do it. But the greatest of all time of all of the goats is Juice Shop. Who here knows Juice Shop? You're gonna love Juice Shop. This is the one to download. This is the one I got running a Docker container right now. I'll show you in a second. But Juice Shop is a fully functional, bug-free application that's completely insecure, according to the last pop 10. Super well documented, tons of articles about it. One of my favorite talks I've seen in the last year is on YouTube from Bjorn, that breaks down how to use it. So Juice Shop looks like this. This is around my local. And yeah, it's just a, it's a Juice Shop. But it can, do I still have my cross scripting in here? No, I don't.  It's a built-in CFT, or Capture the Flag CTF built in. So if you go to Scoreboard, yeah, it's a full on tutorial on how to hack a website that tracks your progress as you go, with tips and training as you go. Not just how not to build a website, but how to attack a website. All in one awesome thing you can run in a Docker container that you get up in seconds that scales. It's amazing. So Juice Shop, go check it out. Definitely should have it running. Zap, who's ever run the ZetaTax Proxy? Cool, got one in the back. Yes, yes. Zap is a tool you should be running, or at least run occasionally. Only against things that you control, that you own. You have permission to attack. Don't just go randomly attack websites with this. Please don't. You could, but don't. It's an automated scan that literally goes and attacks down the list, and tries every dirty trick currently on the top 10 list. And then builds a nice report on what went wrong. So yeah, there's only nine alerts, but like, cross domain can misconfiguration, there's 40 in instances that. Oh, this is against Juice Shop, by the way. This is how insecure Juice Shop is. So yeah, cross site scripting, session ID, URL rewrites. There are a lot of known bugs with Zap, and that's why it's not in the production-ready camp right now, previous conversations is like, well, this tool isn't built for the enterprise, but at the same time, it is built for the enterprise. Anyway, oh, Zap is awesome. Download it, run it. These are the four ways in. But, all right, I'm gonna wrap up. It's dangerous out there. There is a group of people that wanna help you. They're called OASP, they've been around for a long time. It's a Byzantine labyrinth to get through. But, if you go talk to the people involved, they're all nice. They all wanna share their knowledge. They all want you to succeed. They all want you to sleep better tonight, and have better security, and stop writing insecure apps. And I would start here. Before last week, I probably wouldn't have said start with JuShop, but JuShop is just fun. I've had to have a lot of fun with it lately. When you get to the advanced things, it's like, wow, I've never even thought of that for application security. Zap is a much quicker way to get to like, how do I make my application secure? Not how do I learn how to not write bad applications? But that's it. And if you don't know the top 10, that's one you should bookmark. And every time you think of building your application or changing your application, just go to review the list. Anyway, I've been doing, I'm a developer advocate, have been for a few years, hit me up on Twitter about anything, rock and roll, B-Sides tech. I gotta fix that. But I do love B-Sides, they're awesome organization. And that's my talk. Any questions? Back there. When I say the bug list, I mean the issue queue, and it's still there. That's the conversation, literally the same conversation I had in West Virginia about Zap. Is an enterprise ready? According to them, yeah, can you automate it? Ooh, there's problems with that. And there's issues, known issues with it, unfortunately. But they do accept pull requests, and they are open source. So if you can make it work, you can make it work. But that's not a great answer. But I'm actually, you know what? I've got enough time. Let's just, this is like, automate. I haven't seen this before. This must be fairly new. No, there's a path. There we go. 90% of what I know, I just Google or look up on DuckDuckGo. Any other questions that I can help other people with? Well, enjoy the rest of the event, and thank you very much for coming out to my talk.


So, this week, we are excited to have Justin Troika from David's College give us a talk, and he will be speaking about split graphs, combinatorial species and asymptotics. So without further ado, go ahead and take us away. All right. Yeah. So it's great to be here on campus. As you can see, I'm in a room full of people. Yeah, and this is so I'm Justin Troika. Yeah, I've met at David's College. Oh, yeah. Thank you for two years. This is what my face looks like. I'll keep this on for a second. Can you all hear me? Yeah, where this is a small room. Okay. Can people on zoom hear me? Okay. Probably if not, let me know. So yeah, it's great to be here. And I am. Thank you. I'm going to talk to you about a research project that I did and that I'm kind of still doing part of on split graphs. So I don't know who in the audience is dealing with sort of does like enumerative combinatorics but that's sort of my area is enumerative combinatorics and I do all kinds of things with that with usually counting permutations. So that's going to be more about counting graphs. And like I was telling some of you before the talk, counting graphs is not a good idea. There's a there's too many of them, which sounds funny but like, so, you know, the number of simple graphs on and vertices. Well, each pair of vertices there either can be an edge between them or not be an edge. So that's two to the power of the number of pairs of vertices right and so the number of pairs. So that's, that's not just exponential like two to the end that's like two to the, you know, o of n squared. That's, it's, which is even bigger than n factorial it turns out so in fact and so usually when I'm working with permutations, like n factorial. There's n factorial permutations of size and that's already kind of pushing it in terms of how many combinatorial objects were dealing with so this is just crazy but you know there's the interesting thing is there's still, there's still meaningful side about, like the number of graphs with certain properties of each given a number of vertices. And I'm going to tell you about some of those sort of recent areas of research, sort of avenues of research that I found interesting and that I have contributed a little bit to. So yeah, okay, let's, let's get to it. So, yeah, these are the outline of the talk first I'll give you a little bit of background to tell you what split graphs are. I'm going to, then I'm going to talk a little bit about labeled graphs versus unlabeled graphs, the distinction is important when you're counting them. And usually labeled structures are a lot easier to count. I, you know, went through the fact that there were two to the power of and choose to labeled graphs on and vertices. So if you want just isomorphism classes of graphs that's a much harder problem and you have to use group theory basically and you have to count, you know, symmetry groups of different graphs and things like it's like that. And then, then we also have that and then I'll tell you sort of what I might my contribution to this. And I drew the drew all the pictures this morning before I drove down here from Davidson. A split graph is this is how it's defined it's a graph whose vertices can be partitioned into a clique a complete graph and a stable set or an independent set.  It will be called s. So here's an example of one as you can see all four of these vertices are adjacent, right every pair of vertices on the left is adjacent to each other. Every pair of vertices on the right is not adjacent, and then we have whatever edges we like between the two pairs there, you know, between the two sides. Similar idea to a bipartite graph except that instead of two independent sets with some edges between them we have a click and independent set. And that is that that there actually is a pretty important connection between these and bipartite graphs from the point of view of what I'm going to be talking to you about. So we'll get to that soon. So a, then a K s partition is a partition of a grass vertices in this way where you have a click and you have an independent set. So these are the types of graphs that we're talking about. And by the way, if anyone has any questions, I mean I'll try to stop periodically and see, you know what questions people have. But if you know if anyone wants to just raise your hand I feel like it's small enough group we can sort of be a little bit informal so yeah. So what a split graph is. And so, now I'll tell you a little bit of their significance they've been studied for several decades they're a well known class of perfect graphs. So and it turns out split graphs are precisely the graphs such that the graph is a chordal graph and it's complement is cordal cordal meaning any cycle of size four or more has, you know, it has a chord, basically, you know, connecting vertices that are not adjacent in the cycle. So that that's a different characterization of split graphs than what I've just given you but it's equivalent. There's a summary of some of the known facts about split graphs in this textbook there's a there's a section of the textbook on split graphs. And the main paper from this era on split graphs is from by hammer and I don't know how to say this person's name Simeone or Simeone 1991 1981, where they characterize split graphs by their degree sequence there's a paper that says a graph is a split graph, if and only if the, you know, the multi set of the degrees of its vertices satisfies such and such properties. So you can tell whether a graph is a split graph just by looking at the degrees of the vertices. And hence, there's an efficient algorithm for identifying split graphs you just look at the list of the degrees, see if that list satisfies the degrees, which is not quite which is not really all that relevant to what we're talking about today just wanted to give you a sense of the history here, and how they were studied by you know real graph theorists and. And now, now there's me coming in from enumerative combinatorics. So, and so here's the, the counting stuff that has been done on this. So, Royal in 2000. So, again, there's the distinction between counting the unlabeled split graphs versus counting the labeled ones. And we'll, I'll talk more about that in the part two of the three you know three parts of this talk. So, the enumeration of unlabeled split graphs. So in 2000 Royal found a bijection between the unlabeled split graphs on vertices and minimal set covers of size at which actually don't remember what minimal set covers are but there's some sort of, you know, graph or hyper graph like a biject that has certain properties. Then the 2018, the paper by Collins and trink, which is, I think, oh no this is, I forgot this is this should say this is going to work. This should be saying Collins and trink 2018. Yes that showed up wonderful. I wrote have a paper where they establish bijections with several different combinatorial objects, including by colored graphs, where the two color classes are colored red and green, such that no green vertex is isolated. And I am going to show you a little bit more about that later on in the talk. They also can, there's a connection to bipartite post sets, essentially establishing that all of these different types of combinatorial things are counted by the same sequence of objects and they be proved this using bijection between between these various objects. Yeah, and then the. So then for labeled split graphs in 1985 it's shown that a bunch of different types of graphs have the same asymptotically the same enumeration so this is an asymptotic enumeration question. So we're saying s s n denoting the number of labeled split graphs on and vertices is the same as b n, the number of labeled by colored graphs on and vertices. So these are asymptotically the same as n goes to infinity, and it also establishes that one of the other types of graphs they were counting already had a known formula. And this is essentially what the formula was it was some constant times and choose n over two times two to the n squared over four. This should be understood as so like this term. So okay if you think about how to actually count by colored graphs. So you can choose how many vertices are red versus green, right, or you can, and that's so you'll have a term for each K for each K you'll have, you know there's K green vertices and minus K red vertices. And then you have to choose K of the end vertices to be green, let's say, and so there, that's where this binomial coefficient comes from, and then there's two to the power of K times and minus K, well there are the formula later in the talk I just wanted to point out that this term here is actually just the middle term of the formula which is saying that basically the majority though not the proportion does not go to one as n goes to infinity but a majority of I think it's a majority. At the very least a constant fraction of approaching a constant fraction of the by colored graphs on and vertices are have are equally distributed between the two colors. But in any case, this was done in 1985. And then in 2015, there was a Bina and pre bill gave a formula for the number of split graphs as a double labeled split grass as a double summation involving binomial coefficients. So, yeah, are there any, any questions so far either from either from the people watching on zoom or from the people in the room here. Let me figure out how to, if I go to the next slide the, I go to the next slide the person's name will still be there so I have to figure that out. Here we go. Clear. Okay. There. So, now more on split graphs and this is really mostly going to be going into the Collins and Trank paper as well as a predecessor. Oh, Chang Collins and trying paper as well as a predecessor paper. Oh, no, this one. Yeah, as well as this one is just Collins and Frank, there's a different paper that's Chang Collins and Frank. Okay, so I didn't even need to write that in in the first place. In any case, this is sort of what their research was on a split graph is balanced. If so this is I'm introducing the notion of a balanced split graph. And what that means is that the chaos partition in other words the way of breaking it down into a click and an independent set is unique. It is the chaos partition may be unique and may not be. So, and if it's unbalanced if there's more than one chaos partition. Now, so the example that I showed you at the beginning is an unbalanced split graph, and what makes it unbalanced. So here it is and what you can see is that actually both of these vertices are adjacent to everything in the click. But they're also not adjacent to anything in the independent set in the stable set. So, we can swing one of them over and the calling it a swing vertex was not my idea that was in the paper that I was referred to earlier the Collins and Frank. So we swing this vertex over here and put it in s instead of in K, and this is still a perfectly valid K s partition where we now have just these three vertices in the K side, and these four in the S side. Right, because this is adjacent to none of these so it can go there as well. We can't move both of them because they're adjacent to each other, but we can move one of them. Yeah. And so what else do I want to say about this right so now and this is sort of the only thing that the only difference is that in any any two K s partitions just differ by one in the size of the parts like there's, you know, you can't. So in this case, K will always have four vertices or three vertices. So it's when it's unbalanced there's not really too much freedom and what you can do. But in any case, the right and so we're going to call this partition, the K max partition because it's of the two sizes of K this is the larger one, and then this one is going to be the s max partition, because s is the larger of the two in this one. So, here is sort of one of the main theorems of the work of Chang Collins and trach from 2016, which is that this number the number of unlabeled the tilde anytime there's a tilde over a letter it's going to be an unlabeled graphs. The number of unlabeled unbalanced bullet graphs on end vertices is equal to. I mean, basically what this is saying is this is the number of split graphs of any with any number of vertices up to n minus one. Or you can state this in terms of generating functions in this way. So the generating the ordinary generating function for the unbalanced is equal to x over one minus x times the, the total split graph. Generating function. I will show you a sketch of this proof. And we're really considering it as sort of this. So when you think of it this way. When you multiply, of course, when you multiply to generating functions to ordinary generating functions what that amounts to is that we have some sort of non empty sequence, and then also a split graph. So x over one minus x rep one over one minus x would just be some sequence of, you know, points, and then x over one minus x means it's a non empty one. And so the proof of this formula is this given an unbalanced split graph like this one, what we do is take the K max partition, and the K max partition is unique. If we're talking about unlabeled graphs, it's there's only one possible K max partition. So what we're going to do is take the swing vertices and just remove them from the graph. And so this graph just becomes this right so what and then what remains is an arbitrary split graph. And that's essentially the proof, because here these, you know this, because it's a K max partition there must be and it's unbalanced, there must be at least once one swing vertex. So this x over one minus x represents the swing vertices that are in K of a K max partition. So when we take those off, what remains is the s the arbitrary split graph which may end up being balanced or unbalanced. Yeah, and so this is the proof that was in that paper from, I guess five years ago now. And the thing I want to point out is that this does not work for labeled graphs. Right so this paper was not really concerned with labeled graphs this was about just counting isomorphism classes of these which is, you know a pretty normal thing to do with graphs. But the reason this does not work for labeled graphs is because it relies on the uniqueness of the K max partition. And it's possible that a split graph can have many distinct K max partitions that are isomorphic to each other and so when you're counting unlabeled structures would just count as one thing, but counts as many things if you are looking at the labeled structures. So I think of like, it's the difference between. Well so you know it's the difference between moving this vertex to the other side or moving that vertex to the other side, the two partitions are isomorphic to each other but if these vertices are distinguishable they're technically not the same thing. Yeah, and a lot of my work sort of focuses on on untangling that and trying to find something that generalizes where it works sort of on a level that can be applied to labeled or unlabeled essentially, in a sense that I will make clear. This would be another good time I think to step through. Are there any questions or, you know, observe, you know, any comments people want to make or anything. Oh, on the on this. Oh yeah so this is just, this is signifying that we're adding up all the, all the number, like the number of zero vertex split graphs, plus the number of one vertex split grass plus the number of two vertex click graphs and so on. Yeah, yeah, yeah, I guess yeah you have to, I guess for zero, let me think, yeah, is the empty graph the empty graph can indeed then be partitioned into that because right then K would be empty as would be empty that's allowed I guess, and then s one would be the graph on one would represent the graph on one vertex. I guess which is. Yeah, that's certainly yeah that's a split graph, and I guess it's an unbalanced split graph because that vertex could count as K or s. And then as and then I think from to and on it becomes more understandable what's meant I think, but yeah that's a that's a good question the base case, you would do have to make sure we have the base case but there's a natural way of doing it. Yeah, yeah good. Anyone else. What was that. Yes, yes, either K or s can be empty. Yeah, there's no restriction on them being non empty. Right. Yeah, that's a that's a good point. Yeah, anyone else. Okay. All right. So now we're gonna I promise you we talked about labeled versus unlabeled graphs. Yeah, so this gets into a lot of if you've ever studied, you know, like the like the poya enumeration theory. That sort of thing is really what is coming into play here and I'm not really, you know, I could, you know, you could teach an entire class on that and I'm really not going to be able to go into the details but that's really what's going on here that we're talking about a group action where and you know isomorphism class or equivalence classes under the group action. And in this case the group is going to be the entire symmetric group on n letters. Okay, so, and instead of going through all of the details of that I'm just going to illustrate with an example. A labeled graph is a graph with n vertices labeled one through n. Yeah, so each, each, and then each of the labels is used exactly one so you can think of it like it's a graph where the vertex set is the equal to the numbers one through n. So there are eight labeled graphs on three vertices. And here they all here they all are. As you can see we count these as three different graphs because the edge one two is different from the edge to three, and they're different from the edge one three right. So there's eight of these and I arranged them so that each one is sort of above its complement, which I thought was nice. So, now what we can do with these, right, we can think about sort of bijections that relabel the graph. So we can say, you know, in this graph what if we change the one to a two and change the two to a three and change the three to a one. And when we do that right so that's some permutation of the numbers one two and three. And so permutations of size three. Or let's say the symmetric group on three on the numbers one through three induces a group action on these objects where by relabeling them. And so that's what this diagram shows. So as you can see, first of all, let's look at this graph. If you switch one and two. Because one and two started out being adjacent. When you switch one and two they are still adjacent. So the transposition that that transposes one and two fixes this graph this graph is sort of is fixed by or is invariant under that transposition. But then if we apply the 123 the cycle, the three cycle, then one becomes relabeled as to so to becomes relabeled as three so the edge becomes two to three. That's what this graph is. So 123 induces, you know, a map that sends this graph to this graph, and then this graph gets sent to this graph. This graph gets sent to this one again. And so, as you can see then the idea here is that we, we have an S3 action on the set of eight labeled graphs on three vertices. And I didn't draw in every single one of the six elements of the group but you know you can imagine how you would like so to like the 23 transposition would have this one fixed. And it would switch this one and this one right and then similar story down here. And then of course every element of S3 keeps this fixed because no matter how you permute 123. No edges. There's only one graph with no edges right. And same thing with the complete graph. And so what we what happened is, we get these orbits which I've drawn a box around each of the orbits of this group action. Right so the orbits are just, you know, you the equivalence classes where you consider two things equivalent if there's a group element, there's a permutation that maps one to the other. So in this case it's all of the ways of relabeling a graph are in the same equivalence class. And so what we get from this is, we can think of each equivalence class as an unlabeled graph because we're sort of considering all of the labelings in the same as the same graph, if we are considering an isomorphism class here. So an unlabeled graph then we can define to be simply an equivalence class of labeled graphs under the action of the symmetric group.  And so we could do it this way instead. This way we also get to do more combinatorics because the symmetric group acts on it and that's nice. And so there are four unlabeled graphs on three vertices that's 123 and four. But of course, you know they're sort of different right this graph has is these two graphs are perfectly symmetric and these two graphs have some asymmetry to them. And so there are more things in these equivalence classes than in these. And that sort of any time you're trying to count unlabeled graphs, you kind of have to think about like, you know, counting the ones that have certain symmetries. And then you use like the Burnside enumeration lemma, where like, I guess the lemma that is not Burnside I've heard it called because it was actually by like Toshi and Frobenius or something like that. And, and, you know, to count the orbits under some group action. Yeah, questions about this so far. Because, yeah. Okay, yeah, I think, and I just think it's, it's really fun to think about I like thinking about group actions a lot. So, so now to give an example of the sort of counting problems involved. So as we talked about the number of all labeled graphs on and vertices is two to the power of and choose to which we can call G seven. The number of all unlabeled graphs is, I, you know, it's, you can it's, I didn't really, you know, it's hard to I don't know it off the top of my head like I do the other one, you know, it's some it's there are several nested summations involved, because you have to count the equivalence class and you have to kind of do it according to like, you know, looking at sort of the different symmetries, and looking at how many graphs are fixed by every possible permutation that induces a relabeling. So this is found by Poya in the 1940s, you know, as part of the sort of theory that he was developing for enumeration under group action, which is a very fun topic as I've said. And so, now, in more generally, right, we so like I said this is an example of the sort of thing we can think about with what's called combinatorial species. And the idea here is, if we have some towards some kind of combinatorial structure, we're getting very general here. If we have some kind of combinatorial structure where fn counts the labeled structures and fn with a squiggle over it counts the unlabeled structures. Then here's what we can do we can define f of x. Exponential generating function for the labeled structures, we can also define the ordinary generating function for the unlabeled structures, but just by putting the coefficient those those counting sequences as the coefficients. And briefly the reason why labeled structures get exponential generating functions, while unlabeled structured get ordinary generating functions really boils down to the multiplication rule. The two ordinary generating functions together, the coefficients of the product are a convolution of the coefficients of the two generating functions. And that's exactly the type of multiplication we want when we're looking at unlabeled structures, because multiplication of generating functions of ordinary generating functions for unlabeled structures corresponds to sort of a concatenation of the of the unlabeled structures that you were that were counting. But then if they're labeled structures, we're not just concatenating them we're also choosing which label, which subset of the labels to use on the first one and which subset of the labels to use on the second one. So it's not just a convolution here, what we really want is a convolution times and choose K. And the application by and choose K is achieved by using an exponential generating function where we have this impact or real in the denominator. So just briefly that's sort of why that's why it's different. And so if you're ever trying to count things and you're not sure whether to use exponential generating functions or ordinary generating functions. It really boils down to, you know, do we have to re worrying about which labels go on each thing or not. So I'm very like, broad, broad strokes idea here, I'm not, I'm not saying anything rigorous here but that's the general idea. Okay, so this slide is going to be, I'm just, it's not really going to come up that much in the presentation if you don't understand what a combinatorial species is after this you will still get what the rest of the slides are saying. But one way of defining it is basically as a sequence of sets one set for each natural number where FN is equipped with a group action by the symmetric group on N lighters for each end. This is the sort of more. This is the more concrete way of doing it in a little bit I'll get to sort of the real way to do it, which involves category theory. But for now this is what a species. This is how I think of a species anyway. And so this set here what we're thinking of it as is the set of labeled structures of that type. And then this, which is the set of orbits under the group action is the set of unlabeled structures, right so in the example of just the species of all graphs. This would be the set of labeled graphs that those eight graphs that I drew, and then they're, they're, they're acted on by S3 or in general the you know graphs on and vertices are acted on by SN. And then the or the orbits under that group action. This is the set of orbits under that group action and that is where we can think of that as the set of unlabeled structures. Right. Now, yeah, so an isomorphism between species is going to be then a bijection between the sets of structures that commutes with the SN action. So it's essentially a, it's a, oh gosh, yeah, it's an isomorphism between the, the, like the SN sets, so to speak. So if you relabel the F structures in some way, and then apply the bijection, it's the same as if you first apply the bijection, and then relabel the G structures in the same way. Right, so it's just it's sort of a natural isomorphism. And really what this means in terms of labeling and relabeling is that it's a bijection on the level of the labeled structures that respects relabeling so that it also in particular it also will induce a bijection on the unlabeled structures as well. And it's actually even stronger than that it's stronger than the labeled structures being the same and the unlabeled structures being the same. When two species are isomorphic it sort of signifies a combinatorial equivalence that is really nice to have and it's saying that you know for combinatorial purposes these are really the same object. So when we make a state when we have a generating function identity, and we generalize it to a identity of combinatorial species that is saying something much stronger. And that is how I convince you that the results I'm about to show you are actually good. Like I said so the real definition of a species if you, does anyone here know category theory or like have been exposed to category theory, a little bit. So yeah, me also a little bit, but these are the words involved that a species is a functor from the category of finite sets with functions. If you go through the definition of a functor, and you write down what it means in the specific case, you'll basically get and then and well, and then you look at what it means, specifically when your finite sets involved are the numbers one through two, you will get exactly what I wrote up here. I think I haven't done that in a while. And then the real definition of a species isomorphism is simply a natural equivalence of two funcars if the species are functors, then a natural equivalence between two functors is a thing from category theory. And that's what it means for two species to be isomorphic. So very, very fun stuff, but you don't actually need to know any category theory to to understand species theory. So what, what questions do people have about this because I know I just threw a lot at you, but after this we're going to get back to split graphs. All right, so back to split grass. So yeah this is a paper that ended up being published in 2019 and the electronic journal of combinatorics. And so here's what, here's, here's, here's the main idea. This is the theorem that I showed you earlier I showed you sort of a sketch of the proof. It was very nice it involved the swing vertices. And what I did was I proved a species version of this, where this you is the species of unbalanced split graphs. S, this S is the species of split graphs just unbalanced or balanced. And then the the E here denote this is sort of one of the sort of basic types of species. You know, it's just the species of sets. So the species of sets is for each end, there's only one set for each for each possible label set. How do I define this right so for so for yeah for each end. It's just the only set of size and is just the numbers one through and you can think of it as like a set of isolated vertices. And then all of the relabeling just give you the same set back because there's no relationships between any of the vertices or any of the, you know, numbers one through and they're just a, you know, they're just an undifferentiated set of things. And so for the species of sets, since there's just one of each size, the unlabeled generating function for that is one minus one over X. And so when we specialize to unlabeled structures by putting in for the species you we put in the ordinary generating function for the unlabeled know the for the, the, yeah, for the unlabeled things same thing for s, and then we put in that we put in this for e.  And if you get bored for the rest of the talk, you can try you know get out some scrap paper and try to work that out yourself. Take this, you know, weird formula, and put in, put in e of x equals this and then when the dust settles you do actually get this back, which is which was, you know, I was relieved that that happened. And then if you on the other hand if you specialize to labeled structures, which because there's again there's one set of each size that's the set species, the generating function is e to the x since we're doing an exponential generating function. So if you put an e to the x here and here, then what you get is a new enumeration theorem that expresses labeled on balance split graphs in terms of labeled split graphs which is not as nice as this, but it's the same type of thing. And both of those identities come from this, which is stronger than both of them and sort of encompasses them both. And we'll say the way that I got this was not direct. I mean, look, there's subtraction there's division it's not going to be direct. So what I mean, it amounted to the same type of proof that I didn't want me to go back a little bit the same type of proof that I showed you in this picture. But I just had to be a lot more careful about, you know, whether there was a unique K max partition or not.  Here, I had to define a few other types of species, and then get a bunch of equations relating them that start out on like the bijective level but then end up being indirect because I had to, you know, basically solve a system of equations, where the things in the equations are the symbolic combinatorial species. So that's fun. It actually well I, you know, it was messy but it was I it was it is actually fun I think. The, so the point of this slide is this cool thing generalizes to the level of combinatorial species. That's the main idea here. Yeah, questions what are people's questions about this. All right, so moving on, I mentioned that by colored graphs were going to come up. So here's where they're coming up. The colored graph is a bipartite graph with a chosen bipartite. It's basically we use by colored graphs when we want to talk about bipartite graphs but we don't want to have to worry about the fact that there might be, you know, different ways of splitting up the vertices in particular if it's not a connected graph, each connected component, you can decide to put, you know, one of the classes on the left and one on the right or you can switch them right and so the total number of ways of coloring a bipartite graph will be to the number of the number of connected components. Right and so that is annoying to have to deal with. And so to get around that we can instead look at by colored graphs which means it's a bipartite graph equipped with a specific bipartisan. Right and so, and for the sake of you can think of it as like one part is colored green the other is colored red. And the reason I chose green and red for this paper and for this presentation is because they're going to end up corresponding to the K and the graph. So there's Kelly green and there's scarlet red. And so those are the chaos partition is what they're going to turn out to be. And so this is an example of a by colored graph. And as what I was saying was so for instance, this is an isolated vertex. So like we could choose to put that on this side or we could put it here and those would be the same bipartite graph, but we're counting them as different by colored graphs if we decide to color this one green instead and put it over here. So like this component here, you know we could have put in these put these two vertices here and this one here, and we could or we could have put this one here and color it green, and put it there, and then put these two vertices color them red, put them here. And so those would all count as the same bipartite graph but they count as different by colored graphs. And so the number of by colored graphs on and vertices is simply this summation, because again, we're choosing K of them to be green. So choosing two to the power of, you know, K times n minus K is the number of ways of choosing the edges between the two halves between the two colored classes. And then this is the thing this is the same term that showed up earlier in the presentation of just right this is the, this is sort of dominated by the middle term of this so that's why there's n choose floor of n over to, and then the, if K is n over to n minus K is also what you're going to do and then you get n squared over the floor. And then the theta of just means it's a constant, basically it's a constant times that I didn't want to get into the details but the constant actually depends on whether, whether, whether n is odd or even it's a just slightly different constant. Yeah, and this is, yeah. So, so yeah by colored graphs are easy to count, even though these again these numbers are way too big, but they are easy to express. And now what we can do. And what we can do is express. So this is for the labeled ones. Again the unlabeled ones is harder and you have to so I mentioned that for graphs unlabeled graphs were counted by poya in you know his seminal work on, you know, the enumeration under group action. The same ideas work to count the by colored graphs unlabeled by colored graphs or unlabeled by apartheid graphs you can sort of, if you find one you can use that to find the other. So this is actually done by, I believe, yeah by Philip Hanlon, who I know as the president current president of Dartmouth College where I went to grad school, but he's also a mathematician and he did stuff with among other areas he worked in, maybe still works in enumerative graph theory and proved. So I got to cite his paper and that was kind of fun. So, I mentioned this, right, the, oh I did not mention yet this result but this was a result in Collins and trance paper, one of their bijections that they found establishes this that the by colored graphs unlabeled by colored graphs, which, again, were counted by Philip Hanlon. I think I have that right. The ordinary generating function for those is equal to one over one minus x times this one, which is the one for split graphs. So this here relates the by colored graphs to the split graphs the numbers of them. And a sketch of the proof is basically, is there a picture on this slide, there's not. That's okay. So given a by colored graph. What we're going to do is remove all isolated green vertices, and then what we're going to then make the remaining green vertices into a click. So what this does is it results in a split graph in its s max partition. Okay, and so what that means is a by colored graph can be decomposed into some isolated green vertices and a an underlying split graph. And that works on the unlabeled level because of the uniqueness of an s max partition. This would not work for labeled, because, well, I, the same argument doesn't work for labeled because of the same issues we talked about before. I did find that actually, I proved this use thing, you know that this result about species that the species of by colored graphs is one over one minus x so this would actually represent the species of linear orders or sequences, which is sort of permutations considered as like a list of the numbers one through and some order times the s split graph species. I was surprised it came out to look exactly like this because again the proof technique use here doesn't actually apply on the level of species the way I proved this was very indirect. Do I say that on this slide. No I don't. So yeah it's an open problem that I hope to either work on or give to, you know, a potential student to work on is to find a bijective proof of this because it looks so simple. What I proved it was using all those other results that I had before, basically.  So it was not a direct proof, but it seems like there should be a bijective proof. Right. So that's, that's interesting. I want to point out that specializing to labeled structures. Also, okay you can see that specializing to unlabeled structures will yield this exact same result specializing to labeled structures yields the same thing with, you know the same relationship between the exponential generating functions which amounts to this that the number of labeled n vertices is the bicolored graphs minus n times the bicolored graphs one size lower the labeled ones and this factor of this factor of n is because of dealing with the exponential generating functions when you. Yeah, so then this ends up being equal to right and again we know I showed you that was what we saw on the previous slide, we know the the coefficients for the, you know the bicolor generating function for labeled structures we know that. For labeled graphs. And so this becomes a summation of just, you know, binomial coefficient times the power of two minus this other binomial coefficient times this other power of two. And this is actually a much simpler formula than what was known before. They are the same, they give you the same numbers. So I guess like this, you know, sort of nested summations thing that they had in, you know, from this paper six years ago, I guess, you know this is what what I've shown essentially is that this, this also gives you the same numbers as that other formula. I mean it's shown, I mean because they both count the same thing, like I didn't actually try to rearrange one of them to become the other one, like algebraically. Yeah, any any questions at this point what are your questions here. Right. So, see specializing. Did I want to say anything else about this. Oh right just that I did this indirectly it would be great to have a bijective proof. I haven't looked that much at trying to find a bijective proof so it could be easy. I don't know. Okay. And finally, this, this is I think the most fun part of this. I was captured by the, the Chang Collins and Frank paper from 2016. And then I managed to prove it using. Well, I'll talk a little bit about how I proved it but the conjecture which I proved is that almost all unlabeled split graphs are balanced in the sense that the limit of, you know, the fraction of them that are unbalanced goes to zero as n goes to infinity. So this issue where you can have two different part ks partitions is rare is what that means as I'm goes to infinity it's vanishingly rare. So, recall, and so the to say a little bit about how this is something that was in this paper the Chang Collins and Frank. They pointed out that if we know that these numbers grow fast enough if we know that the number of split graphs grows fast enough, then what we get is that this sum is dominated by its first term. And then this first term will be way smaller than the next term, right. And so if this the number of unbalanced things is roughly the number of split graphs one size lower. And that's tiny compared to the number of split graphs of that size, then that would prove it. All we would have to do is show that SK grows fast enough and then so that's exactly what I did in my paper.  And I use that connection with the bicolored graph because the bicolored graphs have been counted though with difficulty. Right, a lot of that issue is passing to the unlabeled world. And so the ingredients I'm not really going to talk about the, the proof itself. Wow, I think I'm going to finish this talk early. I think, yeah, is this the last slide. Yeah, this is the last slide. I must have just be talking really fast. So you'll, you'll get to, you'll get an extra 10 minutes to yourself today. So the ingredients of this proof. First of all, like I said, the relationship that I established between bipolar bicolored graphs and split graphs. And then also, once we move it over to the world of bicolored graphs. Then I was able to use existing results on the number of labeled and unlabeled bicolored graphs, including the quote unquote folklore result that the number of unlabeled bicolored graphs is equal to the number of bicolored graphs divided by n factorial the number of labeled ones divided by n factorial. Now what does that mean. I just want to say a few words about this what does that mean that the unlabeled graphs number is equal to the labeled ones divided by n factorial. So that essentially is saying that almost all bicolored graphs are asymmetric, they have no non trivial automorphisms or symmetries that are induced by the symmetric group. And so I could not find this in the literature, when I was writing this paper, and I managed to prove it by sort of mimicking a proof that I found that proves the same result the same result is also very well known for graphs generally that almost all graphs are asymmetric. And so I just sort of tried to use some of the same methods and managed to prove it for this one and I put that in the paper. And in the paper I wrote something along the lines of you know this seems like a fairly fundamental result in graph theory and I'm sure it exists somewhere but I couldn't find it and I asked people. And no one knew. So I'm just putting it in this paper because I need it for this other thing. And this was actually kind of more interesting than anything else in the paper to be honest. But then, yeah, so then when it was going through the review process. The, I think it was the editor that was dealing with my paper. You know asked around as well and then and then they found, they found, they found it in in this reference, but said that it was basically a folklore result in the sense that like everyone sort of knows it and no one's quite sure where it came from originally. So yeah, that was, that was a fun process to try to track down this this formula. So, so yeah that's my talk thank you all for coming. And thank you all on zoom thank you all in person. Yeah, that's been a while since the in person talks you forgot what the procedure is right. Yeah, does anyone have questions. Yeah, the two terms are the same. You have the sum of the sum of the first of the two terms on the slide previous to this one. Oh, let's see. Oh yeah yeah I see what you're saying. I think that I'm trying to remember I think that this one dominates as compared to this one so asymptotically. Yeah, and that's something that is one of the things that goes into proving this in my paper. So asymptotically SN is is equal to be an asymptotically. Yeah, like so that this term sort of is insignificant compared to that. Yeah. Yeah, that's a good question. So yeah this is an exact formula but then asymptotically, you don't need this part at all. Oh yeah for those of you on zoom who maybe weren't I don't know the question was just sort of what happens asymptotically in this line here. And what happens is that this term is insignificant. I will stop.