Zoltán Lóránt Nagy
Benedek Kovács
Dávid Szabó
| Title, Year | Link | Description |
|---|---|---|
| Dániel T. Nagy, Zoltán Lóránt Nagy, Russ Woodroofe, The extensible No-Three-In-Line problem , 2022. | European Journal of Combinatorics ,114, December 2023, 103796 pdf | The classical No-Three-In-Line problem seeks the maximum number of points that may be selected from an n× n grid while avoiding collinear triples. Easy to see that roughly n points can be picked easily as p points is easy to be picked in a p×p grid for every prime p. On the other hand, 2n is a natural upper bound. But what is the relation of these constructions for different values of n? Can we come up with a collinear triple free set in Z×Z such that it contains linearly many points in EVERY subgrid of form [1,n]×[1,n]? The conjecture of Erde states that the answer is negative. We showed that on the other hand, we can obtain a set which has almost linear size in every [1,n]×[1,n] subgrid. |
| Benedek Kovács, Zoltán Lóránt Nagy, Multicolor Turán numbers II. - a generalization of the Ruzsa-Szemerédi theorem and new results on cliques and odd cycles, (2022) |
ArXiv link | Erdős and Turán conjectured ('36) that every set of integers, having positive natural density contains a k-term arithmetic progression for every k.
This was proven by Roth for k=3 ('53) and later, famously by Szemerédi in general ('75). Ruzsa and Szemerédi proved an ingenious connection to a graph theoretic problem,
the so-called (6,3) problem (See e.g. here, Thm17.) Using the regularity lemma they deduce that if an edge set of a graph consists of the edges of distinct triangles s.t. every edge is in a single triangle, then the number of triangles is subquadratic. To rephrase the condition, you may want to pack triangles with distinct colors but a multicolor triangle or triangles sharing an edge are forbidden.
This statement cannot be improved by much, since Behrend's construction provides n^2*exp(-O(n^0.5)) triangles. In this paper we provide a far-reaching generalisation for two integer parameters k, t>2, where we pack cliques of given size K_k, and want to avoid multicolor cliques of given size. or cliques sharing edges. It turns out that whenever k=t or k>t, we have again a subquadratic bound with a similarly almost matching "Behrend-type" lower bound while for k< t, the order of magnitude of the number of cliques is quadratic. (Well this follows from an earlier paper. ) Moreover, this can be stated as a generalisation of the celebrated Erdős-Stone-Simonovits theorem. In the spirit of Erdős' pentagon conjecture, we asymptotically resolve the case when we pack pentagons and want to avoid multicolor triangles. This was the "first" non-resolved case in the quadratic case. |
| Benedek Kovács, Zoltán Lóránt Nagy, Avoiding intersections of given size in finite affine spaces AG(n,2) , (2023) |
ArXiv link | We study the set of intersection sizes of a k-dimensional affine subspace and a point set
of size m ∈ [0, 2^n] of the n-dimensional binary affine space AG(n,2). Following the theme
of Erdős, Füredi, Rothschild and T. Sós, we partially determine which local densities in k-dimensional affine subspaces are unavoidable in all m-element point sets in the n-dimensional
affine space. We also show constructions of point sets for which the intersection sizes with k-dimensional affine subspaces takes values from a set of a small size compared to 2^k. These are built up from affine subspaces and so-called subspace evasive sets. Meanwhile, we improve the best known upper bounds on subspace evasive sets and apply results concerning the canonical signed-digit (CSD) representation of numbers. |
| Zsolt Baja, Dániel Dobák, Benedek Kovács, Péter Pál Pach, Donát Pigler, Towards characterizing the 2-Ramsey equations of the form ax+by=p(z), (2022) | Discrete Mathematics, 346(5), May 2023, 113324 link to paper |
Ramsey theory searches for monochromatic patterns in finite colourings of the positive integers. It dates back to the famous theorem of Schur (1916), stating that any finite colouring of Z^+ contains a monochromatic solution to x+y=z. Another classical example is van der Waerden’s theorem (1927). We investigate the polynomial version of Schur’s theorem; the main question is: given an equation ax+by=p(z) with positive integers a, b and a polynomial p with integer coefficients, is it true that any k-colouring of Z^+ contains a monochromatic solution? If so, we say that the equation is k-Ramsey. Liu, Sándor and Pach (2022) have completely resolved the Ramsey problem for the case x+y=p(z), showing that this equation is 2-Ramsey unless colouring the integers according to their parity avoids monochromatic solutions. In our paper, we show that a certain set of technical assumptions is sufficient for 2-Ramseyness of ax+by=p(z), entailing the 2-Ramseyness of several notable cases, such as the equations ax+y=z^n for arbitrary integers a>=1 and n>=2, and also ax+by=p(z) where a and b are coprime positive integers, and p is a polynomial with integer coefficients of degree at least 2 and a positive leading coefficient, having no constant term but a nonzero linear term. |
| Christian Elsholtz, Jakob Führer, Erik Füredi, Benedek Kovács, Péter Pál Pach, Dániel Simon, Nóra Velich, Maximal line-free sets in F_p^n, (2023) | ArXiv link | We study the maximum cardinality of a subset of F_p^n that does not contain a full line (1-dimensional affine subspace), denoted by r_p(F_p^n). In the case p=3, this problem coincides with the well-known cap set problem, where Ellenberg and Gijswijt (2017) gave the first exponential improvement to the trivial upper bound of 3^n with r_3(F_3^n)<2.756^n. The best known lower bound is r_3(F_3^n)>2.218^n for large enough n by Tyrrell (2022). For the general case, surprisingly few results on r_p(F_p^n) are known. The trivial lower bound r_p(F_p^n)>=(p-1)^n is achieved with a hypercube of side length p-1, known to be sharp for n=2. For n=3, the best known lower bound was (p-1)^3+1 which we improve to (p-1)^3+p-o(p). The best known upper bound, by Bishnoi et al. (2023), was p^3-2p^2+1 which we improve to p^3-2p^2-(sqrt(2)-1)p+o(p). |
| Benedek Kovács, Finding pairwise disjoint vector pairs in F_2^n with a prescribed sequence of differences, (2023) | European Conference on Combinatorics, Graph Theory and Applications, No. 12, August 2023 extended abstract |
Balister, Győri and Schelp conjectured (2008) that F_2^n can always be partitioned into disjoint pairs having a prescribed multiset of differences, given the trivial requirement that the differences sum to zero. They have shown the conjecture in the case when half of the differences are all equal and the rest appear in equal-valued pairs. An analogous question in F_p (called „seating couples around the king’s table”) was resolved by Preissmann and Mischler in 2009. In this extended abstract for the Eurocomb’23 conference, we outline a proof of Balister, Győri, and Schelp’s conjecture for the case when there are at most n-2log(n)-1 distinct values among the given differences, and also for the case when at least a fraction 28/29 of the differences are all equal. |
| János Barát, Andrzej Grzesik, Attila Jung, Zoltán Lóránt
Nagy, Dömötör Pálvölgyi, The double Hall property and cycle covers in bipartite graphs, (2023) |
ArXiv link | In a graph G, the 2-neighborhood of a vertex set X consists of all vertices having at least 2 neighbors in X. A bipartite graph G(A,B) satisfies the double Hall property if |A|>1, and every subset X of A, of size at least 2 has a 2-neighborhood of size at least |X|. Salia conjectured that any bipartite graph G(A,B) satisfying the double Hall property contains a cycle covering A. Here, we prove the existence of a 2-factor covering A in any bipartite graph G(A,B) satisfying the double Hall property. We also show Salia's conjecture for graphs with restricted degrees of vertices in B. Additionally, we prove a lower bound on the number of edges in a graph satisfying the double Hall property, and the bound is sharp up to a constant factor. |
| Benedek Kovács, Finding a perfect matching of F_2^n with prescribed differences, (2023) | ArXiv link | We consider the following question by Balister, Győri and Schelp: given 2^(n-1) nonzero vectors in F_2^n with zero sum, is it always possible to partition the elements of F_2^n into pairs such that the difference between the two elements of the i-th pair is equal to the i-th given vector for every i? An analogous question in F_p, which is a case of the so-called "seating couples" problem, has been resolved by Preissmann and Mischler in 2009. In this paper, we prove the conjecture in F_2^n in the case when the number of distinct values among the given difference vectors is at most n-2log(n)-1, and also in the case when at least a fraction 1/2+epsilon of the given vectors are equal (for all epsilon>0 and n sufficiently large based on epsilon). |
| Gergely Kiss, Ádám Markó, Zoltán Lóránt
Nagy, Gábor Somlai, On polynomials of small range sum (2023) | ArXiv link | What can we say about the degree of a polynomial over F_p, if we know that its range sum, i.e., if we evaluate and add up F(x) - as pozitive integer values - for all x in F_p is small? If the range sum is below p, the problem is trivial, the degree is determined by the sum. If the sum equals p, we show the only polynomials where the degree can be equal to (p-1)/2, which is the smallest possible degree. From this, we could derive the famous Lovász-Schrijver characterisation result on determined directions of AG(2,p). |
| Bence Csajbók, Z.L Nagy Complete 3-term arithmetic progression free sets of small size in vector spaces and other abelian groups (2024) | ArXiv link | Let G denote an Abelian group, written additively. A 3-term arithmetic progression of G, 3-AP for short, is a set of three distinct elements of G of the form g, g+d, g+2d, for some g,d?G. A set S?G is called 3-AP free if it does not contain a 3-AP. S is called complete 3-AP free if it is 3-AP free and the addition of any further element would violate the 3-AP free property. In case S is not necessarily 3-AP free but for each x?G\S there is a 3-AP of G consisting of x and two elements of S, we call S saturating w.r.t. 3-APs. A classical problem in additive combinatorics is to determine the maximal size of a 3-AP free set. A classical problem in finite geometry and coding theory is to find the minimal size of a complete cap in affine spaces, where a cap is a point set without a collinear triplet and in Fn3 caps and 3-AP free sets are the same objects. In this paper we determine the minimum size of complete 3-AP free sets and 3-AP saturating sets for several families of vector spaces and cyclic groups, up to a small multiplicative constant factor. |
.
Extremal graph theory
Conjecture: ex(n, F)=O(n^{2-1/r}).
Some known results: Confirmed for bipartite graphs G(A,B) where deg(v)≤ r (Füredi, '91)Conjecture (Grzesik,Janzer, Nagy): For any 0< Α< 1$ and any graph F, if ex(n, F)= O(n^{2- Α}), then ex(n,F[r])= O(n^{2- Α/r}}). .
Some known results: Confirmed for r-blownups of any tree (Grzesik, Janzer, ZL Nagy, '22, JCTB )Problem
When does the coloring have an importance? When does it hold that the extremal construction is an F-packing of the ordinary G-extremal graph?Conjecture: G contains a relatively small k-core, i.e., a subgraph G' of G where |G'|/|G| <1/k, provided that n is large enough.
Finite geometry, incidence structures
Conjecture: The lines of AG(3,p) can be covered by (2.5+o(1))p^2 points.
Some known results: In 2-D, 2p-1 points are needed, as shown by Jamison, via polynomial methods (basically, via the Combinatorial Nullstellensatz)
Blog of Anurag Bishnoi - on extremal graph related to finite geometries, extremal combinatorics problems and more
Blog of Sam Mattheus - on applications of finite geometries, and more
Page of Ferdinando Zullo - on finite geometry
Blog of Ferdinand Ihringer - yet another combinatorial blog, mostly in algebraic combinatorics
Blog of Gil Kalai - on combinatorial problems and other stuff
Blog of Tim Gowers
Blog of Terry Tao - on various fields of maths