About me
I am currently a postdoc at EPFL working in the Combinatorial Geometry group of Janos Pach. I received my PhD from the University of Cambridge, where I did research in combinatorics and graph theory under the supervision of Bela Bollobas.
I am interested in all sorts of problems in combinatorics, with slight emphasis on partially ordered sets, graph theory and combinatorial geometry.
e-mail: [email protected]
office: MA C1 557
My latest publications are available on arXiv
Selected publications
Packing the Boolean lattice with copies of a poset pdf
This paper is the conclusion of a series of three papers, in which we prove the following conjecture of Lonc from 1991. If P is a poset, then the Boolean lattice 2[n] can be almost partitioned into copies of P for n sufficiently large: there exists a packing of copies of P that might not cover the minimum and maximum of 2[n], and at most |P|-1 other elements, due to divisibility.
Forbidden induced subposets of given height, Journal of Combinatorial Theory, Series A 161 (2019): 537-562. pdf
How large can be a subfamily of 2[n] that avoids a given poset P. It was proved recently by Methuku and Palvolgyi that there exists a constant C such that the size of such a family is bounded by
C2nn-1/2, which is the right order of magnitude as witnessed by the largest antichain of 2[n]. However, we do not know much about the relation between P and the constant C. In this paper, we show that as long as the height of P is bounded, C is at most a polynomial in |P|.
The proof involves a chain partitioning technique, which turns out to be useful in other extremal set theoretic problems as well.
On the size of k-cross-free families (with A. Kupavskii and J. Pach), Combinatorica (2018) https://doi.org/10.1007/s00493-017-3792-8 pdf
Two subsets A,B of an n element set X are crossing if all four sets in the Venn-diagram of A and B are nonempty. The following simple question of Karzanov and Lomonosov remains open since 1979: how large can be a family of subsets of X without k pairwise crossing sets. The bound
O(n log n) is easy to prove and remained the best known upper bound. In this paper, we improve it to O(n log* n).
The poset on connected graphs is Sperner (with S.G.Z. Smith), Journal of Combinatorial Theory, Series A 150 (2017): 162-181. pdf
The well known theorem of Sperner states that the largest antichain in the Boolean lattice 2[n] is the family of all sets of size n/2. Katona asked the following beautiful question: does a similar statement hold for the family of connected graphs? Consider the family of connected graphs on some n element set X. There is a natural poset structure on this family, given by the subgraph relation. Answering the question of Katona, we show that the largest antichain in this family is a family of connected graphs having the same number of edges.
The multiplication table problem for bipartite graphs (with B. P. Narayanan, J. Sahasrabudhe), Combinatorica 37 (5) (2017): 991-1010. pdf
The multiplication table problem of Erdos asks for the size of the set [n].[n]={ab:a,b<n}. The elements of this set are precisely those numbers that appear as the number of edges of an induced subgraph of the complete bipartite graph Kn,n. We consider the following question: if G is a bipartite graph on m edges, how many different edge numbers do its induced subgraphs realize. We show that essentially the complete bipartite graph produces the least number of edges. More precisely, we show that every biparite graph on m edges realizes at least m1-o(1) different edge numbers.
