András Pongrácz
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Research Subjects
András Pongrácz has a total of 13 co-authors. Here are the top co-authors by number of shared publications:
- Manuel Bodirsky
Institut für Algebra, TU Dresden, Dresden, Germany
7 shared publications - Michael Pinsker
TU Wien, Austria
7 shared publications - Csaba Szabó
Department of Algebra and Number Theory, Eötvös Loránd University, Budapest, Hungary
2 shared publications - Kamilla Kátai-Urbán
Bolyai Institute, University of Szeged, Szeged, Hungary
2 shared publications - Barnaby Martin
Durham University, Durham, UK
1 shared publication - Csaba Vincze
Institute of Mathematics, University of Debrecen, Debrecen, Hungary
1 shared publication
Latest Publications
- Open Access
- 15 May 2026
- Published by Elsevier in Discrete Mathematics
- Vol. 349 (10)
Finding cliques and dense subgraphs using edge queries
- 15 May 2026
- Published by Elsevier in Discrete Mathematics
- Vol. 349 (10)
Open AccessFinding cliques and dense subgraphs using edge queries
- 22 May 2025
- Published by Wiley in Journal of the London Mathematical Society
- Vol. 111 (5)
On Diophantine graphs
Diophantine tuples are of ancient and modern interest, with a huge literature. In this paper, we study Diophantine graphs, that is, finite graphs whose vertices are distinct positive integers, and two vertices are linked by an edge if and only if their product increased by one is a square. We provide various results for Diophantine graphs, including extendability properties, lower‐ and upper bounds for the maximum number of edges and chromatic numbers.
- 22 May 2025
- Published by Wiley in Journal of the London Mathematical Society
- Vol. 111 (5)
On Diophantine graphs
Diophantine tuples are of ancient and modern interest, with a huge literature. In this paper, we study Diophantine graphs, that is, finite graphs whose vertices are distinct positive integers, and two vertices are linked by an edge if and only if their product increased by one is a square. We provide various results for Diophantine graphs, including extendability properties, lower‐ and upper bounds for the maximum number of edges and chromatic numbers.
- Open Access
On Diophantine graphs
Diophantine tuples are of ancient and modern interest, with a huge literature. In this paper we study Diophantine graphs, i.e., finite graphs whose vertices are distinct positive integers, and two vertices are linked by an edge if and only if their product increased by one is a square. We provide various results for Diophantine graphs, including extendability properties, lower- and upper bounds for the maximum number of edges and chromatic numbers.
Open AccessOn Diophantine graphs
Diophantine tuples are of ancient and modern interest, with a huge literature. In this paper we study Diophantine graphs, i.e., finite graphs whose vertices are distinct positive integers, and two vertices are linked by an edge if and only if their product increased by one is a square. We provide various results for Diophantine graphs, including extendability properties, lower- and upper bounds for the maximum number of edges and chromatic numbers.
- Open Access
- 8 April 2024
- Published by Springer Nature in Acta Scientiarum Mathematicarum
- Vol. 90 (1-2) , 41-51
Voting protocols on the star graph
Let $$G=(V,E)$$ be a finite graph together with an initial assignment $$V\rightarrow \{0,1\}$$ that represents the opinion of each vertex. Then discordant push voting is a discrete, non-deterministic protocol that alters the opinion of one vertex at a time until a consensus is reached. More precisely, at each round a discordant vertex u (i.e., one that has a neighbor with a different opinion) is chosen uniformly at random, and then we choose a neighbor v with different vote uniformly at random, and force v to change its opinion to that of u. In case of the discordant pull protocol we simply choose a discordant vertex uniformly at random and change its opinion. In this paper, we give asymptotically sharp estimations for the worst expected runtime of the discordant push and pull protocols on the star graph.- 8 April 2024
- Published by Springer Nature in Acta Scientiarum Mathematicarum
- Vol. 90 (1-2) , 41-51
Open AccessVoting protocols on the star graph
Let $$G=(V,E)$$ be a finite graph together with an initial assignment $$V\rightarrow \{0,1\}$$ that represents the opinion of each vertex. Then discordant push voting is a discrete, non-deterministic protocol that alters the opinion of one vertex at a time until a consensus is reached. More precisely, at each round a discordant vertex u (i.e., one that has a neighbor with a different opinion) is chosen uniformly at random, and then we choose a neighbor v with different vote uniformly at random, and force v to change its opinion to that of u. In case of the discordant pull protocol we simply choose a discordant vertex uniformly at random and change its opinion. In this paper, we give asymptotically sharp estimations for the worst expected runtime of the discordant push and pull protocols on the star graph. - 1 January 2022
- Published by Universitat Autonoma de Barcelona in Publicacions Matemàtiques
- Vol. 66 (1) , 57-75
Extremal solutions of an inequality concerning supports of permutation groups and punctured Hadamard codes
- 1 January 2022
- Published by Universitat Autonoma de Barcelona in Publicacions Matemàtiques
- Vol. 66 (1) , 57-75
Extremal solutions of an inequality concerning supports of permutation groups and punctured Hadamard codes
- Open Access
Constraint satisfaction problems for reducts of homogeneous graphs
For $n\geq 3$, let $(H_n, E)$ denote the $n$-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on $n$ vertices. We show that for all structures $\Gamma$ with domain $H_n$ whose relations are first-order definable in $(H_n,E)$ the constraint satisfaction problem for $\Gamma$ is either in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete.Open AccessConstraint satisfaction problems for reducts of homogeneous graphs
For $n\geq 3$, let $(H_n, E)$ denote the $n$-th Henson graph, i.e., the unique countable homogeneous graph with exactly those finite graphs as induced subgraphs that do not embed the complete graph on $n$ vertices. We show that for all structures $\Gamma$ with domain $H_n$ whose relations are first-order definable in $(H_n,E)$ the constraint satisfaction problem for $\Gamma$ is either in P or is NP-complete. We moreover show a similar complexity dichotomy for all structures whose relations are first-order definable in a homogeneous graph whose reflexive closure is an equivalence relation. Together with earlier results, in particular for the random graph, this completes the complexity classification of constraint satisfaction problems of structures first-order definable in countably infinite homogeneous graphs: all such problems are either in P or NP-complete. - Open Access
Projective clone homomorphisms
It is known that a countable $\omega$-categorical structure interprets all finite structures primitively positively if and only if its polymorphism clone maps to the clone of projections on a two-element set via a continuous clone homomorphism. We investigate the relationship between the existence of a clone homomorphism to the projection clone, and the existence of such a homomorphism which is continuous and thus meets the above criterion.
Open AccessProjective clone homomorphisms
It is known that a countable $\omega$-categorical structure interprets all finite structures primitively positively if and only if its polymorphism clone maps to the clone of projections on a two-element set via a continuous clone homomorphism. We investigate the relationship between the existence of a clone homomorphism to the projection clone, and the existence of such a homomorphism which is continuous and thus meets the above criterion.
- Open Access
- 18 December 2020
- Published by Springer Nature in Journal of Mathematical Imaging and Vision
- Vol. 63 (4) , 443-456
On the Reconstruction of the Center of a Projection by Distances and Incidence Relations
Up to an orientation-preserving symmetry, photographic images are produced by a central projection of a restricted area in the space into the image plane. To obtain reliable information about physical objects and the environment through the process of recording is the basic problem of photogrammetry. We present a reconstruction process based on distances from the center of projection and incidence relations among the points to be projected. For any triplet of collinear points in the space, we construct a surface of revolution containing the center of the projection. It is a generalized conic that can be represented as an algebraic surface. The rotational symmetry allows us to restrict the investigations to the defining polynomial of the profile curve in the image plane. An equivalent condition for the boundedness is given in terms of the input parameters, and it is shown that the defining polynomial of the profile curve is irreducible.
- 18 December 2020
- Published by Springer Nature in Journal of Mathematical Imaging and Vision
- Vol. 63 (4) , 443-456
Open AccessOn the Reconstruction of the Center of a Projection by Distances and Incidence Relations
Up to an orientation-preserving symmetry, photographic images are produced by a central projection of a restricted area in the space into the image plane. To obtain reliable information about physical objects and the environment through the process of recording is the basic problem of photogrammetry. We present a reconstruction process based on distances from the center of projection and incidence relations among the points to be projected. For any triplet of collinear points in the space, we construct a surface of revolution containing the center of the projection. It is a generalized conic that can be represented as an algebraic surface. The rotational symmetry allows us to restrict the investigations to the defining polynomial of the profile curve in the image plane. An equivalent condition for the boundedness is given in terms of the input parameters, and it is shown that the defining polynomial of the profile curve is irreducible.
- 1 January 2020
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 34 (4) , 2300-2317
Binary Linear Codes with Near-Extremal Maximum Distance
Let $C$ denote a binary linear code with length $n$ all of whose coordinates are essential; i.e., for each coordinate there is a codeword that is not zero in that position. Then the maximum distanc...- 1 January 2020
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Discrete Mathematics
- Vol. 34 (4) , 2300-2317
Binary Linear Codes with Near-Extremal Maximum Distance
Let $C$ denote a binary linear code with length $n$ all of whose coordinates are essential; i.e., for each coordinate there is a codeword that is not zero in that position. Then the maximum distanc...- Open Access
- 22 May 2019
- Published by Springer Nature in Algebra universalis
- Vol. 80 (2) , 22
The fine- and generative spectra of varieties of monounary algebras
- 22 May 2019
- Published by Springer Nature in Algebra universalis
- Vol. 80 (2) , 22
Open AccessThe fine- and generative spectra of varieties of monounary algebras