C&O Discrete Mathematics Seminar 2023-24

We may not have regular talks yet, but we are trying to revive our seminar (under a new name!). DM talks under a different umbrella are included.

• SERIES	C&O Discrete Math Seminar
  TITLE	Graph Embeddings  and Map Colorings
  SPEAKER	Jason Gao (Carleton University)
  DATE	Friday, January 26, 2024
  TIME	13:30 (coffee at 13:00)
  ROOM	HP 4351, Carleton University
  ABSTRACT	The famous Map Color Theorem says that the chromatic number of every surface of Euler characteristic c<0 is equal to  $\lfloor \frac{1}{2}(7+\sqrt{49-24c})\rfloor$. This was proved  in 1969 by  Ringel and Youngs who showed that K_n can be embedded on surfaces of  Euler characteristic c such that  $n= \lfloor \frac{1}{2}(7+\sqrt{49-24c})\rfloor$. This leads to the study about  the genus distribution of a graph G, that is,  the numbers of embeddings of G on surfaces. This talk will go through some recent results about genus distributions of  bouquets and cubic graphs, including confirmation of Stahl's conjecture about the mode and median of the genus distribution of bouquets. If time permits, we will also talk about the chromatic number of a random map on a given surface.

  
  

• SERIES	Carleton Finite Fields Seminar
  TITLE	On constructing bent functions from cyclotomic mappings
  SPEAKER	Xi Xie (Carleton University)
  DATE	Friday, January 19, 2024
  TIME	13:30 (coffee at 13:00)
  ROOM	HP 4351, Carleton University
  ABSTRACT	This talk focuses on a new method of constructing Boolean bent functions from cyclotomic mappings. Three generic constructions are obtained by considering different branch functions such as Dillon functions, Niho functions and Kasami functions over multiplicative cosets and additive cosets respectively. As a result, several new explicit innite families of bent functions and their duals are derived. We demonstrate that some previous constructions are special cases of our simple constructions. In addition, by studying their polynomial forms, we observe that the last construction provides some examples which are EA-inequivalent to five classes of monomials, Dillon type and Niho type polynomials.

  
  

• SERIES	CRM Distinguished Colloquium
  TITLE	A Compendium of Difference Families
  SPEAKER	Douglas Stinson, University of Waterloo and Carleton University
  DATE	Wednesday, November 22, 2023
  TIME	16:00 (tea time 15:30 in the department lounge)
  ROOM	TBD
  ABSTRACT	We discuss a variety of external difference families (EDFs), including strong and circular variants. The study of these combinatorial objects is motivated by applications to robust and nonmalleable threshold schemes. However, they are also of intrinsic interest, apart from applications. In this talk, we mainly discuss mathematical aspects, especially existence and nonexistence, of various types of EDFs. Two of the interesting construction techniques involve using graceful labellings to construct circular EDFs, and using classical results on cyclotomic numbers to obtain close approximations to (nonexistent) strong circular EDFs.

  
  

• SERIES	C&O Discrete Math Seminar
  TITLE	Graph Product Structure Theorem
  SPEAKER	Vida Dujmovic, University of Ottawa
  DATE	Friday, November 10, 2023
  TIME	15:00
  ROOM	STM 364
  ABSTRACT	This talk will introduce the product structure theorem. It states that every planar graph is a subgraph of the strong product of a path and a bounded treewidth graph. The theorem has led to resolutions of several long-standing open problems on planar graphs. Time permitting, I will also present some of these applications of the product structure theorem. The theorem can also be generalized from planar graphs to bounded genus graphs, apex-minor-free graphs, bounded-degree graphs from minor closed families, and k-planar graphs.

• SERIES	Carleton Finite Fields Seminar and C&O Discrete Math Seminar
  TITLE	Trade-Based LDPC Codes and QC-LDPC Codes
  SPEAKER	Farzane Amirzade (Carleton University)
  DATE	Friday, October 6, 2023
  TIME	13:15
  ROOM	HP 4351, Carleton University
  ABSTRACT	LDPC (Low-Density Parity-Check) codes are one of the most important families of codes. They are used in practice in 5G wireless communications. There are different approaches to constructing LDPC codes such as quasi-cyclic LDPC (QC-LDPC) codes, algebraic-based LDPC codes as well as LDPC codes based on combinatorial designs. In this talk we provide a novel approach to construct the parity-check matrix of an LDPC code based on trades obtained from block designs. We call these trade-based LDPC codes. Using properties of cyclical trades, we consider graphical structures of their Tanner graph such as short cycles, girth, as well as trapping sets which are key factors that influence the code performance and determine the minimum distance of the code. We establish a relation between our trade-based LDPC codes and QC– LDPC codes. QC-LDPC codes are built from a, so-called, exponent matrix. We define an exponent matrix for the parity-check matrix of a trade-based LDPC code that is obtained from block designs developed by base blocks. We comment on results related to the minimum distance of these codes. We conclude showing experiments comparing the performance of our trade-based LDPC codes with other codes like protograph-based Raptor-like LDPC codes.

  
  

• SERIES	Graduate Student Colloquium
  TITLE	The spouse loving variant of the Oberwolfach Problem
  SPEAKER	Marusa Lekse, University of Ljubljana
  DATE	Friday, September 15, 2023
  TIME	4:00pm
  ROOM	STM 464
  ABSTRACT	At the conference in Oberwolfach there was a tradition for participants to have dinner together each evening of the conference. In 1967 Gerhard Ringel asked the following question: given a room with t round tables of sizes ℓ1, . . . , ℓt, is it possible for people to sit around those tables in such a way that over an appropriate amount of meals, every person sits next to every other person exactly once? Or equivalently, given integers ℓ1, . . . , ℓt ≥ 3 , with n = ℓ1+. . .+ℓt being an odd integer, does there exist a decomposition of the complete graph Kn into copies of a graph F, where F is a disjoint union of t cycles of lengths ℓ1, . . . , ℓt? A lot of results have been obtained on this problem and its many variants, but in general it still remains unsolved. In this talk, we will focus on one of the recently studied variants - the spouse loving variant, in which the participants at the conference are couples, and every person wants to sit next to every other person exactly once, except for their spouse, next to whom they want to sit exactly twice. OP+(ℓ1, . . . , ℓt) has been previously solved for the case when all ℓi are even, the case when ℓ1 = . . . = ℓt, as well as the two-table case when one table has size 3, and we will look at some of these constructions. We will then present a new result on the two-table spouse-loving variant.