KAIST Discrete Math Seminar

For a module L the formal Dirichlet series $\zeta$_L(s) = ∑_{n ≥ 1</i>}a_nn^-s is defined whenever the number a_n of submodules of L with index n is finite for each positive integer n. For a ring R and a finite association scheme (X,S) we denote the adjacency algebra of (X,S) over R by RS. In this talk we aim to compute $\zeta$_ZS(s) where $$ZS is regarded as a $$ZS-module under the assumption that $|X|$ is prime or $|S|=2$.</p>

In this talk we deal with extremal results on combinatorial number theory. A typical problem is as follows. We fix a family of linear equations (for example, a+b=2c or a+b=c+d). Then we want to estimate the maximum size of subsets with no solution of the given equations in {1,2,…,n} or a random subset of {1,2,…,n} of size m < n. We consider two important examples:</p>

(1) Sets which contain no arithmetic progression of a fixed size

(2) Sidon sets (without solutions of a+b=c+d)

The first example is about the results of Roth in 1953 and Szemeredi in 1975, and the recent results by Schacht in 2009+, and Conlon-Gowers in 2010+.

Next, the second example is about the results by Erdős, Turán, Chowla, Singer in 1940s and the results by Kohayakawa, Lee, Rödl, and Samotij in 2012+.

The first application of Szemeredi’s regularity method was the following celebrated Ramsey-Turan result proved by Szemeredi in 1972: any K₄-free graph on N vertices with independence number o(N) has at most (1/8 + o(1)) N² edges. Four years later, Bollobas and Erdos gave a surprising geometric construction, utilizing the isoperimetric inequality for the high dimensional sphere, of a K₄-free graph on N vertices with independence number o(N) and (1/8 – o(1)) N² edges. Starting with Bollobas and Erdos in 1976, several problems have been asked on estimating the minimum possible independence number in the critical window, when the number of edges is about N² / 8. These problems have received considerable attention and remained one of the main open problems in this area. In this work, we give nearly best-possible bounds, solving the various open problems concerning this critical window.
More generally, it remains an important problem to determine if, for certain applications of the regularity method, alternative proofs exist which avoid using the regularity lemma and give better quantitative estimates. In their survey on the regularity method, Komlos, Shokoufandeh, Simonovits, and Szemeredi surmised that the regularity method is likely unavoidable for applications where the extremal graph has densities in the regular partition bounded away from 0 and 1. In particular, they thought this should be the case for Szemeredi’s result on the Ramsey-Turan problem. Contrary to this philosophy, we develop new regularity-free methods which give a linear dependence, which is tight, between the parameters in Szemeredi’s result on the Ramsey-Turan problem.
Joint work with Jacob Fox and Yufei Zhao.

The cube graph Q_n is the skeleton of the n-dimensional cube. It is an n-regular graph on 2ⁿ vertices. The Ramsey number r(Q_n, K_s) is the minimum N such that every graph of order N contains the cube graph Q_n or an independent set of order s. Burr and Erdős in 1983 asked whether the simple lower bound r(Q_n, K_s) ≥ (s-1)(2ⁿ -1)+1 is tight for s fixed and n sufficiently large. We make progress on this problem, obtaining the first upper bound which is within a constant factor of the lower bound.
Joint work w/ David Conlon, Jacob Fox, and Benny Sudakov

Brooks’ Theorem states that for a graph G with maximum degree Δ(G) at least 3, the chromatic number is at most Δ(G) when the clique number is at most Δ(G). Vizing proved that the list chromatic number is also at most Δ(G) under the same conditions. Borodin and Kostochka conjectured that a graph G with maximum degree at least 9 must be (Δ(G)-1)-colorable when the clique number is at most Δ(G)-1; this was proven for graphs with maximum degree at least 10¹⁴ by Reed. We prove an analogous result for the list chromatic number; namely, we prove that a graph G with Δ(G)≥ 10²⁰ is (Δ(G)-1)-choosable when the clique number is at most Δ(G)-1. This is joint work with H. A. Kierstead, L. Rabern, and B. Reed.