Combinatorics, Information Theory & Related Topics Seminar @ Xidian University
The seminar mainly hosts speakers in the fields of combinatorics, information theory and related topics. Topics of interest include, but are not limited to, additive combinatorics, algebraic combinatorics, coding theory, combinatorial designs, cryptography, discrete geometry, extremal combinatorics, finite geometry, graph theory and incidence geometry.
Organizer: Tao Zhang
Time: Thursday, 9:30am-11:30am UTC (One hour for talk and one hour for discussion)
Location: Online / Cybersecurity Innovation Building A-1236（网络安全创新大楼12楼A-1236）
Date: Oct. 23
Speaker: Huajun Zhang (Shaoxing University)
Location: Online (Tencent Meeting: 507-2372-1447)
Title: The Erdos-Ko-Rado Theorem in l_2 Norm
Abstract: The codegree squared sum ${\rm co}_2(\mathcal F)$ of a hypergraph (family) $\mathcal F \subseteq \binom{[n]} k$ is defined to be the sum of codegrees squared $d(E)^2$ over all $E\in \binom{[n]}{k-1}$, where $$d(E)=|\{F\in \mathcal F: E\subseteq F\}|.$$ Given a family of $k$-uniform hypergraphs $\mathcal H$, Balogh, Clemen and Lidick\'y recently introduced the problem to determine the maximum codegree squared sum ${\rm co}_2(\mathcal F)$ over all $\mathcal H$-free $\mathcal F$. In this talk, we will show that: Let $t,k,n$ be positive integers such that $n\geq(t+1)(k-t+1)$. If $\mathcal F$ is a $t$-intersecting family of $\binom{[n]}{k}$, then \[{\rm co}_2(\mathcal F)\le {\binom{n-t}{k-t}}(1+(n-k+1)(k-t)).\] Moreover, for $n> (t+1)(k-t+1)$, equality holds if and only if $\mathcal{F}=\{F\in {\binom{[n]}{k}}: T\subset F\}$ for some $t$-subset $T$ of $[n]$. This confirms a conjecture of Brooks and Linz. This is a joint work with Biao Wu.
Date: Nov. 6
Speaker: Zichao Dong (Institute for Basic Science)
Location: Online (Tencent Meeting: 507-2372-1447)
Title: Set families: restricted distances via restricted intersections
Abstract: Denote by $f_D(n)$ the maximum size of a set family $\mathcal{F}$ on $[n] \stackrel{\mbox{\normalfont\tiny def}}{=} \{1, \dots, n\}$ with distance set $D$. That is, $|A \bigtriangleup B| \in D$ holds for every pair of distinct sets $A, B \in \mathcal{F}$. Kleitman's celebrated discrete isodiametric inequality states that $f_D(n)$ is maximized at Hamming balls of radius $d/2$ when $D = \{1, \dots, d\}$. We study the generalization where $D$ is a set of arithmetic progression and determine $f_D(n)$ asymptotically for all homogeneous $D$. In the special case when $D$ is an interval, our result confirms a conjecture of Huang, Klurman, and Pohoata. Moreover, we demonstrate a dichotomy in the growth of $f_D(n)$, showing linear growth in $n$ when $D$ is a non-homogeneous arithmetic progression. Different from previous combinatorial and spectral approaches, we deduce our results by converting the restricted distance problems to restricted intersection problems. Our proof ideas can be adapted to prove upper bounds on $t$-distance sets in Hamming cubes (also known as binary $t$-codes), which has been extensively studied by algebraic combinatorialists community, improving previous bounds from polynomial methods and optimization approaches.
Date: Nov. 13
Time: 4:00pm--5:00pm
Speaker: Jun Gao (University of Warwick)
Location: Online (Tencent Meeting: 701-335-580)
Title: New upper bound for lattice covering by spheres
Abstract: We show that there exists a lattice covering of $\mathbb{R}^n$ by Euclidean spheres of equal radius with density $O\big(n \ln^{\beta} n \big)$ as $n\to\infty$, where \[ \beta:=\frac{1}{2}\log_2\left(\frac{8\pi\mathrm{e}}{3\sqrt3}\right)=1.85837... \] This improves upon the previously best known upper bound by Rogers from 1959 of $O\big(n \ln^{\alpha} n \big)$, where $\alpha:= \frac{1}{2} \log_{2}(2\pi \mathrm{e})=2.0471...$. This is a joint work with Xizhi Liu, Oleg Pikhurko and Shumin Sun
Date: Nov. 20
Speaker: Yifan Jing (Ohio State University)
Location: Online (Tencent Meeting: 507-2372-1447)
Title: Measure doubling for small sets in compact Lie groups
Abstract: A central problem in additive combinatorics is to understand how the size of a sumset (or product set) compares to the size of the original set, and to describe the underlying structure when this "doubling" is small. In this talk, I will survey some classical results in the area and discuss recent developments in the setting of compact Lie groups, based on joint work with Chieu-Minh Tran and Simon Machado.
Date: Nov. 27
Speaker: TBA
Location: TBA
Title: TBA
Abstract: TBA
Date: Dec. 4
Speaker: TBA
Location: TBA
Title: TBA
Abstract: TBA
Date: Dec. 11
Speaker: TBA
Location: TBA
Title: TBA
Abstract: TBA
Date: Dec. 25
Speaker: TBA
Location: TBA
Title: TBA
Abstract: TBA