Abhishek Methuku

Last Name

Methuku

First Name

Abhishek

ORCID

0000-0002-5244-5365

Show all metadata

Search Results

Publications 1 - 6 of 6

Cycles with many chords
Draganić, Nemanja; Methuku, Abhishek; Munhá Correia, David; et al. (2024)
Random Structures & Algorithms
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 question and showed that any $ n $-vertex graph with $ 2{n}^{3/2} $ edges contains such a cycle. We significantly improve this old bound by showing that $ \Omega \left(n\kern0.2em {\log}^8n\right) $ edges are enough to guarantee the existence of such a cycle. Our proof exploits a delicate interplay between certain properties of random walks in almost regular expanders. We argue that while the probability that a random walk of certain length in an almost regular expander is self-avoiding is very small, one can still guarantee that it spans many edges (and that it can be closed into a cycle) with large enough probability to ensure that these two events happen simultaneously.
The Extremal Number of Cycles with All Diagonals
Bradač, Domagoj; Methuku, Abhishek; Sudakov, Benny (2024)
International Mathematics Research Notices
A proof of the Elliott-Rodl conjecture on hypertrees in Steiner triple systems
Im, Seonghyuk; Kim, Jaehoon; Lee, Joonkyung; et al. (2024)
Forum of Mathematics, Sigma
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 n0 such that the following holds. Every n-vertex Steiner triple system contains all hypertrees with at most (1−μ)n vertices whenever n≥n0 . We prove this conjecture.
Tight General Bounds for the Extremal Numbers of 0-1 Matrices
Janzer, Barnabas; Janzer, Oliver; Magnan, Van; et al. (2024)
International Mathematics Research Notices
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 resulting matrix is A. The extremal number of A, denoted ex(n, A), is the maximum number of 1-entries that an n × n zero-one matrix can have without containing A. The systematic study of this function for various patterns A goes back to the work of Füredi and Hajnal from 1992, and the field has many connections to other areas of mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices, but very little is known about the general case (i.e., the case where A is not necessarily acyclic). We prove the first asymptotically tight general result by showing that if A has at most t 1-entries in every row, then ex(n, A) ≤ n^(2−1/t+o(1)). This verifies a conjecture of Methuku and Tomon. Our result also provides the first tight general bound for the extremal number of vertex- ordered graphs with interval chromatic number 2, generalizing a celebrated result of Füredi and Alon, Krivelevich, and Sudakov about the (unordered) extremal number of bipartite graphs with maximum degree t in one of the vertex classes.
Power saving for the Brown-Erdős-Sós problem
Janzer, Oliver; Methuku, Abhishek; Milojević, Aleksa; et al. (2025)
Discrete Analysis
Tight bounds for intersection‐reverse sequences, edge‐ordered graphs, and applications
Janzer, Barnabas; Janzer, Oliver; Methuku, Abhishek; et al. (2025)
Journal of the London Mathematical Society
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$ and $A^j$ appear in reversed cyclic order in $A^i$ and $A^j$, then $\sum _{i} |A^i|=O(n^{3/2}\log n)$. This result is tight up to the logarithmic factor and has since become an important tool in Discrete Geometry. In this paper, we improve this to the optimal bound $O(n^{3/2})$. In fact, we prove the following more general result. We show that if $A^1,\dots,A^n$ are linear orders on some subsets of a set of $n$ symbols such that no three symbols appear in the same order in any two distinct linear orders, then $\sum _{i} |A^i|=O(n^{3/2})$. Using this result, we resolve several open problems in Discrete Geometry and Extremal Graph Theory as follows. (i)We prove that every $n$-vertex topological graph that does not contain a self-crossing four-cycle has $O(n^{3/2})$ edges. This resolves a problem of Marcus and Tardos from 2006. (ii)We show that $n$ pseudo-circles in the plane can be cut into $O(n^{3/2})$ pseudo-segments, which, in turn, implies new bounds on the number of point-circle incidences and on other geometric problems. This goes back to a problem of Tamaki and Tokuyama from 1998 and improves several results in the area. (iii)We also prove that the edge-ordered Turán number of the four-cycle $C_4^{1243}$ is $\Theta (n^{3/2})$. This gives the first example of an edge-ordered graph whose Turán number is known to be $\Theta (n^{\alpha })$ for some $1<\alpha <2$, and answers a question of Gerbner, Methuku, Nagy, Pálvölgyi, Tardos, and Vizer. Using different methods, we determine the largest possible extremal number that an edge-ordered forest of order chromatic number two can have. Kucheriya and Tardos showed that every such graph has extremal number at most $n2^{O(\sqrt {\log n})}$, and conjectured that this can be improved to $n(\log n)^{O(1)}$. We disprove their conjecture in a strong form by showing that for every $C>0$, there exists an edge-ordered tree of order chromatic number two whose extremal number is $\Omega (n 2^{C\sqrt {\log n}})$.

Publications 1 - 6 of 6

Abhishek Methuku

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results