Abhishek Methuku

Random independent sets in uncrowded hypergraphs

Abhishek Dhawan, Lina Li, Abhishek Methuku +2

Given any fixed integer $k \geq 2$ and sufficiently large $d$ , we show that the largest possible fractional chromatic number of a $k$ -uniform $d$ -degenerate uncrowded hypergraph $H$ …

Counting hypergraphs without linear cycles of fixed length

József Balogh, Ramon I. Garcia, Abhishek Methuku

Let $C_{k}^{(r)}$ be the $r$ -uniform linear cycle on $k$ hyperedges. An $r$ -graph is $C_{k}^{(r)}$ -free if it contains no copy of $C_{k}^{(r)}$ . Let $\operatorname{ex}_{r}(n,C_{k}^…

A nearly linear bound for the Lovász conjecture

Bowen Li, Abhishek Methuku

The celebrated conjecture of Lovász from 1969 asks whether every connected vertex-transitive graph has a Hamiltonian path. Bucić, Christoph, Pokrovskiy and Steiner recently proved…

Long Directed Cycles in Vertex-Transitive Digraphs

Bowen Li, Abhishek Methuku

The search for Hamiltonian cycles in vertex-transitive graphs and digraphs is a classical problem at the interface of graph theory and group theory. In the undirected setting, this…

List coloring uncrowded hypergraphs at the shattering threshold

Abhishek Dhawan, Abhishek Methuku, Minh-Quan Vo

Improving an earlier bound of Frieze and Mubayi, Iliopoulos showed that any $k$ -uniform uncrowded hypergraph of maximum degree $Δ$ has list chromatic number at most $(1+o(1))(k-1)\…

Independent sets and colorings of $K_{t, t, t}$ -free graphs

Abhishek Dhawan, Oliver Janzer, Abhishek Methuku

Alon, Krivelevich, and Sudakov conjectured in 1999 that every $F$ -free graph of maximum degree at most $Δ$ has chromatic number $O (Δ/ lo g Δ)$ . This was previously known only for a…

Toward Vu's conjecture

Peter Bradshaw, Abhishek Dhawan, Abhishek Methuku +1

In 2002, Vu conjectured that graphs of maximum degree $Δ$ and maximum codegree at most $ζ Δ$ have chromatic number at most $(ζ + o (1)) Δ$ . Despite its importance, the conjecture has re…

Packing subgraphs in regular graphs

Shoham Letzter, Abhishek Methuku, Benny Sudakov

An \emph{ $H$ -packing} in a graph $G$ is a collection of pairwise vertex-disjoint copies of $H$ in $G$ . We prove that for every $c > 0$ and every bipartite graph $H$ , any $\lfloor c…

Nearly Hamilton cycles in sublinear expanders, and applications

Shoham Letzter, Abhishek Methuku, Benny Sudakov

We develop novel methods for constructing nearly Hamilton cycles in sublinear expanders with good regularity properties, as well as new techniques for finding such expanders in gen…

Tight bounds for intersection-reverse sequences, edge-ordered graphs and applications

Barnabás Janzer, Oliver Janzer, Abhishek Methuku +1

In 2006, Marcus and Tardos proved that if $A^{1}, \dots, A^{n}$ are cyclic orders on some subsets of a set of $n$ symbols such that the common elements of any two distinct orders $A^{i}$ a…

Regular subgraphs at every density

Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku +1

In 1975, Erdős and Sauer asked to estimate, for any constant $r$ , the maximum number of edges an $n$ -vertex graph can have without containing an $r$ -regular subgraph. In a recent b…

Edge-disjoint cycles with the same vertex set

Debsoumya Chakraborti, Oliver Janzer, Abhishek Methuku +1

In 1975, Erdős asked for the maximum number of edges that an $n$ -vertex graph can have if it does not contain two edge-disjoint cycles on the same vertex set. It is known that Turá…

Tight general bounds for the extremal numbers of 0-1 matrices

Barnabás Janzer, Oliver Janzer, Van Magnan +1

A zero-one matrix $M$ is said to contain another zero-one matrix $A$ if we can delete some rows and columns of $M$ and replace some $1$ -entries with $0$ -entries such that the resul…

math.CO2023

Power saving for the Brown-Erdős-Sós problem

Oliver Janzer, Abhishek Methuku, Aleksa Milojević +1

Let $f (n, v, e)$ denote the maximum number of edges in a 3-uniform hypergraph on $n$ vertices which does not contain $v$ vertices spanning at least $e$ edges. A central problem in…

math.CO2023

The extremal number of cycles with all diagonals

Domagoj Bradač, Abhishek Methuku, Benny Sudakov

In 1975, Erdős asked the following natural question: What is the maximum number of edges that an $n$ -vertex graph can have without containing a cycle with all diagonals? Erdős obse…

math.CO2023

Cycles with many chords

Nemanja Draganić, Abhishek Methuku, David Munhá Correia +1

How many edges in an $n$ -vertex graph will force the existence of a cycle with as many chords as it has vertices? Almost 30 years ago, Chen, Erdős and Staton considered this questi…

math.CO2022

A proof of the Elliott-Rödl conjecture on hypertrees in Steiner triple systems

Seonghyuk Im, Jaehoon Kim, Joonkyung Lee +1

Hypertrees are linear hypergraphs where every two vertices are connected by a unique path. Elliott and Rödl conjectured that for any given $μ > 0$ , there exists $n_{0}$ such that the f…

Solution to a problem of Erdős on the chromatic index of hypergraphs with bounded codegree

Dong Yeap Kang, Tom Kelly, Daniela Kühn +2

In 1977, Erdős asked the following question: for any integers $t, n \in N$ , if $G_{1}, \dots, G_{n}$ are complete graphs such that each $G_{i}$ has at most $n$ vertices and eve…

Counting cliques in $1$ -planar graphs

J. Pascal Gollin, Kevin Hendrey, Abhishek Methuku +2

The problem of maximising the number of cliques among $n$ -vertex graphs from various graph classes has received considerable attention. We investigate this problem for the class of…

Rainbow subdivisions of cliques

Tao Jiang, Shoham Letzter, Abhishek Methuku +1

We show that for every integer $m \geq 2$ and large $n$ , every properly edge-coloured graph on $n$ vertices with at least $n (lo g n)^{53}$ edges contains a rainbow subdivision of $…

math.CO2021★ 10 cited

Rainbow Turán number of clique subdivisions

Tao Jiang, Abhishek Methuku, Liana Yepremyan

We show that for any integer $t \geq 2$ , every properly edge-coloured graph on $n$ vertices with more than $n^{1 + o (1)}$ edges contains a rainbow subdivision of $K_{t}$ . Note that this…

math.CO2021★ 3 cited

Graph and hypergraph colouring via nibble methods: A survey

Dong Yeap Kang, Tom Kelly, Daniela Kühn +2

This paper provides a survey of methods, results, and open problems on graph and hypergraph colourings, with a particular emphasis on semi-random `nibble' methods. We also give a d…