BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Péter Pál Pach appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
Let $ρ_k(N)$ denote the maximum size of a set $A\subseteq \{1,2,\dots,N\}$ such that no product of $k$ distinct elements of $A$ is a perfect $d$-th power. In this short note, we prove that $ρ_d(N)=\sum\limits_{k=1}^{d-1}π\left( \frac{N}{k} \right) +O_d(π(N^{1/2}))$, furthermore, for prime power $d$ and sufficiently large $N$ we have $ρ_d(N)=\sum\limits_{k=1}^{d-1}π\left( \frac{N}{k} \right)$. This answers a question of Verstraëte.
We resolve the Ramsey problem for $\{x,y,z:x+y=p(z)\}$ for all polynomials $p$ over $\mathbb{Z}$. In particular, we characterise all polynomials that are $2$-Ramsey, that is, those $p(z)$ such that any $2$-colouring of $\mathbb{N}$ contains infinitely many monochromatic solutions for $x+y=p(z)$. For polynomials that are not $2$-Ramsey, we characterise all $2$-colourings of $\mathbb{N}$ that are not $2$-Ramsey, revealing that certain divisibility barrier is the only obstruction to $2$-Ramseyness for $x+y=p(z)$.
For which values of $n$ can we color the positive integers with precisely $n$ colors in such a way that for any $a$, the numbers $a,2a,\dots,na$ all get different colors? Pach posed the question around 2008-9. Particular cases appeared in KöMaL in April 2010, and the general version appeared in May 2010 on MathOverflow, posted by Pálvölgyi. The question remains open. We discuss the known partial results and investigate a series of related matters attempting to understand the structure of these $n$-satisfactory colorings. Specifically, we show that there is an $n$-satisfactory coloring whenever there is an abelian group operation $\oplus$ on the set $\{1,2,\dots,n\}$ compatible with multiplication in the sense that whenever $i$, $j$ and $ij$ are in $\{1,\dots,n\}$, then $ij=i\oplus j$. This includes in particular the cases where $n+1$ is prime, or $2n+1$ is prime, or $n=p^2-p$ for some prime $p$, or there is a $k$ such that $q=nk+1$ is prime and $1^k,\dots,n^k$ are all distinct modulo $q$ (in which case we call $q$ a strong representative of order $n$). The colorings obtained by this process we call multiplicative. We also show that nonmultiplicative colorings exist for some values of $n$. There is an $n$-satisfactory coloring of $\mathbb Z^+$ if and only if there is such a coloring of the set $K_n$ of $n$-smooth numbers. We identify all $n$-satisfactory colorings for $n\le 5$ and all multiplicative colorings for $n\le 8$, and show that there are as many nonmultiplicative colorings of $K_n$ as there are real numbers for $n=6$ and 8. We show that if $n$ admits a strong representative $q$ then the set of such $q$ has positive natural density in the set of all primes. We show that the question of whether there is an $n$-satisfactory coloring is equivalent to a problem about tilings, and use this to give a geometric characterization of multiplicative colorings.
A set $A$ of natural numbers possesses property $\mathcal{P}_h$, if there are no distinct elements $a_0,a_1,\dots ,a_h\in A$ with $a_0$ dividing the product $a_1a_2\dots a_h$. Erdős determined the maximum size of a subset of $\{1,\ldots, n\}$ possessing property $\mathcal{P}_2$. More recently, Chan, Győri and Sárközy solved the case $h=3$, finally the general case also got resolved by Chan, the maximum size is $π(n)+Θ_h(\frac{n^{2/(h+1)}}{(\log n)^{2}})$. In this note we consider the counting version of this problem and show that the number of subsets of $\{1,\ldots, n\}$ possessing property $\mathcal{P}_h$ is $T(n)\cdot e^{Θ(n^{2/3}/\log n)}$ for a certain function $T(n)\approx (3.517\dots)^{π(n)}$. For $h>2$ we prove that the number of subsets possessing property $\mathcal{P}_h$ is $T(n)\cdot e^{\sqrt{n}(1+o(1))}$. This is a rare example in which the order of magnitude of the lower order term in the exponent is also determined.
In this paper we investigate how small the density of a multiplicative basis of order $h$ can be in $\{1,2,\dots,n\}$ and in $\mathbb{Z}^+$. Furthermore, a related problem of Erd\H os is also studied: How dense can a set of integers be, if none of them divides the product of $h$ others?
Recently it has been shown that all non-trivial closed permutation groups containing the automorphism group of the random poset are generated by two types of permutations: the first type are permutations turning the order upside down, and the second type are permutations induced by so-called rotations. In this paper we introduce rotations for finite posets, which can be seen as the poset counterpart of Seidel-switch for finite graphs. We analyze some of their combinatorial properties, and investigate in particular the question of when two finite posets are rotation-equivalent. We moreover give an explicit combinatorial construction of a rotation of the random poset whose image is again isomorphic to the random poset. As an corollary of our results on rotations of finite posets, we obtain that the group of rotating permutations of the random poset is the automorphism group of a homogeneous structure in a finite language.
We determine, up to the equivalence of first-order interdefinability, all structures which are first-order definable in the random partial order. It turns out that these structures fall into precisely five equivalence classes. We achieve this result by showing that there exist exactly five closed permutation groups which contain the automorphism group of the random partial order, and thus expose all symmetries of this structure. Our classification lines up with previous similar classifications, such as the structures definable in the random graph or the order of the rationals; it also provides further evidence for a conjecture due to Simon Thomas which states that the number of structures definable in a homogeneous structure in a finite relational language is, up to first-order interdefinability, always finite. The method we employ is based on a Ramsey-theoretic analysis of functions acting on the random partial order, which allows us to find patterns in such functions and make them accessible to finite combinatorial arguments.