Gaurav Kucheriya

activity

20222026

collaborators

Showing math.COShow all

9 papers · 1 filter

math.CO2026

Proof of the mad conjecture and its coloring applications

Andrzej Grzesik, Lenka Kopfová, Gaurav Kucheriya +2

For a finite graph $G$ , the maximum average degree $mad (G)$ is the largest average degree of a nonempty subgraph of $G$ . Hendrey, Norin and Wood asked whether this p…

math.CO2026

Multicolor vector space Ramsey numbers over the binary field

Anurag Bishnoi, Gaurav Kucheriya

For every fixed integer $t \geq 2$ , we give an upper bound on the multicolor vector space Ramsey number $R_{2} (t; k)$ that is a tower function of height independent of $k$ . For $t \g…

math.CO2026

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

Gaurav Kucheriya, Allan Lo, Jan Petr +2

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 natura…

math.CO2026

Hunting for Directed 2-Spiders

Grzegorz Gutowski, Gaurav Kucheriya

Hons, Klimošová, Kucheriya, Mikšaník, Tkadlec, and Tyomkyn proved that, for every integer $ℓ \geq 1$ , every directed graph with minimum out-degree at least $3.23 \cdot ℓ$ cont…

math.CO2025

Unavoidable subgraphs in digraphs with large out-degrees

Tomáš Hons, Tereza Klimošová, Gaurav Kucheriya +3

We ask the question, which oriented trees $T$ must be contained as subgraphs in every finite directed graph of sufficiently large minimum out-degree. We formulate the following sim…

math.CO2024

On Turán-type problems and the abstract chromatic number

Dániel Gerbner, Hilal Hama Karim, Gaurav Kucheriya

In 2020, Coregliano and Razborov introduced a general framework to study limits of combinatorial objects, using logic and model theory. They introduced the abstract chromatic numbe…

math.CO2024

Orientations of graphs with at most one directed path between every pair of vertices

Barbora Dohnalová, Jiří Kalvoda, Gaurav Kucheriya +1

Given a graph $G$ , we say that an orientation $D$ of $G$ is a KT orientation if, for all $u, v \in V (D)$ , there is at most one directed path (in any direction) between $u$ and $v$ .…

math.CO2023

On edge-ordered graphs with linear extremal functions

Gaurav Kucheriya, Gábor Tardos

The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. in 2020. Here we characterize connected edge-ordered graphs with linear…

math.CO2022

A characterization of edge-ordered graphs with almost linear extremal functions

Gaurav Kucheriya, Gábor Tardos

The systematic study of Turán-type extremal problems for edge-ordered graphs was initiated by Gerbner et al. arXiv:2001.00849. They conjectured that the extremal functions of edge-…