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: Mar. 6
Time: 9:30am-11:30am UTC
Speaker: Jinxin Zhou (Beijing Jiaotong University)
Location: Online (Tencent Meeting: 760-114-864)
Title: On the symmetry of token graphs
Abstract: Let G be a graph with n vertices. For 1< k < n, the k-token graph of G is a graph with vertices the k-subsets of V(G) such that two k-subsets are adjacent whenever their symmetric difference is an edge of G. In this talk, we shall introduce some of our recent work on the symmetry of token graphs.
Date: Mar. 13
Time: 9:30am-11:30am UTC
Speaker: Hong Liu (Institute for Basic Science, Korea)
Location: Online (Tencent Meeting: 690-971-088)
Title: Chromatic, homomorphism and blowup thresholds
Abstract: I will talk about the classical chromatic/homomorphism thresholds problems which studies density conditions that guarantee an H-free graph to have bounded complexity. I will survey some recent developments, including an unexpected connection to the theory of VC dimension and also discrete geometry, a novel asymmetric version that we introduce to interpolate the two problems. If time permits, I will discuss two related problems, blowup and VC thresholds.
Date: Mar. 20
Time: 9:30am-11:30am UTC
Speaker: Yuejian Peng (Hunan University)
Location: Online (Tencent Meeting: 948-2462-3387)
Title: Chromatic profile of $C_{2k+1}$-free graphs
Abstract: Erd\H{o}s and Simonovits asked the following question: For an integer $r\geq 2$ and a family of non-bipartite graphs $\mathcal{H}$, what is the tight bound of $\alpha$ such that any $\mathcal{H}$-free $n$-vertex graph with minimum degree at least $\alpha n$ has chromatic number at most $r$? We answer this question for $\mathcal{H}=\{C_{2k+1}\}$, $r\ge 2$ and $k\ge 3r+4$. This is a joint work with Yan Zilong and Yuan Xiaoli.
Date: Apr. 3
Time: 9:30am-11:30am UTC
Speaker: Xujin Chen (Academy of Mathematics and Systems Science)
Location: Online (Tencent Meeting: 948-2462-3387)
Title:Network Topologies Immune to the Strong Braess Paradox
Abstract: The Strong Braess Paradox (SBP) describes a counterintuitive scenario where providing additional roadway options to some self-interested travelers can paradoxically increase their travel times. SBP extends the classical Braess paradox by introducing stricter conditions, requiring that travel latency strictly increases for travelers who gain access to more road options.. In this talk, we discuss the conditions under which SBP does not occur in networks with selfish routing behavior. In particular, we present a complete characterization of network topologies that are immune to a particular case of SBP—the Informational Braess Paradox—thereby resolving an open question posed by Acemoglu et al. (2018).
Date: Apr. 10
Time: 9:30am-11:30am UTC
Speaker: Yongtang Shi (Nankai University)
Location: Online (Tencent Meeting: 948-2462-3387)
Title:Extremal results on the sum of degree powers of graphs
Abstract: Let $G$ be a simple graph with the degree sequence $(d_1, d_2, \ldots,d_n)$. Given a positive integer $p$, denote the \textit{degree power} of $G$ by $e_p(G)=\sum_{i=1}^nd_i^p$. The degree power has extensive applications not only in the study of graph structures but also is closely related to graph spectra. In this talk, we show some extremal results on the sum of degree powers of graphs.
Date: Apr. 24
Time: 9:00am-11:00am UTC
Speaker: Qing Xiang (Southern University of Science and Technology)
Location: Online (Tencent Meeting: 212-489-675)
Title:Linear Representations of Finite Geometries and Associated LDPC Codes
Abstract: The linear representation of a subset of a finite projective space is an incidence structure of affine points and lines determined by the subset. In this talk we use character theory to show that the rank of the incidence matrix has a direct geometric interpretation in terms of certain hyperplanes. We consider the LDPC codes defined by taking the incidence matrix and its transpose as parity-check matrices, and in the former case prove a conjecture of Vandendriessche that the code is generated by words of minimum weight called plane words. In the latter case we compute the minimum weight in some cases and provide a few constructions of codewords.
Date: May 6
Time: 2:00pm-4:00pm UTC
Speaker: Ben Lund (Institute for Basic Science, Korea)
Location: Cybersecurity Innovation Building A-1236（网络安全创新大楼12楼A-1236）, Tencent Meeting: 529-195-633
Title: Embedding distance graphs into subsets of finite vector spaces
Abstract: Iosevich and Rudnev showed that every sufficiently large subset of a finite vector space determines every (algebraically defined) distance. I will talk about how to use their result, in combination with techniques developed in the study of pseudorandom graphs, to embed large classes of nearly spanning graphs of distances in arbitrary subsets of finite vector spaces. I will mention results from two recent papers, one joint with Debsoumya Chakraborti and the other with Chuandong Xu.
Date: May 15
Speaker: Yue Zhou (National University of Defense Technology)
Location: Online (Tencent Meeting: 948-2462-3387)
Title:New maximal additive d-codes on symmetric matrices over finite fields
Abstract: Let $q$ be an odd prime power and let $X(n, q)$ denote the set of symmetric matrices over $\mathbb{F}_q$. A subset $\mathcal{C}$ of $X(n,q)$ is called a \emph{$d$-code} if the rank of $A-B$ is at least $d$ for any distinct $A$ and $B$ in $\mathcal{C}$. It has been proved by Schmidt that if $\mathcal{C}$ is additive, then \[ |\mathcal{C}|\leq \begin{cases} q^{n(n-d+2)/2}, &2\mid n-d;\\\ q^{(n+1)(n-d+1)/2}, &2\nmid n-d. \end{cases} \] Additive $d$-codes meeting the bounds above are called \emph{maximal}. When $d=n$, they are equivalent to commutative finite semifields which have been investigated for around 120 years, and many constructions are known. When d\le n-1, there are very few known constructions of maximal additive $d$-codes in X(n,q) In this talk, we present a new family of maximal additive $(n-2)$-codes for odd $q$ and $n=6,8$ and $10$.
Date: May 29
Speaker: Jian Wang (Taiyuan University of Technology)
Location: Online (Tencent Meeting: 948-2462-3387)
Title:On r-wise t-intersecting uniform families
Abstract: Let $\mathcal{F}$ be a family of $k$-subsets of an $n$-set. For integers $r\geq 2$, $t\geq 1$, $\mathcal{F}$ is called $r$-wise $t$-intersecting if any $r$ of its members have at least $t$ elements in common. The most natural construction of such a family is the full $t$-star, consisting of all $k$-sets containing a fixed $t$-set. In the case $r=2$ the Exact Erd\H{o}s-Ko-Rado Theorem shows that the full $t$-star is largest if $n\geq (t+1)(k-t+1)$. In this talk, we show that for $n\geq (2.5t)^{1/(r-1)}(k-t)+k$, the full $t$-star is largest in case of $r\geq 3$. Examples show that the exponent $\frac{1}{r-1}$ is best possible. This represents a considerable improvement on a recent result of Balogh and Linz. Joint work with Peter Frankl.
Date: Jun. 3
Time: 2:30pm-4:30pm UTC
Speaker: Thang Pham (Vietnam National University Hanoi)
Location: Cybersecurity Innovation Building A-1236（网络安全创新大楼12楼A-1236）
Title:The Erdős and Falconer distance conjectures: connections and applications
Abstract: In this talk, I present recent results on the Erdős and Falconer distance conjectures, highlighting the interplay between these two problems. I also discuss applications to intersection patterns, in particular addressing the prime‐field version of a question posed by Pertti Mattila. These results are based on joint work with Murphy, Petridis, Rudnev, and Steven (2022) and with Yoo (2023).
Date: Jun. 19
Speaker: Achill Schürmann (University of Rostock)
Location: Cybersecurity Innovation Building A-1236（网络安全创新大楼12楼A-1236）
Title:Computing Certificates for Complete Positivity
Abstract: A key problem in computer proofs based on solutions from copositive optimization, is checking whether or not a given quadratic form is completely positive or not. In this talk we describe the first known algorithm for arbitrary rational input. It is based on a suitable adaption of Voronoi's Algorithm and the underlying theory from positive definite to copositive quadratic forms. We observe several similarities with the classical theory, but also some differences, in particular for three and more variables. A key element and currently the main bottleneck in our algorithm is an adapted shortest vector computation, asking for all nonnegative integer vectors that are short with respect to a given copositive quadratic form. (based on joint work with Valentin Dannenberg, Alexander Oertel, Mathieu Dutour Sikirić and Frank Vallentin)