Ross KangMay 21

Just yesterday, I was musing to a (younger) research visitor, "I hope that within my lifetime we will still see another breakthrough on the bounds for R(3,k)"...

https://arxiv.org/abs/2505.13371

I am excited to see what developments follow on from here!

(Also that old adage: just as soon as you publish a survey (https://arxiv.org/abs/2501.03379) it is out of date.)

#math #mathematics #combinatorics #ExtremalCombinatorics #graphtheory #probability

A new lower bound for the Ramsey numbers $R(3,k)$

We prove a new lower bound for the off-diagonal Ramsey numbers, \[ R(3,k) \geq \bigg( \frac{1}{3}+ o(1) \bigg) \frac{k^2}{\log k }\, , \] thereby narrowing the gap between the upper and lower bounds to a factor of $3+o(1)$. This improves the best known lower bound of $(1/4+o(1))k^2/\log k$ due, independently, to Bohman and Keevash, and Fiz Pontiveros, Griffiths and Morris, resulting from their celebrated analysis of the triangle-free process. As a consequence, we disprove a conjecture of Fiz Pontiveros, Griffiths and Morris that the constant $1/4$ is sharp.

arXiv.org
Ross KangMay 10

(Just finished writing my laudatio speech.)

Eoin Hurley will defend his PhD on Wednesday.

https://www.uva.nl/en/content/events/2025/05/leave-it-to-chance-random-solutions-to-deterministic-problems-in-discrete-mathematics.html

#combinatorics #graphtheory #ExtremalCombinatorics #probability #algorithms #math

Leave it to Chance. Random Solutions to Deterministic Problems in Discrete Mathematics

Eoin Hurley will defend the dissertation 'Leave it to Chance. Random Solutions to Deterministic Problems in Discrete Mathematics'. Supervisors are Dr J.R. Kang and Prof. M.R.H. Mandjes.

University of Amsterdam
Ross KangMar 14

For various (mathematical, meteorological, alimentary) reasons, I usually prefer 2π day.
Nevertheless, today I make the following offering:

http://arxiv.org/abs/2503.10002

Pjotr Buys, @Janvadehe and I used Shearer's induction to address the question:

How few independent sets can a triangle-free graph of average degree d have?


The answer is close to how many a random graph has.
What is perhaps surprising is just *how* close it comes.
(I queried the combinatorial hive mind about this last week.)

#combinatorics #graphtheory #ExtremalCombinatorics #probability #math #mathematics #piDay

Triangle-free graphs with the fewest independent sets

Given $d>0$ and a positive integer $n$, let $G$ be a triangle-free graph on $n$ vertices with average degree $d$. With an elegant induction, Shearer (1983) tightened a seminal result of Ajtai, Komlós and Szemerédi (1980/1981) by proving that $G$ contains an independent set of size at least $(1+o(1))\frac{\log d}{d}n$ as $d\to\infty$. By a generalisation of Shearer's method, we prove that the number of independent sets in $G$ must be at least $\exp\left((1+o(1))\frac{(\log d)^2}{2d}n\right)$ as $d\to\infty$. This improves upon results of Cooper and Mubayi (2014) and Davies, Jenssen, Perkins, and Roberts (2018). Our method also provides good lower bounds on the independence polynomial of $G$, one of which implies Shearer's result itself. As certified by a classic probabilistic construction, our bound on the number of independent sets is sharp to several leading terms as $d\to\infty$.

arXiv.org
Ross KangJan 31

Starting out in mathematical research, especially in discrete mathematics, a big focus is problem-solving. It's like a race, and once you've solved one, you set out right away for the next adrenaline rush.

Take for granted a bustling market of open problems (again, especially in discrete mathematics). Scour papers or problem sites. Challenge close colleagues with the ones that eluded you. The harder, the better, right? There is occasionally awkward coffee talk of that intangible `taste' or `judgement', but, come on, less talk and more solving!

(please imagine here a subtly ironic tone in my voice)

(1/3)

#math
#graphtheory
#combinatorics
#ExtremalCombinatorics

Ross KangJan 31

A post of @11011110 has reminded me that (after a year and a half lurking here) it's never too late for me to toot and pin an intro here.

I am a Canadian mathematician in the Netherlands, and I have been based at the University of Amsterdam since 2022. I also have some rich and longstanding ties to the UK, France, and Japan.

My interests are somewhere in the nexus of Combinatorics, Probability, and Algorithms. Specifically, I like graph colouring, random graphs, and probabilistic/extremal combinatorics. I have an appreciation for randomised algorithms, graph structure theory, and discrete geometry.

Around 2020, I began taking a more active role in the community, especially in efforts towards improved fairness and openness in science. I am proud to be part of a team that founded the journal, Innovations in Graph Theory (https://igt.centre-mersenne.org/), that launched in 2023. (That is probably the main reason I joined mathstodon!) I have also been a coordinator since 2020 of the informal research network, A Sparse (Graphs) Coalition (https://sparse-graphs.mimuw.edu.pl/), devoted to online collaborative workshops. In 2024, I helped spearhead the MathOA Diamond Open Access Stimulus Fund (https://www.mathoa.org/diamond-open-access-stimulus-fund/).

Until now, my posts have mostly been about scientific publishing and combinatorics.

#introduction
#openscience
#diamondopenaccess
#scientificpublishing
#openaccess
#RemoteConferences
#combinatorics
#graphtheory
#ExtremalCombinatorics
#probability

Innovations in Graph Theory Innovations in Graph Theory