## PIMS- UVic Discrete Math Seminar: Jiaxi Nie

- Date: 11/24/2022
- Time: 15:30

*Shanghai Centre for Mathematical Sciences*

University of Victoria

Odd covers of graphs

Given a finite simple graph $G$, an {\em odd cover of $G$} is a collection of complete bipartite graphs, or bicliques, in which each edge of $G$ appears in an odd number of bicliques and each non-edge of $G$ appears in an even number of bicliques. We denote the minimum cardinality of an odd cover of $G$ by $b_2(G)$ and prove that $b_2(G)$ is bounded below by half of the rank over $\mathbb{F}_2$ of the adjacency matrix of $G$. We show that this lower bound is tight in the case when $G$ is a bipartite graph and almost tight when $G$ is an odd cycle. However, we also present an infinite family of graphs which shows that this lower bound can be arbitrarily far away from $b_2(G)$. Babai and Frankl (1992) proposed the ``odd cover problem," which in our language is equivalent to determining $b_2(K_n)$. Radhakrishnan, Sen, and Vishwanathan (2000) determined $b_2(K_n)$ for an infinite but density zero subset of positive integers $n$. In this paper, we determine $b_2(K_n)$ for a density $3/8$ subset of the positive integers.

This is joint work with Calum Buchanan, Alexander Clifton, Jason O'Neil, Puck Rombach, and Mei Yin.

**Time**: 3.30PM - 4.20PM Pacific

**Location**: University of Victoria, MAC D116

**Registration**: Free

More details listedÂ here.