KAIST Discrete Math Seminar

I will discuss the Ramsey problem for {x,y,z:x+y=p(z)} for polynomials p over ℤ. This is joint work with Peter Pach and Csaba Sandor.

Counting problems on sets of integers with additive constraints have been extensively studied. In contrast, the counting problems for sets with multiplicative constraints remain largely unexplored. In this talk, we will discuss two such recent results, one on primitive sets and the other on multiplicative Sidon sets. Based on joint work with Peter Pach, and with Peter Pach and Richard Palincza.

Given graphs H₁,…, H_k, a graph G is (H₁,…, H_k)-free if there is a k-edge-colouring of G with no H_i in colour-i for all i in {1,2,…,k}. Fix a function f(n), the Ramsey-Turán function rt(n,H₁,…,H_k,f(n)) is the maximum size of an n-vertex (H₁,…, H_k)-free graph with independence number at most f(n). We determine rt(n,K₃,K_s,δn) for s in {3,4,5} and sufficiently small δ, confirming a conjecture of Erdős and Sós from 1979. It is known that rt(n,K₈,f(n)) has a phase transition at f(n)=Θ(√(n\log n)). We prove that rt(n,K₈,o(√(n\log n)))=n²/4+o(n²), answering a question of Balogh, Hu and Simonovits. The proofs utilise, among others, dependent random choice and results from graph packings. Joint work with Jaehoon Kim and Younjin Kim.

Let f(n,r) denote the maximum number of colourings of A⊆{1,…,n} with r colours such that each colour class is sum-free. Here, a sum is a subset {x,y,z} such that x+y=z. We show that f(n,2) = 2^⌈n/2⌉, and describe the extremal subsets. Further, using linear optimisation, we asymptotically determine the logarithm of f(n,r) for r≤5.
Joint work with Maryam Sharifzadeh and Katherine Staden.