## Korea-Taiwan-Vietnam joint seminar in Combinatorics and Analysis

Introduction:

We aim to invite researchers to present results in which Combinatorics and Analysis interact in an interesting fashion. One of the main purposes is to create a research environment in particular for people in Korea, Taiwan, and Vietnam to get to know each other and stimulate joint works. We also expect the joint seminar helps local researchers to maintain their research enthusiasm and to cultivate young talents.

The seminar is held in ZOOM

Link: https://us02web.zoom.us/j/87167950828?pwd=UFpHTkcwaDZWTndsRGloRE5yN2tIdz09 (updated)

Zoom Meeting ID: 871 6795 0828

Passcode: 352266

If you want to be added to the mailing list, please email Thang Pham (thangpham.math@vnu.edu.vn).

Organizers: Doowon Koh, Thang Pham, Chun-Yen Shen, and Tuan Tran

Upcoming meeting: The Korea-Taiwan-Vietnam Joint Meeting on Discrete Geometry and Geometric Measure Theory

Upcoming (February 2023-July 2023): Updating

Date and Time: February 17, Friday 9:00 am Hanoi time (February 16, Thursday 8:00 pm CST)

Speaker: Chun-Hung Liu (Texas A&M University, USA)

Title: Homomorphism counts in robustly sparse graphs

Abstract:

For a fixed graph H and for arbitrarily large host graphs G, the number of homomorphisms from H to G and the number of subgraphs isomorphic to H contained in G have been extensively studied when the host graphs are allowed to be dense. This talk addresses the case when the host graphs are robustly sparse. We determine, up to a constant multiplicative error, the maximum number of subgraphs isomorphic to H contained in an n-vertex graph in any fixed hereditary graph class with bounded expansion. This result solves a number of open questions and can be generalized to counting the number of homomorphisms from H.

-------------------------------------------------------------------------------------------------------------------------

Date and Time: March 3, Friday 2:00 pm Hanoi time

Speaker: Dabeen Lee (Korea Advanced Institute of Science & Technology, Korea)

Title: Non-smooth, Holder-smooth, and Robust Submodular Maximization.

Abstract: We study the problem of maximizing a continuous DR-submodular function that is not necessarily smooth. We prove that the continuous greedy algorithm achieves an $[(1-1/e)\text{OPT}-\epsilon]$ guarantee when the function is monotone and H\"older-smooth, meaning that it admits a H\"older-continuous gradient. For functions that are non-differentiable or non-smooth, we propose a variant of the mirror-prox algorithm that attains an $[(1/2)\text{OPT}-\epsilon]$ guarantee. We apply our algorithmic frameworks to robust submodular maximization and distributionally robust submodular maximization under Wasserstein ambiguity. In particular, the mirror-prox method applies to robust submodular maximization to obtain a single feasible solution whose value is at least $(1/2)\text{OPT}-\epsilon$. For distributionally robust maximization under Wasserstein ambiguity, we deduce and work over a submodular-convex maximin reformulation whose objective function is H\"older-smooth, for which we may apply both the continuous greedy method and the mirror-prox method.

-------------------------------------------------------------------------------------------------------------------------

Date and Time: March 17, Friday, 2:00 pm Hanoi time.

Speaker: Jaehoon Kim (Korea Advanced Institute of Science and Technology, Korea)

Title: A bandwidth theorem for graph transversals

Abstract: Given a collection $\mathcal{G}=(G_1,\dots, G_h)$ of graphs on the same vertex set $V$ of size $n$, an $h$-edge graph $H$ on the vertex set $V$ is a $\mathcal{G}$-transversal if there exists a bijection $\lambda : E(H) \rightarrow [h]$ such that $e\in E(G_{\lambda(e)})$ for each $e\in E(H)$. The conditions on the minimum degree $\delta(\mathcal{G})=\min_{i\in[h]}\{ \delta(G_i)\}$ for finding a spanning $\mathcal{G}$-transversal isomorphic to a graph $H$ have been actively studied when $H$ is a Hamilton cycle, an $F$-factor, a spanning tree with maximum degree $o(n/\log n)$ and a power of a Hamilton cycle, etc. We determined the asymptotically tight threshold on $\delta(\mathcal{G})$ for finding a $\mathcal{G}$-transversal isomorphic to $H$ when $H$ is a general $n$-vertex graph with bounded maximum degree and $o(n)$-bandwidth. This provides a transversal generalization of the celebrated Bandwidth theorem by B\"ottcher, Schacht and Taraz. This is joint work with Debsoumya Chakraborti, Seonghyuk Im and Hong Liu

