@article{MTMT:35294372, title = {On Bh[1]-sets which are asymptotic bases of order 2h}, url = {https://m2.mtmt.hu/api/publication/35294372}, author = {Kiss, Sándor and Sándor, Csaba}, doi = {10.1016/j.jnt.2024.07.006}, journal-iso = {J NUMBER THEORY}, journal = {JOURNAL OF NUMBER THEORY}, volume = {266}, unique-id = {35294372}, issn = {0022-314X}, year = {2025}, eissn = {1096-1658}, pages = {350-376} } @article{MTMT:35492943, title = {Corrigendum to “An algorithm to find maximum area polygons circumscribed about a convex polygon” [Discrete Appl. Math. 255 (2019) 98–108]}, url = {https://m2.mtmt.hu/api/publication/35492943}, author = {Ausserhofer, Markus and Dann, Susanna and Lángi, Zsolt and Tóth, Géza}, doi = {10.1016/j.dam.2024.04.013}, journal-iso = {DISCRETE APPL MATH}, journal = {DISCRETE APPLIED MATHEMATICS}, volume = {353}, unique-id = {35492943}, issn = {0166-218X}, year = {2024}, eissn = {1872-6771}, pages = {222-226}, orcid-numbers = {Lángi, Zsolt/0000-0002-5999-5343} } @misc{MTMT:35297550, title = {From clonal interference to Poissonian interacting trajectories}, url = {https://m2.mtmt.hu/api/publication/35297550}, author = {Hermann, Felix and González, Casanova Adrián and dos, Santos Renato Soares and Tóbiás, András József and Wakolbinger, Anton}, unique-id = {35297550}, year = {2024}, pages = {1-38} } @article{MTMT:35192732, title = {An Efficient Algorithm to Compute the Toughness in Graphs with Bounded Treewidth}, url = {https://m2.mtmt.hu/api/publication/35192732}, author = {Katona, Gyula Y. and Khan, Humara}, doi = {10.1007/s00373-024-02828-y}, journal-iso = {GRAPH COMBINATOR}, journal = {GRAPHS AND COMBINATORICS}, volume = {40}, unique-id = {35192732}, issn = {0911-0119}, abstract = {Let t be a positive real number. A graph is called t-tough if the removal of any vertex set S that disconnects the graph leaves at most |S|/t components. The toughness of a graph is the largest t for which the graph is t-tough. We prove that toughness is fixed-parameter tractable parameterized with the treewidth. More precisely, we give an algorithm to compute the toughness of a graph G with running time O(|V(G)|3·tw(G)2tw(G)) where tw(G) is the treewidth. If the treewidth is bounded by a constant, then this is a polynomial algorithm. © The Author(s) 2024.}, keywords = {Treewidth; 05C85; Fixed-parameter tractable; 05C40; 68Q25; 68R10; Tougness}, year = {2024}, eissn = {1435-5914}, orcid-numbers = {Katona, Gyula Y./0000-0002-5119-8681} } @article{MTMT:35191119, title = {The Core of Housing Markets from an Agent’s Perspective. Is It Worth Sprucing up Your Home?}, url = {https://m2.mtmt.hu/api/publication/35191119}, author = {Schlotter, Ildikó Anna and Biró, Péter and Fleiner, Tamás}, doi = {10.1287/moor.2023.0092}, journal-iso = {MATH OPER RES}, journal = {MATHEMATICS OF OPERATIONS RESEARCH}, unique-id = {35191119}, issn = {0364-765X}, abstract = {We study housing markets as introduced by Shapley and Scarf. We investigate the computational complexity of various questions regarding the situation of an agent a in a housing market H: we show that it is [Formula: see text]-hard to find an allocation in the core of H in which (i) a receives a certain house, (ii) a does not receive a certain house, or (iii) a receives a house other than a’s own. We prove that the core of housing markets respects improvement in the following sense: given an allocation in the core of H in which agent a receives a house h, if the value of the house owned by a increases, then the resulting housing market admits an allocation in its core in which a receives either h or a house that a prefers to h; moreover, such an allocation can be found efficiently. We further show an analogous result in the Stable Roommates setting by proving that stable matchings in a one-sided market also respect improvement.}, year = {2024}, eissn = {1526-5471} } @article{MTMT:35159616, title = {Stability from graph symmetrization arguments in generalized Turán problems}, url = {https://m2.mtmt.hu/api/publication/35159616}, author = {Gerbner, Dániel and Hama Karim, Hilal}, doi = {10.1002/jgt.23151}, journal-iso = {J GRAPH THEOR}, journal = {JOURNAL OF GRAPH THEORY}, volume = {107}, unique-id = {35159616}, issn = {0364-9024}, abstract = {Given graphs (Formula presented.) and (Formula presented.), (Formula presented.) denotes the largest number of copies of (Formula presented.) in (Formula presented.) -free (Formula presented.) -vertex graphs. Let (Formula presented.). We say that (Formula presented.) is F-Turán-stable if the following holds. For any (Formula presented.) there exists (Formula presented.) such that if an (Formula presented.) -vertex (Formula presented.) -free graph (Formula presented.) contains at least (Formula presented.) copies of (Formula presented.), then the edit distance of (Formula presented.) and the (Formula presented.) -partite Turán graph is at most (Formula presented.). We say that (Formula presented.) is weakly F-Turán-stable if the same holds with the Turán graph replaced by any complete (Formula presented.) -partite graph (Formula presented.). It is known that such stability implies exact results in several cases. We show that complete multipartite graphs with chromatic number at most (Formula presented.) are weakly (Formula presented.) -Turán-stable. Partly answering a question of Morrison, Nir, Norin, Rzażewski, and Wesolek positively, we show that for every graph (Formula presented.), if (Formula presented.) is large enough, then (Formula presented.) is (Formula presented.) -Turán-stable. Finally, we prove that if (Formula presented.) is bipartite, then it is weakly (Formula presented.) -Turán-stable for (Formula presented.) large enough. © 2024 Wiley Periodicals LLC.}, keywords = {STABILITY; Graph theory; Chromatic number; Symmetrization; Symmetrization; Free graphs; Partite graphs; generalized Turan problem; exact results; Complete multipartite graph; Edit distance; Generalized Turan problems; Vertex graphs}, year = {2024}, eissn = {1097-0118}, pages = {681-692} } @article{MTMT:35159588, title = {Multiplicative complements, II.}, url = {https://m2.mtmt.hu/api/publication/35159588}, author = {Kocsis, Anett and Matolcsi, Dávid and Sándor, Csaba and Tőtős, György}, doi = {10.1016/j.jnt.2024.05.014}, journal-iso = {J NUMBER THEORY}, journal = {JOURNAL OF NUMBER THEORY}, volume = {265}, unique-id = {35159588}, issn = {0022-314X}, abstract = {In this paper we prove that if A and B are infinite subsets of positive integers such that every positive integer n can be written as n=ab, a∈A, b∈B, then [Formula presented]. We present some tight density bounds in connection with multiplicative complements. © 2024 Elsevier Inc.}, keywords = {COUNTING FUNCTION; Additive complements}, year = {2024}, eissn = {1096-1658}, pages = {1-19} } @article{MTMT:35148907, title = {The Robust Chromatic Number of Graphs}, url = {https://m2.mtmt.hu/api/publication/35148907}, author = {Bacsó, Gábor and Patkós, Balázs and Tuza, Zsolt and Vizer, Máté}, doi = {10.1007/s00373-024-02817-1}, journal-iso = {GRAPH COMBINATOR}, journal = {GRAPHS AND COMBINATORICS}, volume = {40}, unique-id = {35148907}, issn = {0911-0119}, abstract = {A 1-removed subgraph G_f G f of a graph G=(V,E) G = ( V , E ) is obtained by (i) selecting at most one edge f ( v ) for each vertex v\in V v ∈ V , such that v\in f(v)\in E v ∈ f ( v ) ∈ E (the mapping f:V\rightarrow E \cup \{\varnothing \} f : V → E ∪ { ∅ } is allowed to be non-injective), and (ii) deleting all the selected edges f ( v ) from the edge set E of G .}, year = {2024}, eissn = {1435-5914}, orcid-numbers = {Patkós, Balázs/0000-0002-1651-2487} } @article{MTMT:35085705, title = {Restricted optimal pebbling is NP-hard}, url = {https://m2.mtmt.hu/api/publication/35085705}, author = {Papp, László F.}, doi = {10.1016/j.dam.2024.06.013}, journal-iso = {DISCRETE APPL MATH}, journal = {DISCRETE APPLIED MATHEMATICS}, volume = {357}, unique-id = {35085705}, issn = {0166-218X}, abstract = {Consider a distribution of pebbles on a graph. A pebbling move removes two pebbles from a vertex and place one at an adjacent vertex. A vertex is reachable under a pebble distribution if it has a pebble after the application of a sequence of pebbling moves. A pebble distribution is solvable if each vertex is reachable under it. The size of a pebble distribution is the total number of pebbles. The optimal pebbling number π∗(G) is the size of the smallest solvable distribution. A t-restricted pebble distribution places at most t pebbles at each vertex. The t-restricted optimal pebbling number πt∗(G) is the size of the smallest solvable t-restricted pebble distribution. We show that deciding whether π2∗(G)≤k is NP-complete. We prove that πt∗(G)=π∗(G) if δ(G)≥[Formula presented]−1 and we show infinitely many graphs which satisfies δ(H)≈[Formula presented]|V(H)| but πt∗(H)≠π∗(H), where δ denotes the minimum degree. © 2024 The Author}, keywords = {Optimization; NP-hard; Pebbling numbers; Adjacent vertices; NP Complete; Minimum degree; Optimal pebbling; Optimal pebbling; Graph pebbling; Graph pebbling; Restricted optimal pebbling; Restricted optimal pebbling}, year = {2024}, eissn = {1872-6771}, pages = {258-263} } @article{MTMT:35083842, title = {Parameterized complexity of candidate nomination for elections based on positional scoring rules}, url = {https://m2.mtmt.hu/api/publication/35083842}, author = {Schlotter, Ildikó Anna and Cechlárová, Katarína and Trellová, Diana}, doi = {10.1007/s10458-024-09658-5}, journal-iso = {AUTON AGENTS MULTI-AG}, journal = {AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS}, volume = {38}, unique-id = {35083842}, issn = {1387-2532}, abstract = {Consider elections where the set of candidates is partitioned into parties, and each party must nominate exactly one candidate. The P ossible P resident problem asks whether some candidate of a given party can become the unique winner of the election for some nominations from other parties. We perform a multivariate computational complexity analysis of P ossible P resident for several classes of elections based on positional scoring rules. We consider the following parameters: the size of the largest party, the number of parties, the number of voters and the number of voter types. We provide a complete computational map of P ossible P resident in the sense that for each choice of the four possible parameters as (i) constant, (ii) parameter, or (iii) unbounded, we classify the computational complexity of the resulting problem as either polynomial-time solvable or -complete, and for parameterized versions as either fixed-parameter tractable or [1]-hard with respect to the parameters considered.}, year = {2024}, eissn = {1573-7454} }