Schedule for: 25w5352 - Finite Geometry and Extremal Combinatorics

A set dinner is served daily between 5:30pm and 7:30pm in the Xianghu Lake National Tourist Resort.

Breakfast is served daily between 7 and 9am in the Xianghu Lake National Tourist Resort

We study the following conjecture: for any finite family of graphs $\mathcal{H}$ with $\textrm{ex}(n, \mathcal{H}) = \Theta(n^s)$ and any rational $1 \leq r \leq s$, there exists a graph $F_r$ such that $\textrm{ex}(n, \mathcal{H} \cup F_r) = \Theta(n^r)$. In particular, when $\mathcal{H}$ consists of the single graph $C_4$, we show that this conjecture follows from another conjecture of Bukh and Conlon about the extremal number of powers of rooted trees. We also discuss some applications of our results. Joint work with Jeck Lim.

Let $S$ be a subset of the Hamming cube $\{0,1\}^n$ that has diameter $d$, and is maximal with respect to this property. What are the possible sizes of $S$? We show that these are very constrained. For example, we prove that there exists a function $f(d)$ such that each such $S$ has either at least $n$ or at most $f(d)$ elements. We show near-optimal bounds on $f$ and its generalization to larger alphabets. We also discuss the lower bounds on $|S|$.

Lunch is served daily between 11:30am and 1:30pm in the Xianghu Lake National Tourist Resort

In 1976, Burr, Erdős and Lovász initiated a systematic study of various properties of Ramsey graphs. A graph $G$ is said to be $r$-Ramsey if every $r$-colouring of the edges of $G$ contains a monochromatic copy of $K_k$. Moreover, it is called minimal when no proper subgraph of $G$ has this property. While historically a lot of attention has been devoted to the smallest possible order of a $2$-Ramsey graph, one could also consider for example the smallest chromatic number, maximum, or minimum degree of a minimal $r$-Ramsey graph. While Burr, Erdős and Lovász already determined the smallest possible minimum degree of minimal $2$-Ramsey graphs, the behavior of this quantity is much less understood for more colours. In particular, it is not clear what the correct asymptotic behaviour (in both $k$ and $r$) is. We will present some progress towards this problem, based on joint work Jacques Verstraete.

In 2014, Krivelevich, Lee and Sudakov proved that given a (large) graph of minimum degree $n/2$, if we independently keep each edge with probability $p\ge C\log n/n$, then with high probability the resulting subgraph still has a Hamiltonian cycle. There has been a recent trend on the study of random subgraph of (dense) graphs and hypergraphs, inspired by the development of the spread technique. In this talk we will briefly survey these results and introduce our result on perfect matchings in the random subgraph of dense uniform hypergraphs.

Finding good lower bounds for the problem studied here https://arxiv.org/abs/2009.00130

Finite generalized polygons correspond to rank $2$ spherical buildings and are important geometric structures. A generalized $n$-gon is a point-line incidence structure whose incidence graph is a bipartite graph of diameter $n$ and girth $2n$. Their collinearity graphs form important classes of distance regular graphs, from which Feit and Higman showed that $n\in\{2,3,4,6,8,12\}$. I would like to seek a proper definition of a hypergraph version of generalized polygons, and consider its applications in extremal combinatorics.

Godsil-McKay (GM) switching is an operation on a graph that does not change the spectrum of the graph. GM switching has been studied to obtain cospectral but non-isomorphic graphs having a highly symmetric structure, e.g., strongly regularity. If we apply GM switching to a graph, the complement of the resulting graph is also obtained by applying GM switching with the same switching set to the complement of the original graph. In particular, we can interpret GM switching as an operation of exchanging some edges between a graph and its complement. Hence, it is natural to extend GM switching for the pair of a graph and its complement to switching for a decomposition of the complete graph by some good graphs. In this talk, we pose some fundamental problems on switching for association schemes to obtain non-isomorphic association schemes as a generalization of the previous studies for strongly regular graphs. Furthermore, we explain a few results on switching for association schemes shown by the speaker.

Breakfast is served daily between 7 and 9am in the Xianghu Lake National Tourist Resort

In this survey type talk we describe a recently-developed technique for bounding the number (and controlling the typical structure) of finite objects with forbidden substructures. This technique exploits a subtle clustering phenomenon exhibited by the independent sets of uniform hypergraphs whose edges are sufficiently evenly distributed; more precisely, it provides a relatively small family of ‘containers’ for the independent sets, each of which contains few edges. We attempt to convey a general high-level overview of the method, focusing on a small number of illustrative applications in areas such as extremal graph theory, Ramsey theory, additive combinatorics, and discrete geometry, and avoiding technical details as much as possible.

We prove a version of sparsification result for multipartite graphs which finds, within any multipartite graph with positive pairwise densities, a bounded order subgraph with sufficiently many parts and almost the same pairwise densities. As an application, we settle a multicolor Turan problem first suggested by Bollobas. This is joint work with Ander Lamaison.

