当前位置: 首页/ 学术报告

Odd covers of graphs

发布时间:2022-11-28 浏览量:86

时   间:  2022-11-28 15:00 — 16:00

地   点:  腾讯会议 APP()
报告人:  聂家熹
单   位:  上海数学中心
邀请人:  汪彦
备   注:  #腾讯会议:259-259-068
报告摘要:  

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.