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 innite 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. |