In this talk, we will present the recent graph-theoretic method of constructing strong blocking sets and their generalizations in finite geometry. A strong blocking set is a set of points that meets every hyperplane in a spanning set. We will show a connection between these and affine blocking sets for codimension 2 subspaces, and obtain an asymptotically optimal explicit construction using constant degree expanders. Moreover, we will describe how these finite geometric objects are connected to minimal codes and trifferent codes.

In 1982, Cameron and Liebler introduced specific line classes in PG$(3,q)$ when investigating the orbits of the subgroups of the collineation group of PG$(3,q)$. They found that these Cameron-Liebler sets can be defined in many equivalent ways; some combinatorial, geometrical or algebraic in nature. A Cameron-Liebler line set $\mathcal{L}$ in PG$(3,q)$ is a set of lines, such that every line spread in PG$(3,q)$ has the same number of lines in common with $\mathcal{L}$. The examination of these Cameron-Liebler line sets in PG$(3,q)$ started the motivation for defining and investigating Cameron-Liebler sets in other contexts, including the context of finite classical polar spaces \cite{CLpol, CLpolik}. In this talk I will focus on Cameron-Liebler sets in these finite classical polar spaces, in particular in the hyperbolic quadric $Q^+(5,q)$. I will present some non-trivial examples of Cameron-Liebler sets of generators in $Q^+(5,q)$, which were recently found by using the Klein correspondence. This project is joint work with J. Mannaert and L. Storme \cite{CLpolQ}.

We will discuss the problem of constructing dense (optimally) pseudorandom clique-free graphs. In the first half of the talk we will explain constructions by Alon and Krivelevich as well as Bishnoi, Ihringer and Pepe using Euclidean geometry. In the second half we will discuss a selection of approaches for improving upon the existing constructions which do not seem work. Our hope is not only that this will prevent others from trying hopelessly, but also that it will give inspiration for how finite geometry and highly regular graphs could be used in other extremal problems.

Given a set $X$ and $\mathcal{S}$ which consists of some special subsets of $X$, a t-packing is a sub-(multi)set $\mathcal{C}$ of $\mathcal{S}$ such that each element $a\in X$ belongs to at most $t$ elements in $\mathcal{C}$. The classical $t$-packings with $t=1$ are: (1). sphere packings in Euclidean spaces: $X=\mathbb{R}^n$, $\mathcal{S}=\{B(a,1): a\in \mathbb{R}^n\}$ where $B(a,1):=\{x: \|x-a\|_2\leq 1\}$; (2). error-correcting codes with Hamming distance: $X=\mathbb{F}_q^n$, $\mathcal{S}=\{B(a,r): a\in \mathbb{F}_q^n\}$ where $B(a,r):=\{x: \|x-a\|_H\leq r\}$. For both of them, the linear programming method provides very strong upper bounds on their densities/sizes. However, for $t>1$, it seems that there is no direct way to use it. $$ $$ How to obtain upper bounds for $t$-packings in Hamming, Johnson, Grassmannian schemes which are better than those obtained by counting/induction? $$ $$ Another important case is defined by $X=\mathrm{PG}(n,q)$ and $\mathcal{S}$ consisting of $k$-subspaces in $\mathrm{PG}(n,q)$. Now a $1$-packing is equivalent to a $k$-partial spread, and the existence of large $t$-packings become more interesting. In this part, I will discuss several open problems concerning the existence of long fractional MDS codes and large-dimensional dual arcs. Probabilistic methods and other approaches in hypergraph theory appear to be particularly promising in addressing these challenges.

We prove that any two longest cycles (or paths) in a k-connected graph must intersect in at least c k^{2/3} vertices for some absolute constant c>0. This improves earlier bounds established by Chen–Faudree–Gould and Groenland–Longbrake–Steiner–Turcotte–Yepremyan. We also prove that the size of the intersection of any two longest cycles in every vertex-transitive graph on n vertices tends to infinity as n tends to infinity. This partially answers a question of Babai. Joint work with Ziyuan Zhao .

Let H be a graph. The function ex(n,H) is the maximum number of edges that a graph with n vertices can have, which contains no subgraph isomorphic to H. If H is not bipartite then the asymptotic behaviour of ex(n,H) is known, but if H is bipartite then in general this is not the case. It is not known for H=K_4,4. This talk will focus on the case that H is a complete bipartite graph. I will review the previous constructions from a geometrical point of view and in particular study the norm graph. Geometrical arguments allow one to prove that the norm graph which contains no K_4,7 contains no K_5,5. There are many open problems and geometrical arguements have yet to be exploited for other bipartite graphs.

Coming soon

