CanaDAM 2021
En ligne, 25 - 28 mai 2021

Contributed Talks II

MÁRIA MACEKOVÁ, P.J. Šafárik University in Košice, Slovakia
Scarce and frequent cycles in polyhedral graphs  [PDF]

Let $\mathcal{G}$ be a class of graphs. Given a positive integer $n \geq 3$, an $n$-vertex graph $H$ is called frequent in a graph family $\mathcal{G}$ if there exists a real function $f$ such that each graph of $\mathcal{G}$ with at least $f(n)$ vertices contains a subgraph isomorphic to $H$. If $H$ is not frequent in $\mathcal{G}$, then it is called scarce in $\mathcal{G}$; this means that there exists an infinite sequence $\{G_i\}_{i =1}^{\infty}$ of graphs from $\mathcal{G}$ such that no $G_i$ contains an isomorphic copy of $H$.

In the talk we present some results on the frequent and scarce cycles in the family of polyhedral graphs and its particular subfamilies.

SEAN MCGUINNESS, Thompson Rivers University
Rota's Basis Conjecture for Binary Matroids: the case for constructing bases one-at-a-time.  [PDF]

Rota's basis conjecture (RBC) states that given a collection $\mathbb{B}$ of $n$ bases in a matroid $M$ of rank $n$, one can always find $n$ disjoint rainbow bases with respect to $\mathbb{B}$. In this talk, we examine this conjecture in the case of binary matroids, in particular binary matroids having $n+k$ elements where $k$ is small. We introduce a heuristic for constructing $n$ disjoint rainbow bases, one-at-a-time which we conjecture will work for all binary matroids. A key ingredient in the method is the requirement that at each step, the rainbow basis constructed satisfy certain inequalities.

ANDRIY PRYMAK, University of Manitoba
Spherical coverings and X-raying convex bodies of constant width  [PDF]

We give constructions of certain spherical coverings in small dimensions. K. Bezdek and Gy. Kiss showed that existence of origin-symmetric coverings of unit sphere in $\mathbb{E}^n$ by at most $2^n$ congruent spherical caps with radius not exceeding $\arccos\sqrt{\frac{n-1}{2n}}$ implies the $X$-ray conjecture and the illumination conjecture for convex bodies of constant width in $\mathbb{E}^n$, and constructed such coverings for $4\le n\le 6$. We give such constructions with fewer than $2^n$ caps for dimensions $5\le n\le 15$. In combination with the known result for higher dimensions due to O. Schramm, this completely settles the above mentioned conjectures for convex bodies of constant width in all dimensions. We also show how to calculate the covering radius of a given discrete point set on the sphere efficiently on a computer.

This is a joint work with A. Bondarenko and D. Radchenko.

VENKITESH S., Indian Institute of Technology Bombay
Covering Symmetric Subsets of the Cube by Affine Hyperplanes  [PDF]

Alon and F\"uredi (1993) proved that any family of hyperplanes covering the Boolean hypercube \(\{0,1\}^n\), except the origin, must contain at least \(n\) hyperplanes. We will obtain two extensions of this result to hyperplane covers of symmetric subsets of the hypercube (subsets that are closed under permutations of coordinates).

To prove our results, we introduce \emph{hyperplane closures}, a family of closure operators defined using hyperplane covers, for subsets of the hypercube. We will give a combinatorial characterization of the hyperplane closures of symmetric subsets, which enables us to compute these efficiently, via a greedy algorithm.

This characterization may also be of independent interest; indeed, we consider two other applications. Firstly, we obtain an easy proof of a lemma by Alon et al. (1988). Secondly, we characterize the symmetric hitting sets for polynomial functions with degree at most \(d\), for all \(d\), and characterize the certifying degrees of all symmetric subsets.

ZACH WALSH, Louisiana State University
Totally D-Modular Matroids  [PDF]

For a positive integer D, an integer matrix is totally D-modular if the determinant of each square submatrix has absolute value at most D. Tutte proved that a matroid is representable over every field if and only if it has a representation as a totally 1-modular matrix. When D is at least two, what can be said about the class of matroids with a representation as a totally D-modular matrix?