---------------------------------------------------------------------------------------------------------------------------

Date and Time: March 31, Friday, 9:00 am Hanoi time.

Speaker: Van Khu Vu (National University of Singapore, Singapore)

Title: Locally-constrained de Bruijn codes and their applications.

Abstract: The de Bruijn graph, its sequences, and their various generalizations, have found many applications, including cryptography, wireless sensor network, robot localization, quantum communication.

In this talk, motivated by some applications for emerging memory technologies, including racetrack memories and DNA based storage, we generalize the window property of de Bruijn sequences to define a new combinatorial object, called locally-constrained de Bruijn sequence. In a [b,k]-locally-constrained de Bruijn sequence, any subset of b consecutive substrings of length k contains exactly b distint k-tuples.

A set of such sequences will be called a locally-constrained de Bruijn code. We investigate several properties of these sequences and propose various enumeration techniques to design these codes.

Finally, we show how these locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the l-symbol read channel and in the racetrack memory channel.

--------------------------------------------------------------------------------------------------------------------------

Date and Time: April 07, Friday 3:00 pm Hanoi time

Speaker: Chieu-Minh Tran (National University of Singapore, Singapore)

Title: Measure doubling of small sets in $\mathrm{SO}(3,\mathbb{R})$

Abstract: Let $\mathrm{SO}(3,\mathbb{R})$ be the 3D-rotation group equipped with the real-manifold topology and the normalized Haar measure $\mu$. An old problem in multiplicative combinatorics asks whether $$ \mu(A^2) > 3.99 \mu(A)$$ for open $A \subseteq $\mathrm{SO}(3,\mathbb{R})$ with sufficiently small measure. This question was described in Ben Green’s list of open problems, where it was also attributed to discussion with Emmanuel Breuillard. In this talk, I will discuss recent joint work with Yifan Jing and Ruixiang Zhang where we combine techniques from model theory, probability theory, and harmonic analysis to positively answer the above question.

-----------------------------------------------------------------------------------------------------------------------

Date and Time: April 21, Friday 9:00 am Hanoi time

Speaker: Minki Kim (Gwangju Institute of Science and Technology, Korea)

Title: Strong Erd\H{o}s-Hajnal properties in chordal graphs

Abstract: A graph class is said to have the strong Erd\H{o}s-Hajnal property (SEH property) if, for every graph in the class, the graph itself or its complement contains a balanced complete bipartite graph of linear size. Recently, we obtain a quantitatively tight result on the SEH property of chordal graphs. In addition, we discuss a colored version of this property for chordal graphs with bounded leafage. In particular, we show that for every pair $F_1, F_2$ of subtree families in a tree with $k$ leaves, there exist subfamilies $F_1' \subset F_1$ and $F_2' \subset F_2$ with $|F_i'| = \Theta\left(\frac{\log{k}}{k}|F_i| \right)$ such that either every colorful pair is intersecting or there is no intersecting colorful pair. This is joint work with Minho Cho, Andreas Holmsen, and Jinha Kim.

-----------------------------------------------------------------------------------------------------------------------

Previous talks (Feb 2022-December 2022):

Date and Time: Feb 24, Thursday 9 am Hanoi time (Feb 23, Wednesday 9 pm EST time)

Speaker: Alex Iosevich (University of Rochester New York, USA)

Title: Point configurations from a universal standpoint

Abstract: Given a compact subset $E$ of Euclidean space of dimension $s>\frac{d}{2}$, and a Frostman measure $\mu$ on this set, we are going to consider operators of the form $T_Kf(x)=\int K(x,y) f(y) d\mu(y),$$ where $K$ is a non-negative $L^1$ kernel or a compactly supported measure. We form a distance graph by taking the points of $E$ as vertices and connecting two vertices $x,y$ by an edge if $K(x,y)>0$. We are going to see that many of the classical distance set techniques go through in this setting. We will also see that this point of view allows us to recover configurations that would have been difficult to achieve with classical methods.

---------------------------------------------------------------------------------------------------------------------------

Date and Time: March 11, Friday 9 am Hanoi time

Speaker: Shagnik Das (National Taiwan University, Taiwan)

Title: Schur's Theorem for randomly perturbed sets

