Ross Kang3d ago

https://arxiv.org/abs/2603.12358

Here is the *third* manuscript coming out of the "Topics in Ramsey theory" online-only problem-solving session (https://sparse-graphs.mimuw.edu.pl/doku.php?id=sessions:2025sessions:2025session1) of the Sparse (Graphs) Coalition, which took place less than a year ago.

It is still surprising to realise what one can make of such events, if they are set up well.

#combinatorics #remoteconferences #graphtheory #extremalcombinatorics #openscience

Ordered Ramsey and Turán numbers of alternating paths and their variants

An ordered graph is a graph whose vertex set is equipped with a total order. The ordered complete graph $K_N^<$ is the complete graph with vertex set $[N]$ equipped with the natural ordering of the integers. Given an ordered graph $H$, the ordered Ramsey number $R_<(H)$ is the smallest integer $N$ such that every red/blue edge-colouring of $K_N^<$ contains a monochromatic copy of $H$ with vertices appearing in the same relative order as in $H$. Balko, Cibulka, Král, and Kyn\v cl asked whether, among all ordered paths on $n$ vertices, the ordered Ramsey number is minimised by the alternating path $\mathrm{AP}_n$ -- the ordered path with vertex set $[n]$ such that the vertices encountered along the path are $1, n, 2, n - 1,3, n-2,\dots$. Motivated by this problem, we make progress on establishing the value of $R_<(\mathrm{AP}_n)$ by proving that \[ R_{<}(\mathrm{AP}_n)\leq \left(2+\frac{\sqrt{2}}{2}+o(1)\right)n. \] We then use similar methods to determine the exact ordered Turán number of $\mathrm{AP}_n$, and study the ordered Ramsey and Turán numbers of several related ordered paths.

arXiv.org
Ross KangJan 29

RE: https://mastoxiv.page/@arXiv_mathCO_bot/115904052353835071

Here is the second manuscript coming out of the "Topics in Ramsey theory" online-only problem-solving session (https://sparse-graphs.mimuw.edu.pl/doku.php?id=sessions:2025sessions:2025session1) of the Sparse (Graphs) Coalition, which took place less than a year ago.

The first manuscript already came out a couple months earlier (https://arxiv.org/abs/2510.17981).

Both have made serious progress in serious Erdős problems.

#combinatorics #remoteconferences #graphtheory #extremalcombinatorics #erdős

Ross KangOct 22

Here's some new work that came from last month's Sparse (Graphs) Coalition session on Ramsey numbers:

https://mathstodon.xyz/@WouterCvB/115418077892309375

#combinatorics #ExtremalCombinatorics #graphtheory #remoteconferences

Wouter (@[email protected])

New paper on multicolour Ramsey numbers. The best part? It's only 4 pages. https://arxiv.org/abs/2510.17981

Mathstodon
Ross KangMay 21, 2025

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, 2025

(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, 2025

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, 2025

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, 2025

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