BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Emina Soljanin (Rutgers University) DTSTART:20210804T160000Z DTEND:20210804T170000Z DTSTAMP:20260416T193616Z UID:CCM2021/1 DESCRIPTION:Title: Codes\, Graphs\, and Hyperplanes in Data Access Service\nby Emina Solj anin (Rutgers University) as part of Carleton Combinatorics Meeting 2021\n \n\nAbstract\nDistributed computing systems strive to maximize the number of concurrent data access requests they can support with fixed resources. Replicating data objects according to their relative popularity and access volume helps achieve this goal. However\, these quantities are often unpr edictable. Erasure-coding has emerged as an efficient and robust form of r edundant storage. In erasure-coded models\, data objects are elements of a finite field\, and each node in the system stores one or more linear comb inations of data objects. This talk asks 1) which data access rates an era sure-coded system can support and 2) which codes can support a specified r egion of access rates. We will address these questions by casting them int o some known and some new combinatorial optimization problems on graphs. W e will explain connections with batch codes. This talk will also describe how\, instead of a combinatorial\, one can adopt a geometric approach to t he problem.\n LOCATION:https://researchseminars.org/talk/CCM2021/1/ END:VEVENT BEGIN:VEVENT SUMMARY:Brett Stevens and Lucas Perin (Carleton University and Federal Uni versity of Santa Catarina) DTSTART:20210805T160000Z DTEND:20210805T170000Z DTSTAMP:20260416T193616Z UID:CCM2021/2 DESCRIPTION:Title: Randomness properties of $\\mathbb{Z}_v$ ElGamal sequences\nby Brett S tevens and Lucas Perin (Carleton University and Federal University of Sant a Catarina) as part of Carleton Combinatorics Meeting 2021\n\n\nAbstract\n In 2020 Boppré et al. investigated the randomness properties of the ElGam al function considered as a permutation $x \\to g^x$ on $\\mathbb{Z}_{p}^ *$. They prove that the graph of this map is equidistributed and demonstr ate experimentally that this map behaves like a random permutation with re spect to the number of cycles and the number of $k$-cycles. These randomne ss properties imply that cryptographic systems based on ElGamal are resist ant to certain attacks and they call for investigation of other randomness properties. We investigate the randomness properties of $\\mathbb{Z}_v$ sequences derived from ElGamal. We prove that the period and number of oc currences of runs and tuples match sequences from random permutations clos ely. We describe extensive experiments which probe these similarities furt her.\n LOCATION:https://researchseminars.org/talk/CCM2021/2/ END:VEVENT BEGIN:VEVENT SUMMARY:Hadi Kharaghani and Sho Suda (University of Lethbridge and Nationa l Defense Academy of Japan) DTSTART:20210804T143000Z DTEND:20210804T153000Z DTSTAMP:20260416T193616Z UID:CCM2021/3 DESCRIPTION:Title: Balanced Generalized Weighing matrices and Association Schemes\nby Had i Kharaghani and Sho Suda (University of Lethbridge and National Defense A cademy of Japan) as part of Carleton Combinatorics Meeting 2021\n\n\nAbstr act\nA symmetric Balanced Incomplete Design\, $\\mathrm{BIBD}(v\, k\, \\la mbda)$\, is signable if it is possible\nto turn its incidence matrix\, by negating some of the entries\, into a matrix with a specific orthogonality property.\n\nSigned symmetric designs possess interesting properties and lead to a variety of association schemes. In addition\, the process is rev ersible\, and signed symmetric designs are constructible from association schemes.\n LOCATION:https://researchseminars.org/talk/CCM2021/3/ END:VEVENT BEGIN:VEVENT SUMMARY:Lucia Moura and Thaís Bardini Idalino (University of Ottawa and F ederal University of Santa Catarina) DTSTART:20210804T171500Z DTEND:20210804T181500Z DTSTAMP:20260416T193616Z UID:CCM2021/4 DESCRIPTION:Title: Cover-free families\, constructions and cryptographical applications\n by Lucia Moura and Thaís Bardini Idalino (University of Ottawa and Federa l University of Santa Catarina) as part of Carleton Combinatorics Meeting 2021\n\n\nAbstract\nCover-free families have been investigated under diffe rent names such as disjunct matrices\, superimposed codes and strongly sel ective families. They are interesting combinatorial objects used in combin atorial group testing as well as various applications in communications.\n \nA $d$-cover-free family $d$-$\\mathrm{CFF}(t\,n)$ is a set system consis ting of n subsets of a $t$-set\, where the union of any $d$ subsets does n ot contain any other. In combinatorial group testing\, a $d$-$\\mathrm{CFF }(t\, n)$ allows for the identification of up to $d$ defective elements in a set of $n$ elements by performing only $t$ tests (typically $t ≪ n$). \n\nThis talk begins with an introduction of cover-free families\, constru ctions and applications. We then focus on applications in cryptography and in particular discuss our work in the use of cover-free families to add f ault-tolerance to classical problems in cryptography. In order to add faul t-tolerance in aggregation of signatures\, we construct infinite sequences of cover-free families with desired properties such as high compression r atio. In the context of malleable digital signatures\, we propose a method that uses cover-free families to locate modifications in signed documents . Works by the authors on this topic can be found in the proceedings of IW OCA2018 and Indocrypt2019\, and in Advances in Mathematics of Communicatio ns (2019) and Theoretical Computer Science (2021).\n LOCATION:https://researchseminars.org/talk/CCM2021/4/ END:VEVENT BEGIN:VEVENT SUMMARY:Jozsef Solymosi\, Kyle Chi Hoi Yip and Ethan White (University of British Columbia) DTSTART:20210805T171500Z DTEND:20210805T184500Z DTSTAMP:20260416T193616Z UID:CCM2021/5 DESCRIPTION:Title: Lacunary polynomials over finite fields and their applications\nby Joz sef Solymosi\, Kyle Chi Hoi Yip and Ethan White (University of British Col umbia) as part of Carleton Combinatorics Meeting 2021\n\n\nAbstract\nIn th e early 70's Laszlo Redei published a book titled "Lacunary Polynomials Ov er Finite Fields". In Redei's notation a polynomial $f(x)$ is lacunary if there is a gap between its largest and second largest exponent. For exampl e $x^5-2x+1$ is a lacunary polynomial. His book is about the properties an d applications of lacunary polynomials. His most important application is bounding the number of directions determined by point sets in an affine G alois plane. We revisit his work giving better bounds on the number of dir ections determined by a Cartesian product. As an immediate corollary we gi ve an upper bound on the clique number of a Paley graph. After the intro ( by Jozsef Solymosi) Kyle Yip will talk about the Van Lint-MacWilliams' con jecture and maximum cliques in Cayley graphs over finite fields and then E than White will talk about the number of distinct roots of a lacunary poly nomial over finite fields.\n LOCATION:https://researchseminars.org/talk/CCM2021/5/ END:VEVENT BEGIN:VEVENT SUMMARY:David Pike and Andrea Burgess (Memorial University of Newfoundland and University of New Brunswick Saint John) DTSTART:20210803T160000Z DTEND:20210803T170000Z DTSTAMP:20260416T193616Z UID:CCM2021/7 DESCRIPTION:Title: The Firebreak problem\nby David Pike and Andrea Burgess (Memorial Univ ersity of Newfoundland and University of New Brunswick Saint John) as part of Carleton Combinatorics Meeting 2021\n\n\nAbstract\nSuppose a network i s represented by a graph $G$. A fire (or some sort of contagion) breaks o ut at a vertex. Firefighters then respond by establishing a single firebr eak consisting of $k$ other vertices of $G$. The fire cannot burn or pass through these $k$ protected vertices\; however\, the fire subsequently spr eads to all vertices it can reach without passing through the firebreak. A natural question arises: how many vertices can be prevented from burning ?\n\nWe discuss how this problem came to our attention\, how the research process evolved\, and how collaborators became engaged. We also delve int o the scientific aspects of the problem\, with emphasis on computational c omplexity. In general\, the associated decision problem is NP-complete\, but it is solvable in polynomial time for certain graph classes. In addit ion\, we will discuss potential applications.\n\nThis is joint work with K athleen Barnetson\, Jessica Enright\, Jared Howell and Brady Ryan.\n LOCATION:https://researchseminars.org/talk/CCM2021/7/ END:VEVENT BEGIN:VEVENT SUMMARY:Karen Meagher\, Mahsa N. Shirazi and Sarobidy Razafimahatratra (Un iversity of Regina) DTSTART:20210803T171500Z DTEND:20210803T184500Z DTSTAMP:20260416T193616Z UID:CCM2021/8 DESCRIPTION:Title: The Ratio Bound for Erdős-Ko-Rado Type Theorems\nby Karen Meagher\, M ahsa N. Shirazi and Sarobidy Razafimahatratra (University of Regina) as pa rt of Carleton Combinatorics Meeting 2021\n\n\nAbstract\nIn this talk Kare n Meagher will introduce the Ratio Bound\, also called Hoffman's Bound or Delsarte's Bound. This is an algebraic bound the size of the maximum cocli que/independent set in a graph. This bound has been used to prove many var iations of the Erdős-Ko-Rado theorem. She will outline some examples of such problems and will show how it can be used effectively for such proble ms.\n\nThen Sarobidy Razafimahatratra will use the Hoffman Bound to prove the Erdős-Ko-Rado\ntheorem for transitive groups. A set of permutations $\\mathcal{F}$ of a finite transitive group $G\\leq\n\\operatorname{Sym}(\ \Omega)$ is intersecting if any two\npermutations in $\\mathcal{F }$ agree on an element of $\\Omega$. The\ntransitive group $G$ is said to have the Erdős-Ko-Rado (EKR)\nproperty if any intersecting set o f $G$ has size at most\n$\\frac{|G|}{|\\Omega|}$. The alternating group $\ \operatorname{Alt}(4)$ acting on the six\n$2$-subsets of $\\{1\,2\,3\,4\\} $ is an example of groups without the EKR\nproperty. This means that trans itive groups do not always have the EKR\nproperty. Given a transitive g roup $G\\leq\\operatorname{Sym}(\\Omega)$\, we are interested in finding t he size and\nstructure of the largest intersecting sets in $G$. In this ta lk\, we will\nuse the Hoffman bound to prove the EKR property for some fam ilies of\ntransitive groups.\n\nFinally\, Mahsa Nasrollahi Shirazi will pr ove an extension of the Erdős-Ko-Rado theorem to set-wise intersecting pe rfect matchings. Two perfect matchings $P$ and $Q$ of a graph on $2k$ vert ices are said to be set-wise $t$-intersecting if there exist edges $P_{1}\ , \\ldots\, P_{t}$ in $P$ and $Q_{1}\, \\ldots\, Q_{t}$ in $Q$ such that t he union of edges $P_{1}\, \\ldots\, P_{t}$ has the same set of vertices a s the union of $Q_{1}\, \\ldots\, Q_{t}$. We define a graph for which find ing a maximum coclique is equivalent to finding a largest family of set-wi se $t$-intersecting perfect matchings for $t=2\,3$. In this approach we us e the ratio bound to find bounds on the size of a maximum coclique in thi s graph.\n LOCATION:https://researchseminars.org/talk/CCM2021/8/ END:VEVENT END:VCALENDAR