Abstract:

A set A of integers is said to be Schur if any two-colouring of A results in monochromatic x,y and z with x+y=z. We study the following problem: how many random integers from [n] need to be added to some subset A of [n] to ensure with high probability that the resulting set is Schur? Hu showed in 1980 that when |A|> 4n/5, no random integers are needed, as A is already guaranteed to be Schur. Recently, Aigner-Horev and Person showed that for any dense set of integers A, adding ω(n^{1/3}) random integers suffices, noting that this is optimal for sets A with |A| < n/2. We close the gap between these two results by showing that if |A| = n/2 + t < 4n/5, then adding ω( min (n^{1/3} , n/t) ) random integers will with high probability result in a set that is Schur. Our result is optimal for all t, and we further provide a stability result showing that one needs far fewer random integers when A is not close in structure to the extremal examples. Finally, we initiate the study of perturbing sparse sets of integers by providing nontrivial upper and lower bounds for the number of random integers that need to be added in this case.

This is joint work with Charlotte Knierem (ETH Zurich) and Patrick Morris (FU Berlin).

-------------------------------------------------------------------------------------------------------------------------

Date and Time: March 24, Thursday 9 am Hanoi time (March 23, Wednesday 10 pm EST time)

Speaker: Eyvindur Ari Palsson (Virginia Tech, USA)

Title: Triangles and triangle averaging operators

Abstract:

Point configuration questions can give rise to geometric averaging operators. A natural example is the spherical averaging operator, which can encode the simple point configuration that is given by distance. In this talk I will introduce a multilinear analogue, the triangle averaging operator and discuss some recent work on its mapping properties. If time permits I will also discuss a recent Mattila-Sjolin type theorem for triangles.

Date and Time: April 8, Friday, 2.30 pm Hanoi time.

Speaker: Ali Mohammadi (Institute for Research in Fundamental Sciences, Iran)

Title: Energy estimates over finite fields and applications

Abstract:

I will begin by discussing a range of energy estimates, which are closely related to the sum-product problem over finite fields. I will then explore a number of applications including improved bounds on the few sums, many products problem, and expansion of orbits of dynamical systems generated by quadratic maps.

In particular, I will give a brief overview of the methods of Cilleruelo, Garaev, Ostafe, and Shparlinski (2012) and Chang (2014), in the study of polynomial orbits, highlighting the superiority of more recent techniques based on incidence geometry.

The talk will include results from joint works with Bryce Kerr, Thang Pham, Sophie Stevens, and Yiting Wang.

---------------------------------------------------------------------------------------------------------------------------

Date and Time: April 22, Friday, 9:00 am Hanoi time.

Speaker: Tuan Tran (Institute for Basic Science, Korea)

Title: Exponential decay of intersection volume and applications

Abstract:

When two balls in a metric space have small intersection?

We give some natural conditions to guarantee an exponential decay on the volume of such intersections.

Our proof is conceptually simple, making use of concentration of measure on a “slice”.

We will discuss a couple of applications of this volume estimate in coding theory.

This is joint work with Hong Liu and Jaehoon Kim.

--------------------------------------------------------------------------------------------------------------------------

Date and Time: May 04, Wednesday 8 am Hanoi time

Speaker: Huy Tuan Pham (Stanford University, USA)

Title: A proof of the Kahn-Kalai conjecture

Abstract:

Kahn and Kalai conjectured that the threshold of an increasing property is always within a logarithmic factor of the expectation threshold, a quantity often much easier to compute. The Kahn-Kalai conjecture directly implies a number of difficult results in probabilistic combinatorics. I will discuss recent joint work with Jinyoung Park that resolves the Kahn-Kalai conjecture. Time permitting, I will discuss our resolution of some conjectures and questions of Talagrand, which were in fact the precursor to the resolution of the Kahn-Kalai conjecture.

-----------------------------------------------------------------------------------------------------------------------

Date and Time: May 11, Wednesday 9 am Hanoi time

Speaker: Changkeun Oh (University of Wisconsin-Madison)

Title: Decoupling inequalities for quadratic forms

Abstract :

In this talk, I will present some recent progress on decoupling inequalities for some translation- and dilation-invariant systems (TDI systems in short). In particular, I will emphasize decoupling inequalities for quadratic forms. Joint work with Shaoming Guo, Pavel Zorin-Kranich, and Ruixiang Zhang.

