Source author record

Abhishek Methuku

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Discrete Mathematics

Catalog footprint

Research overview

13works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Rainbow Turán number of clique subdivisions

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 bound on the number of edges is sharp up to the $o(1)$ error term. This is a rainbow analogue of some classical results on clique subdivisions and extends some results on rainbow Turán numbers. Our method relies on the framework introduced by Sudakov and Tomon[2020] which we adapt to find robust expanders in the coloured setting.

preprint2022arXiv

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

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 following holds. Every $n$ -vertex Steiner triple system contains all hypertrees with at most $(1-μ)n$ vertices whenever $n\geq n_0$ . We prove this conjecture.

preprint2021arXiv

Minimizing the number of complete bipartite graphs in a $K_s$ -saturated graph

A graph $G$ is $F$ -saturated if it contains no copy of $F$ as a subgraph but the addition of any new edge to $G$ creates a copy of $F$ . We prove that for $s \geq 3$ and $t \geq 2$ , the minimum number of copies of $K_{1,t}$ in a $K_s$ -saturated graph is $Θ( n^{t/2})$ . More precise results are obtained when $t = 2$ where the problem is related to Moore graphs with diameter 2 and girth 5. We prove that for $s \geq 4$ and $t \geq 3$ , the minimum number of copies of $K_{2,t}$ in an $n$ -vertex $K_s$ -saturated graph is at least $Ω( n^{t/5 + 8/5})$ and at most $O(n^{t/2 + 3/2})$ . These results answer a question of Chakraborti and Loh. General estimates on the number of copies of $K_{a,b}$ in a $K_s$ -saturated graph are also obtained, but finding an asymptotic formula remains open.

preprint2020arXiv

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

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 the problem of finding a majority vertex (or show that none exists) if we can query edges to learn whether their endpoints have the same or different colors. Denote the least number of queries needed in the worst case by $m(G)$ . It was shown by Saks and Werman that $m(K_n)=n-b(n)$ , where $b(n)$ is the number of 1's in the binary representation of $n$ . In this paper, we initiate the study of the problem for general graphs. The obvious bounds for a connected graph $G$ on $n$ vertices are $n-b(n)\le m(G)\le n-1$ . We show that for any tree $T$ on an even number of vertices we have $m(T)=n-1$ and that for any tree $T$ on an odd number of vertices, we have $n-65\le m(T)\le n-2$ . Our proof uses results about the weighted version of the problem for $K_n$ , which may be of independent interest. We also exhibit a sequence $G_n$ of graphs with $m(G_n)=n-b(n)$ such that $G_n$ has $O(nb(n))$ edges and $n$ vertices.

preprint2020arXiv

Edge colorings of graphs without monochromatic stars

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 entropy inequality of Shearer.

preprint2020arXiv

On $3$ -uniform hypergraphs avoiding a cycle of length four

In this note we show that the maximum number of edges in a $3$ -uniform hypergraph without a Berge cycle of length four is at most $(1+o(1))\frac{n^{3/2}}{\sqrt{10}}$ . This improves earlier estimates by Győri and Lemons and by Füredi and Özkahya.

preprint2020arXiv

Rainbow Ramsey problems for the Boolean lattice

We address the following rainbow Ramsey problem: For posets $P,Q$ what is the smallest number $n$ such that any coloring of the elements of the Boolean lattice $B_n$ either admits a monochromatic copy of $P$ or a rainbow copy of $Q$ . We consider both weak and strong (non-induced and induced) versions of this problem. We also investigate related problems on (partial) $k$ -colorings of $B_n$ that do not admit rainbow antichains of size $k$ .

preprint2020arXiv

The exact linear Turán number of the Sail

A hypergraph is linear if any two of its edges intersect in at most one vertex. The Sail (or $3$ -fan) $F^3$ is the $3$ -uniform linear hypergraph consisting of $3$ edges $f_1, f_2, f_3$ pairwise intersecting in the same vertex $v$ and an additional edge $g$ intersecting all $f_i$ in a vertex different from $v$ . The linear Turán number $ex_{lin}(n, F^3)$ is the maximum number of edges in a $3$ -uniform linear hypergraph on $n$ vertices that does not contain a copy of $F^3$ . Füredi and Gyárfás proved that if $n = 3k$ , then $ex_{lin}(n, F^3) = k^2$ and the only extremal hypergraphs in this case are transversal designs. They also showed that if $n = 3k+2$ , then $ex_{lin}(n, F^3) = k^2+k$ , and the only extremal hypergraphs are truncated designs (which are obtained from a transversal design on $3k+3$ vertices with $3$ groups by removing one vertex and all the hyperedges containing it) along with three other small hypergraphs. However, the case when $n =3k+1$ was left open. In this paper, we solve this remaining case by proving that $ex_{lin}(n, F^3) = k^2+1$ if $n = 3k+1$ , answering a question of Füredi and Gyárfás. We also characterize all the extremal hypergraphs. The difficulty of this case is due to the fact that these extremal examples are rather non-standard. In particular, they are not derived from transversal designs like in the other cases.

preprint2016arXiv

An improvement of the general bound on the largest family of subsets avoiding a subposet

