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:20260404T094149Z UID:CCM2021/1 DESCRIPTION:Title: Codes\, Graphs\, and Hyperplanes in Data Access Service\nby Emi na Soljanin (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 reso urces. Replicating data objects according to their relative popularity and access volume helps achieve this goal. However\, these quantities are oft en unpredictable. Erasure-coding has emerged as an efficient and robust fo rm of redundant storage. In erasure-coded models\, data objects are elemen ts of a finite field\, and each node in the system stores one or more line ar combinations of data objects. This talk asks 1) which data access rates an erasure-coded system can support and 2) which codes can support a spec ified region of access rates. We will address these questions by casting t hem into some known and some new combinatorial optimization problems on gr aphs. We will explain connections with batch codes. This talk will also de scribe how\, instead of a combinatorial\, one can adopt a geometric approa ch to the problem.\n LOCATION:https://stable.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:20260404T094149Z UID:CCM2021/2 DESCRIPTION:Title: Randomness properties of $\\mathbb{Z}_v$ ElGamal sequences\nby Brett Stevens and Lucas Perin (Carleton University and Federal University of Santa Catarina) as part of Carleton Combinatorics Meeting 2021\n\n\nAbs tract\nIn 2020 Boppré et al. investigated the randomness properties of th e ElGamal function considered as a permutation $x \\to g^x$ on $\\mathbb{ Z}_{p}^*$. They prove that the graph of this map is equidistributed and d emonstrate experimentally that this map behaves like a random permutation with respect to the number of cycles and the number of $k$-cycles. These r andomness properties imply that cryptographic systems based on ElGamal are resistant to certain attacks and they call for investigation of other ran domness properties. We investigate the randomness properties of $\\mathbb {Z}_v$ sequences derived from ElGamal. We prove that the period and numbe r of occurrences of runs and tuples match sequences from random permutatio ns closely. We describe extensive experiments which probe these similariti es further.\n LOCATION:https://stable.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:20260404T094149Z UID:CCM2021/3 DESCRIPTION:Title: Balanced Generalized Weighing matrices and Association Schemes\ nby Hadi Kharaghani and Sho Suda (University of Lethbridge and National De fense Academy of Japan) as part of Carleton Combinatorics Meeting 2021\n\n \nAbstract\nA symmetric Balanced Incomplete Design\, $\\mathrm{BIBD}(v\, k \, \\lambda)$\, is signable if it is possible\nto turn its incidence matri x\, by negating some of the entries\, into a matrix with a specific orthog onality property.\n\nSigned symmetric designs possess interesting properti es and lead to a variety of association schemes. In addition\, the process is reversible\, and signed symmetric designs are constructible from assoc iation schemes.\n LOCATION:https://stable.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:20260404T094149Z UID:CCM2021/4 DESCRIPTION:Title: Cover-free families\, constructions and cryptographical application s\nby Lucia Moura and Thaís Bardini Idalino (University of Ottawa and Federal University of Santa Catarina) as part of Carleton Combinatorics M eeting 2021\n\n\nAbstract\nCover-free families have been investigated unde r different names such as disjunct matrices\, superimposed codes and stron gly selective families. They are interesting combinatorial objects used in combinatorial group testing as well as various applications in communicat ions.\n\nA $d$-cover-free family $d$-$\\mathrm{CFF}(t\,n)$ is a set system consisting of n subsets of a $t$-set\, where the union of any $d$ subsets does not contain any other. In combinatorial group testing\, a $d$-$\\mat hrm{CFF}(t\, n)$ allows for the identification of up to $d$ defective elem ents 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\, constructions and applications. We then focus on applications in cryptogr aphy and in particular discuss our work in the use of cover-free families to add fault-tolerance to classical problems in cryptography. In order to add fault-tolerance in aggregation of signatures\, we construct infinite s equences of cover-free families with desired properties such as high compr ession ratio. In the context of malleable digital signatures\, we propose a method that uses cover-free families to locate modifications in signed d ocuments. Works by the authors on this topic can be found in the proceedin gs of IWOCA2018 and Indocrypt2019\, and in Advances in Mathematics of Comm unications (2019) and Theoretical Computer Science (2021).\n LOCATION:https://stable.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:20260404T094149Z UID:CCM2021/5 DESCRIPTION:Title: Lacunary polynomials over finite fields and their applications\ nby Jozsef Solymosi\, Kyle Chi Hoi Yip and Ethan White (University of Brit ish Columbia) as part of Carleton Combinatorics Meeting 2021\n\n\nAbstract \nIn the early 70's Laszlo Redei published a book titled "Lacunary Polynom ials Over Finite Fields". In Redei's notation a polynomial $f(x)$ is lacun ary if there is a gap between its largest and second largest exponent. For example $x^5-2x+1$ is a lacunary polynomial. His book is about the proper ties and applications of lacunary polynomials. His most important applicat ion is bounding the number of directions determined by point sets in an a ffine Galois plane. We revisit his work giving better bounds on the number of directions determined by a Cartesian product. As an immediate corollar y we give 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-MacWillia ms' conjecture and maximum cliques in Cayley graphs over finite fields and then Ethan White will talk about the number of distinct roots of a lacuna ry polynomial over finite fields.\n LOCATION:https://stable.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:20260404T094149Z UID:CCM2021/7 DESCRIPTION:Title: The Firebreak problem\nby David Pike and Andrea Burgess (Memori al University of Newfoundland and University of New Brunswick Saint John) as part of Carleton Combinatorics Meeting 2021\n\n\nAbstract\nSuppose a ne twork is represented by a graph $G$. A fire (or some sort of contagion) b reaks out at a vertex. Firefighters then respond by establishing a single firebreak consisting of $k$ other vertices of $G$. The fire cannot burn o r pass through these $k$ protected vertices\; however\, the fire subsequen tly spreads to all vertices it can reach without passing through the fireb reak. A natural question arises: how many vertices can be prevented from burning?\n\nWe discuss how this problem came to our attention\, how the re search process evolved\, and how collaborators became engaged. We also de lve into the scientific aspects of the problem\, with emphasis on computat ional complexity. In general\, the associated decision problem is NP-comp lete\, but it is solvable in polynomial time for certain graph classes. I n addition\, we will discuss potential applications.\n\nThis is joint work with Kathleen Barnetson\, Jessica Enright\, Jared Howell and Brady Ryan.\ n LOCATION:https://stable.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:20260404T094149Z UID:CCM2021/8 DESCRIPTION:Title: The Ratio Bound for Erdős-Ko-Rado Type Theorems\nby Karen Meag her\, Mahsa N. Shirazi and Sarobidy Razafimahatratra (University of Regina ) as part of Carleton Combinatorics Meeting 2021\n\n\nAbstract\nIn this ta lk Karen Meagher will introduce the Ratio Bound\, also called Hoffman's Bo und or Delsarte's Bound. This is an algebraic bound the size of the maximu m coclique/independent set in a graph. This bound has been used to prove m any variations of the Erdős-Ko-Rado theorem. She will outline some examp les of such problems and will show how it can be used effectively for such problems.\n\nThen Sarobidy Razafimahatratra will use the Hoffman Bound to prove the Erdős-Ko-Rado\ntheorem for transitive groups. A set of permut ations $\\mathcal{F}$ of a finite transitive group $G\\leq\n\\operatorname {Sym}(\\Omega)$ is intersecting if any two\npermutations in $\\ma thcal{F}$ agree on an element of $\\Omega$. The\ntransitive group $G$ is s aid to have the Erdős-Ko-Rado (EKR)\nproperty if any intersectin g set of $G$ has size at most\n$\\frac{|G|}{|\\Omega|}$. The alternating g roup $\\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 tha t transitive groups do not always have the EKR\nproperty. Given a trans itive group $G\\leq\\operatorname{Sym}(\\Omega)$\, we are interested in fi nding the size and\nstructure of the largest intersecting sets in $G$. In this talk\, we will\nuse the Hoffman bound to prove the EKR property for s ome families of\ntransitive groups.\n\nFinally\, Mahsa Nasrollahi Shirazi will prove an extension of the Erdős-Ko-Rado theorem to set-wise intersec ting perfect matchings. Two perfect matchings $P$ and $Q$ of a graph on $2 k$ vertices 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 the union of edges $P_{1}\, \\ldots\, P_{t}$ has the same set of ver tices as the union of $Q_{1}\, \\ldots\, Q_{t}$. We define a graph for whi ch finding a maximum coclique is equivalent to finding a largest family of set-wise $t$-intersecting perfect matchings for $t=2\,3$. In this approac h we use the ratio bound to find bounds on the size of a maximum coclique in this graph.\n LOCATION:https://stable.researchseminars.org/talk/CCM2021/8/ END:VEVENT END:VCALENDAR