Date and Time: May 31, Tuesday 9 am Hanoi time

Speaker: Sang-il Oum (IBS Discrete Mathematics Group & KAIST)

Title: Building the hierarchy of graph classes

Abstract:

We will give a survey on the classification of graph classes in terms of the transductions in certain logic such as monadic second-order logic and first-order logic. We will discuss how a recent theorem of the speaker with O-joung Kwon, Rose McCarty, and Paul Wollan and an old theorem of the speaker with Bruno Courcelle solve cases of the problem of characterizing graph classes in terms of counting monadic second-order logic of the first kind.

Date and Time: June 14, Tuesday 9 am Hanoi time

Speaker: Khanh Nguyen Duc (State University of New York at Albany)

Title: A Murnaghan-Nakayama rule for Grothendieck polynomials of Grassmannian type.

Abstract:

The Grothendieck polynomials appearing in the K-theory of Grassmannians are analogs of Schur polynomials. We establish a version of the Murnaghan-Nakayama rule for Grothendieck polynomials of the Grassmannian type. This rule allows us to express the product of a Grothendieck polynomial with a power sum symmetric polynomial into a linear combination of other Grothendieck polynomials.

Date and Time: September 09, Friday at 02:00 pm Hanoi time

Speaker: Oliver Roche-Newton (Johannes Kepler Universität in Linz, Austria)

Title: Counting arcs in F_q^2

Abstract: An arc is a set of points in F_q^2 which does not contain any collinear triples. This talk will discuss how the method of hypergraph containers can be used to prove various counting results concerning the number of arcs in F_q^2. For instance, I will discuss a recent result which shows that there are 2^{(1+o(1))q} arcs in F_q^2. This bound is optimal up to the o(1) factor, as can be seen by considering any arc of size q and all of its subsets.

The talk is based on joint work with Audie Warren and Krishnendu Bhowmick.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Date and Time: September 16, Friday at 08:00 am Hanoi time

Speaker: Andreas Holmsen (Korea Advanced Institute of Science and Technology)

Title: Some recent results on geometric transversals

Abstract: Helly's theorem on the intersections of convex sets has a long history with a number of deep generalizations and variations. One possible generalization deals with geometric transversals, where instead of intersecting a family of convex sets by a point, we want to intersect the sets by a k-dimensional affine subspace. In this talk I will go over some recent results and open problems in this area.

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Date and Time: October 14, Friday at 02:00 pm Hanoi time

Speaker: Shakhar Smorodinsky (Department of Mathematics, Ben-Gurion University)

Title: A Solution to Ringel’s Circle Problem (1959)

Abstract: In 1959 Gerhard Ringel posed the following problem which remained open for over 60 years. Suppose we are given a finite family C of circles in the plane no three of which are pairwise tangent at the same point. Is it possible to always color the circles with five colors so that tangent circles get distinct colors? When the circles are not allowed to overlap (i.e., the discs bounded by the circles are pairwise interiorly disjoint) then the number of colors that always suffice is four and this fact is equivalent to the Four-Color-Theorem for planar graphs. We construct families of circles in the plane such that their tangency graphs have arbitrarily large girth and chromatic number. Moreover, no two circles are internally tangent and no two circles are concentric. This provides a strong negative answer to Ringel’s 1959 open problem. The proof relies on a (multidimensional) version of Gallais theorem with polynomial constraints, which we derive using tools from Ramsey-Theory.

Joint work with James Davis, Chaya Keller, Linda Kleist and Bartosz Walczak

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Date and Time: October 28, Friday at 09:00 am Hanoi time.

Speaker: Semin Yoo (School of Computational Sciences at Korea Institute for Advanced Study)

Title: Weak Bruhat interval modules of the $0$-Hecke algebras for genomic Schur functions

Abstract:

This talk will be mostly devoted to convey about the story around our work without details. In 2017, Yong and Pechenik introduced the genomic Schur function as a natural deformation of the ordinary Schur function in the context of the K-theory of Grassmannians. They showed that genomic Schur functions consist of a basis of the ring of symmetric functions, although they are not Schur-positive in general. Recently, Pechenik proved that genomic Schur functions are expanded positively in terms of fundamental quasisymmetric functions, implying the possibility of the existence of nice $0$-Hecke modules corresponding to genomic Schur functions under quasisymmetric characteristics.

