Personne

Abhishek Methuku

Cette personne n’est plus à l’EPFL

Publications associées (17)

Adaptive majority problems for restricted query graphs and for weighted sets

Doemoetoer Palvoelgyi, Balázs Keszegh, Abhishek Methuku

Suppose that the vertices of a graph G are colored with two colors in an unknown way. The color that occurs on more than half of the vertices is called the majority color (if it exists), and any vertex of this color is called a majority vertex. We study th ...

ELSEVIER2021

On subgraphs of C-2k-free graphs and a problem of Kuhn and Osthus

Abhishek Methuku

Let c denote the largest constant such that every C-6-free graph G contains a bipartite and C-4-free subgraph having a fraction c of edges of G. Gyori, Kensell and Tompkins showed that 3/8

2020

A simple proof for a forbidden subposet problem

Abhishek Methuku

The poset Y-k,Y-2 consists of k + 2 distinct elements x(1), x(2), ..., x(k), y(1), y(2), such that x(1)

ELECTRONIC JOURNAL OF COMBINATORICS2020

Edge colorings of graphs without monochromatic stars

Abhishek Methuku

In this note, we improve on results of Hoppen, Kohayakawa and Lefmann about the maximum number of edge colorings without monochromatic copies of a star of a fixed size that a graph on n vertices may admit. Our results rely on an improved application of an ...

Elsevier2020

Avoiding long Berge cycles: the missing casesk=r+1 andk=r+2

Abhishek Methuku

The maximum size of anr-uniform hypergraph without a Berge cycle of length at leastkhas been determined for allk >= r+ 3 by Furedi, Kostochka and Luo and fork

2020

On clique coverings of complete multipartite graphs

Abhishek Methuku

A clique covering of a graph G is a set of cliques of G such that any edge of G is contained in one of these cliques, and the weight of a clique covering is the sum of the sizes of the cliques in it. The sigma clique cover number scc(G) of a graph G, is de ...

ELSEVIER2020

Generalized Turan Problems For Even Cycles

Abhishek Methuku

Given a graph H and a set of graphs F, let ex(n, H, F) denote the maximum possible number of copies of H in an T-free graph on n vertices. We investigate the function ex(n, H, F), when H and members of F are cycles. Let C-k denote the cycle of length k and ...

2019

Adaptive Majority Problems For Restricted Query Graphs And For Weighted Sets

Doemoetoer Palvoelgyi, Balázs Keszegh, Abhishek Methuku

COMENIUS UNIV2019

Edge Ordered Turan Problems

Doemoetoer Palvoelgyi, Gábor Tardos, Abhishek Methuku

We introduce the Turan problem for edge ordered graphs. We call a simple graph edge ordered, if its edges are linearly ordered. An isomorphism between edge ordered graphs must respect the edge order. A subgraph of an edge ordered graph is itself an edge or ...

COMENIUS UNIV2019

On the Rainbow Turan number of paths

Abhishek Methuku

Let F be a fixed graph. The rainbow Turan number of F is defined as the maximum number of edges in a graph on n vertices that has a proper edge-coloring with no rainbow copy of F (i.e., a copy of F all of whose edges have different colours). The systematic ...

ELECTRONIC JOURNAL OF COMBINATORICS2019

On the Number of Containments in P-free Families

Abhishek Methuku

A subfamily {F-1, F-2, ..., F-vertical bar P vertical bar} subset of F is a copy of the poset P if there exists a bijection i : P -> {F-1, F-2, ..., F-vertical bar P vertical bar}, such that p

Springer2019

Saturation of Berge hypergraphs

Abhishek Methuku

Given a graph F, a hypergraph is a Berge-F if it can be obtained by expanding each edge in F to a hyperedge containing it. A hypergraph H is Berge-F-saturated if H does not contain a subhypergraph that is a Berge-F, but for any edge e is an element of E((H ...

Elsevier2019

Asyrnptotics for the Turan number of Berge-K-2,K-t

Abhishek Methuku

Let F be a graph. A hypergraph is called Berge-F if it can be obtained by replacing each edge in F by a hyperedge containing it. ...

ACADEMIC PRESS INC ELSEVIER SCIENCE2019

Linearity of saturation for Berge hypergraphs

Abhishek Methuku

For a graph F, we say a hypergraph H is a Berge-F if it can be obtained from F by replacing each edge of F with a hyperedge containing it. We say a hypergraph is Berge-F-saturated if it does not contain a Berge-F, but adding any hyperedge creates a copy of ...

ACADEMIC PRESS LTD- ELSEVIER SCIENCE LTD2019

Stability results for vertex Turan problems in Kneser graphs

Abhishek Methuku

The vertex set of the Kneser graph K(n, k) is V = (([n])(k)) and two vertices are adjacent if the corresponding sets are disjoint. For any graph F, the largest size of a vertex set U subset of V such that K(n, k)[U] is F-free, was recently determined by Al ...

2019

Generalized Turan problems for disjoint copies of graphs

Abhishek Methuku

Given two graphs H and F, the maximum possible number of copies of H in an F-free graph on n vertices is denoted by ex(n, H, F). We investigate the function ex(n, H, kF), where kF denotes k vertex disjoint copies of a fixed graph F. Our results include cas ...

Elsevier2019

On the Turan number of some ordered even cycles

Istvan Tomon, Dániel József Korándi, Abhishek Methuku

2018