According to a widely held belief, nothing unexpected can occur with projective embeddings of Lie geometries, except possibly when they are defined over a very small field. In particular, it is supposed that all of them admit the absolutely universal embedding (from which all other projective embeddings of the given geometry can be obtained as projections) and this absolute embedding is the one hosted by the appropriate Weyl module. In my talk I will present a few results which disprove this belief. $$ $$ Theorem 1. The long-root geometry $A_{n,\{1,n\}}(F)$ for $\mathrm{SL}(n+1,F)$ (where the points are the point-hyperplane flags of $\mathrm{PG}(n,F)$) admits the absolutely universal embedding only if the field $F$ admits no non-trivial automorphism. $$ $$ Theorem 2. The adjoint embedding of $A_{n,\{1,n\}}(F)$ in (the projective geometry of the underlying vector space of) the lie Algebra $\mathrm{sl}(n+1,F)$ is relatively universal, namely it is not a projection from a larger embedding, if and only if $F$ admits no non-trivial derivation (in other words, $F$ is either perfect of positive characteristic or an algebraic number field). $$ $$ When $\mathrm{char}(F) \neq 2$ a result similar to the above holds true for the long root geometries $B_{n,2}(F)$ and $D_{n,2}(F)$, where the points are the lines of the polar spaces associated with the orthogonal groups $\mathrm{O}(2n+1,F)$ and $O^+(2n,F)$ respectively. The only difference with the case of $A_{n,\{1,n\}}(F)$ is that both $B_{n,2}(F)$ and $D_{n,2}(F)$ admit the absolutely universal embedding. $$ $$ Theorem 3. Let $\mathrm{char}(F) \neq 2$. (1) Let $n > 2$. Then the adjont embedding of $B_{n,2}(F)$ in the Lie algebra $\mathrm{o}(2n+1,F)$ is universal if and only if $F$ admits no non-trivial derivation. (2) The adjoint embedding of $D_{n,2}(F)$ in the Lie algebra $\mathrm{o}(2n,F)$ is universal if and only if $F$ admits no no-trivial derivation.

Let $\alpha(\mathbb{F}^d_q,p)$ be the maximum possible size of a point set in general position in the p-random subset of $\mathbb{F}^d_q$. Building upon recent results of Balogh and Luo about $\alpha(\mathbb{F}^3_q,p)$, we determine $\alpha(\mathbb{F}^4_q,p)$ up to a polylogarithmic factor. Joint work with Yaobin Chen and Wentao Zhang.

Linear codes attaining the Griesmer bound are called Griesmer codes. Let $C$ be an $[n,k,d]_q$ Griesmer code with $q=p^f$, where $p$ is a prime and $f\ge1$ is an integer. In 1998, Ward proved that for $q=p$, if $p^e|d$, then $p^e|\mathrm{wt}(c)$ for all $c\in C$. In this talk, we will discuss recent progress on the divisibility of Griesmer codes. We show that if $q^e|d$, then $C$ has a basis consisting of $k$ codewords such that the first $\min\left\{e+1,k\right\}$ of them span a Griesmer subcode with constant weight $d$ and any $k-1$ of them span a $[g_q(k-1,d),k-1,d]_q$ Griesmer subcode. Using the $p$-adic algebraic method with this basis, we prove that if $q^e|d$, then $p^e|\mathrm{wt}(c)$ for all $c\in C$. Based on this fact, using the geometric approach with the aforementioned basis, we show that if $p^e|d$, then $\left\lceil p^{e-(f-1)(q-2)}\right\rceil|\mathrm{wt}(c)$ for all $c\in C$.

Let $G$ be a finite group and $c$ a real-valued function defined on $G$. The Cayley color graph of $G$ with connection function $c$, denoted by $\mathrm{Cay}(G,c)$, is the directed graph with vertex set $G$ and edge set $G\times G$ where the color of edge $(x,y)$ is given by $c(xy^{-1})$. In this talk, we introduce a natural connection between Cayley color graphs and incidence theorems of Szemer\'edi-Trotter type. We establish an expander mixing lemma for Cayley color graphs and, as applications, prove several new incidence theorems involving multivariate polynomials.

Problem: Bhowmick and Roche-Newton show that the number of arcs in $\mathbb{F}^2_q$ is at most $2^{q+q^{4/5+o(1)}}$, while a trivial lower bound is $2^{q}$. Try to improve these bounds.

We present the first construction of a family of explicit, optimal functional-repair storage codes with parameters attaining the cut-set bound, in extremal points different from the MSR and MSB points. It is well known that such parameters cannot be realized by exact-repair storage codes. These codes are linear, defined over small fields, and come with an explicit, relatively simple repair method.

In this talk, I will present new explicit constructions of families of quasi-random hypergraphs based on algebraic properties of multivariate polynomials over finite fields. Our construction not only offers a systematic method for constructing quasi-random hypergraphs but also provides a unified framework for studying various hypergraphs arising from multivariate polynomials over finite fields, including Paley sum hypergraphs, and hypergraphs derived from Diophantine tuples and their generalizations. Using these quasi-random constructions, I will also give an asymptotic formula for the number of $k$-Diophantine $m$-tuples over finite fields, addressing a question of Hammonds et al. This is joint work with Seoyoung Kim (Universität Basel) and Chi Hoi Yip (Georgia Institute of Technology).