Since the mid-2010s, there have been considerable attempts to provide a representation-theoretic interpretation of noteworthy quasisymmetric functions by constructing appropriate $0$-Hecke modules. Very recently, Jung, Kim, Lee, and Oh introduced weak Bruhat interval modules to provide a unified method to study those $H_{n}(0)$-modules.

In this talk, I will construct new $0$-Hecke modules whose quasisymmetric characteristics are the homogeneous components of genomic Schur functions and study their structural properties. Furthermore, I will decompose of our modules into weak Bruhat interval modules and find the projective cover of each summand of the decomposition.

This is joint work with Young-Hun Kim.

Date and Time: November 11, 09:00 am Hanoi time

Speaker: Chamsol Park (Johns Hopkins University)

Title: Restriction of the Laplace-Beltrami and Schrodinger operator on compact manifolds

Abstract: Studying eigenfunction estimates of the Laplace-Betrami operator has been an interesting topic in harmonic analysis. Seminal work by Sogge gives us the eigenfunction estimates of the Laplace-Beltrami operator on compact Riemannian manifolds. Their restriction analogues were studied by Burq, Gerard, and Tzvetkov, and Hu, and there have been many related studies afterwards. In this talk, we summarize known eigenfunction estimates of the Laplace-Betrami and Schrodinger operators on compact Riemannian manifolds, and talk about future work.

Date and Time: November 25, Friday at 09:00 am Hanoi time

Speaker: Tung T. Nguyen (Western University, Canada)

Title: On the Paley graph of a quadratic character

Abstract: Paley graphs represent a useful class of graphs with interesting properties. Classically, for each prime number p, we can construct the corresponding Paley graph using quadratic and non-quadratic residues modulo p. In this talk, we introduce the generalized Paley graphs. These are graphs that are associated with a general quadratic character. We will then provide some of their basic properties. In particular, we describe their spectrum explicitly and then utilize them to construct some new families of Ramanujan graphs. Time permitting, we will provide an effective upper bound for the Cheeger number of these generalized Paley graphs.

Date and Time: December 02, Friday at 08:00 am CET (14:00 Hanoi time)

Speaker: Pálvölgyi Dömötör (Head of Combinatorial Geometry Research Group, ELTE, Hungary)

Title: Hyperposets from planar orientations

Abstract: We introduce a novel definition of orientation on the triples of a family of pairwise intersecting planar convex sets and study its properties. In particular, we compare it to other systems of orientations on triples that satisfy a natural interiority condition, introduced in this form by Knuth. Such systems, P3O (partial 3-order), are a natural generalization of posets, and include the order types of planar point sets. Our main result is that P3O that emerge from points sets, and P3O that emerge from convex sets, do not contain each other. We also extend our orientation to other good covers from convex sets and study the resulting P3O's.

Based on joint work with Ágoston, Damásdi, and Keszegh:

https://arxiv.org/abs/2206.01721

https://arxiv.org/abs/2206.01723

Date and Time: December 16, Friday at 02:00 pm Hanoi time

Speaker: Joonkyung Lee (Hanyang University, Korea)

Title: Extended commonality of paths and cycles via Schur convexity

Abstract: A graph H is common if the number of monochromatic copies of H in a 2-edge-colouring of the complete graph $K_n$ is asymptotically minimised by the random colouring, or equivalently, $t_H(W)+t_H(1-W)\geq 2^{1-e(H)}$ holds for every graphon $W:[0,1]^2\rightarrow [0,1]$, where $t_H(.)$ denotes the homomorphism density of the graph H. Paths and cycles being common is one of the earliest cornerstones in extremal graph theory, due to Mulholland and Smith (1959), Goodman (1959), and Sidorenko (1989).

We prove a graph homomorphism inequality that extends the commonality of paths and cycles.

Namely, $t_H(W)+t_H(1-W)\geq t_{K_2}(W)^{e(H)} +t_{K_2}(1-W)^{e(H)}$ whenever H is a path or a cycle and $W:[0,1]^2\rightarrow\mathbb{R}$ is a bounded symmetric measurable function.

This answers a question of Sidorenko from 1989, who proved a slightly weaker result for even-length paths to prove the commonality of odd cycles.

Furthermore, it also settles a recent conjecture of Behague, Morrison, and Noel in a strong form, who asked if the inequality holds for graphons W and odd cycles H. Our proof uses Schur convexity of complete homogeneous symmetric functions, which may be of independent interest.

Joint work with Jang Soo Kim.

Sponsors