Let $La(n,P)$ be the maximum size of a family of subsets of $[n]= \{1,2, ..., n \}$ not containing $P$ as a (weak) subposet, and let $h(P)$ be the length of a longest chain in $P$ . The best known upper bound for $La(n,P)$ in terms of $|P|$ and $h(P)$ is due to Chen and Li, who showed that $La(n,P) \le \frac{1}{m+1} \left(|P| + \frac{1}{2}(m^2 +3m-2)(h(P)-1) -1 \right) {\binom {n} {\lfloor n/2 \rfloor}}$ for any fixed $m \ge 1$ . In this paper we show that $La(n,P) \le \frac{1}{2^{k-1}} (|P| + (3k-5)2^{k-2}(h(P)-1) - 1 ) {n \choose {\lfloor n/2\rfloor} }$ for any fixed $k \ge 2$ , improving the best known upper bound. By choosing $k$ appropriately, we obtain that $La(n,P) = O\left( h(P) \log_2\left(\frac{|P|}{h(P)}+2\right) \right) {n \choose \lfloor n/2 \rfloor }$ as a corollary, which we show is best possible for general $P$ . We also give a different proof of this corollary by using bounds for generalized diamonds. We also show that the Lubell function of a family of subsets of $[n]$ not containing $P$ as an induced subposet is $O(n^c)$ for every $c>\frac{1}{2}$ .

preprint2016arXiv

On the Linear Cycle Cover Conjecture of Gyárfás and Sárközy

A linear cycle in a hypergraph $H$ is a cyclic sequence of hyperedges such that two consecutive hyperedges intersect in exactly one element and two nonconsecutive hyperedges are disjoint and $α(H)$ denotes the size of a largest independent set of $H$ . In this note, we show that the vertex set of every $3$ -uniform hypergraph $H$ can be covered by at most $α(H)$ pairwise edge-disjoint linear cycles (where we accept a vertex and a hyperedge as a linear cycle), proving a weaker version of a conjecture of Gyárfás and Sárközy.

preprint2015arXiv

De Bruijn-Erdős type theorems for graphs and posets

A classical theorem of De Bruijn and Erdős asserts that any noncollinear set of n points in the plane determines at least n distinct lines. We prove that an analogue of this theorem holds for graphs. Restricting our attention to comparability graphs, we obtain a version of the De Bruijn-Erdős theorem for partially ordered sets (posets). Moreover, in this case, we have an improved bound on the number of lines depending on the height of the poset. The extremal configurations are also determined.

preprint2014arXiv

Exact forbidden subposet results using Chain decompositions of the Cycle

We introduce a method of decomposing the family of intervals along a cyclic permutation into chains to determine the size of the largest family of subsets of $[n]:= \{1,2,...,n\}$ not containing one or more given posets as a subposet. De Bonis, Katona and Swanepoel determined the size of the largest butterfly-free family. We strengthen this result by showing that, for certain posets containing the butterfly poset as a subposet, the same bound holds. We also obtain the corresponding LYM-type inequalities.

preprint2014arXiv

Forbidden hypermatrices imply general bounds on induced forbidden subposet problems

We prove that for every poset $P$ , there is a constant $C$ such that the size of any family of subsets of $[n]$ that does not contain $P$ as an induced subposet is at most $C{\binom{n}{\lfloor\frac{n}{2}\rfloor}}$ , settling a conjecture of Katona, and Lu and Milans. We obtain this bound by establishing a connection to the theory of forbidden submatrices and then applying a higher dimensional variant of the Marcus-Tardos theorem, proved by Klazar and Marcus. We also give a new proof of their result.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Abhishek Methuku

Research overview

Is this your work?

13 publications

Rainbow Turán number of clique subdivisions

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

Minimizing the number of complete bipartite graphs in a $K_s$ -saturated graph

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

Edge colorings of graphs without monochromatic stars

On $3$ -uniform hypergraphs avoiding a cycle of length four

Rainbow Ramsey problems for the Boolean lattice

The exact linear Turán number of the Sail

An improvement of the general bound on the largest family of subsets avoiding a subposet

On the Linear Cycle Cover Conjecture of Gyárfás and Sárközy

De Bruijn-Erdős type theorems for graphs and posets

Exact forbidden subposet results using Chain decompositions of the Cycle

Forbidden hypermatrices imply general bounds on induced forbidden subposet problems

See the researcher in context

Building this map preview

Abhishek Methuku

Research overview

Is this your work?

13 publications

Rainbow Turán number of clique subdivisions

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

Minimizing the number of complete bipartite graphs in a KsK_sKs​-saturated graph

Adaptive Majority Problems for Restricted Query Graphs and for Weighted Sets

Edge colorings of graphs without monochromatic stars

On 333-uniform hypergraphs avoiding a cycle of length four

Rainbow Ramsey problems for the Boolean lattice

The exact linear Turán number of the Sail

An improvement of the general bound on the largest family of subsets avoiding a subposet

On the Linear Cycle Cover Conjecture of Gyárfás and Sárközy

De Bruijn-Erdős type theorems for graphs and posets

Exact forbidden subposet results using Chain decompositions of the Cycle

Forbidden hypermatrices imply general bounds on induced forbidden subposet problems

See the researcher in context

Building this map preview

Minimizing the number of complete bipartite graphs in a $K_s$ -saturated graph

On $3$ -uniform hypergraphs avoiding a cycle of length four