About me
I am a postdoc at EPFL in the Discrete and Computational Geometry Group of János Pach. My PhD advisors were Gyula O. H. Katona and Ervin Győri.
I am interested in Extremal and Probabilistic Combinatorics (with slight emphasis on sparse graphs and hypergraphs) and its connections to other areas of mathematics such as Algebra.
-
- E-mail: [email protected]
- Curriculum vitae: CV
My papers are available on Google Scholar and arXiv.
Selected publications
Asymptotics for Turán numbers of cycles in 3-uniform linear hypergraphs (with B. Ergemlidze, E. Győri), Journal of Combinatorial Theory, Series A 163 (2019): 163-181 pdf
How large can a 3-uniform linear hypergraph be if it does not contain a (Berge) cycle of length k? If k = 3, this question is equivalent to the famous (6, 3)-problem, that was settled by Ruzsa and Szemerédi. If k = 4, we show the answer is asymptotically equal to n3/2/6, (slightly) strenghtening a theorem of Lazebnik and Verstraëte. If k = 5, we show the answer is n3/2/3√3 (asymptotically).
We also consider the same question for linear cycles (instead of Berge cycles), and show a connection between this question and the well-known problem of determining the maximum size of a graph of given girth. Using this connection, we give new constructions. Combining this with a theorem of Collier-Cartaino, Graber and Jiang, we obtain that the linear Turán number of the linear cycle of length 2k+1 is Θ(n1 + 1/k) for k = 2, 3, 4, 6.
Asymptotics for the Turán number of Berge-K2, t (with D. Gerbner, M. Vizer), To appear in Journal of Combinatorial Theory, Series B pdf
A natural generalisation of classical definitions of Berge paths and cycles is the following: Given a graph F, a hypergraph is called Berge-F if it can be obtained by replacing each edge in F by a hyperedge containing it.
In this paper, we determine (asymptotically) the maximum possible number of edges in a 3-uniform hypergraph on n vertices containing no Berge-K2, t as a subhypergraph, whenever t ≥ 7. (In a recent paper, we settle the cases t = 4, 5, 6, via two general lemmas that also imply other new results and improve several old results in this area.)
We also study the analogous question for linear hypergraphs and determine the answer when t goes to infinity – interestingly, to prove the lower bound, we use a result of Alon, Kim and Spencer on the existence of large matchings in regular 3-uniform hypergraphs. This significantly improves a result of Timmons. We also prove general upper and lower bounds for several classes of graphs improving (or reproving) results of Gerbner-Palmer, Füredi-Özkahya, Jiang-Ma.
An upper bound on the size of diamond-free families of sets (with D. Grósz, C. Tompkins), Journal of Combinatorial Theory, Series A 156 (2018): 164-194 pdf
The two-dimensional Boolean lattice is known as the diamond poset. What is the largest subset of the Boolean lattice that avoids the diamond poset? One can take two middle layers of the Boolean lattice without creating a diamond poset. It is conjectured that this is best possible (asymptotically). In this paper we prove an upper bound of 2.20711 times the size of a middle layer of the Boolean lattice. This improves the earlier bound of Kramer, Martin and Young, and is currently the best known bound.
Intersecting P-free families (with D. Gerbner, C. Tompkins), Journal of Combinatorial Theory, Series A 151 (2017): 61-83 pdf
How large can an intersecting family of subsets of {1, 2, …, n} be if it avoids a given poset P? We answer this question exactly for the butterfly poset and classify the cases of equality. Our proof uses a new generalization of the partition method of Griggs, Li and Lu. We also prove generalizations of two well-known inequalities of Bollobás and Greene, Katona and Kleitman in this case. Furthermore, we obtain a general bound on the size of a largest intersecting P-free family, which is sharp for an infinite class of posets. Finally, we give a new proof of the bound on the maximum size of an intersecting k-Sperner family and determine the cases of equality.
Forbidden hypermatrices imply general bounds on induced forbidden subposet problems (with D. Pálvölgyi), Combinatorics, Probability and Computing 26.4 (2017): 593-602 pdf
What is the maximum size of a subset of the Boolean lattice that does not contain an induced copy of a given poset P? It was conjectured by Katona and Lu, Milans that this maximum is at most a constant CP times the size of a largest layer of the Boolean lattice. 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.
On subgraphs of C2k-free graphs and a problem of Kühn and Osthus (with D. Grósz, C. Tompkins) pdf
Kühn and Osthus proved the following beautiful result: Every bipartite C2k-free graph G contains a C4-free subgraph with at least 1/(k−1) fraction of the edges of G. We give a new simple proof of this result. We also give a negative answer to their question about C2k-free graphs obtained by pasting together copies of C2l (with k > l ≥ 3).
Győri et. al. showed that every C6-free graph G contains a bipartite C4-free subgraph having 3/8 fraction of the edges of G, and asked whether the fraction 3/8 is best possible. We show that it is sharp by giving a new probabilistic construction. We also study generalizations of this problem to C2k-free graphs.
