TY - JOUR AU - Kiss, Sándor AU - Sándor, Csaba TI - On Bh[1]-sets which are asymptotic bases of order 2h JF - JOURNAL OF NUMBER THEORY J2 - J NUMBER THEORY VL - 266 PY - 2025 SP - 350 EP - 376 PG - 27 SN - 0022-314X DO - 10.1016/j.jnt.2024.07.006 UR - https://m2.mtmt.hu/api/publication/35294372 ID - 35294372 N1 - Department of Algebra and Geometry, Institute of Mathematics, Budapest University of Technology and Economics, Műegyetem rkp. 3., Budapest, H-1111, Hungary HUN-REN-BME Stochastics Research Group, Műegyetem rkp. 3., Budapest, H-1111, Hungary Department of Stochastics, Institute of Mathematics, Budapest University of Technology and Economics, Műegyetem rkp. 3., Budapest, H-1111, Hungary Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Műegyetem rkp. 3., Budapest, H-1111, Hungary MTA-BME Lendület Arithmetic Combinatorics Research Group, Műegyetem rkp. 3., Budapest, H-1111, Hungary Export Date: 16 September 2024 CODEN: JNUTA Correspondence Address: Kiss, S.Z.; Department of Algebra and Geometry, Műegyetem rkp. 3., Hungary; email: ksandor@math.bme.hu LA - English DB - MTMT ER - TY - JOUR AU - Ausserhofer, Markus AU - Dann, Susanna AU - Lángi, Zsolt AU - Tóth, Géza TI - Corrigendum to “An algorithm to find maximum area polygons circumscribed about a convex polygon” [Discrete Appl. Math. 255 (2019) 98–108] JF - DISCRETE APPLIED MATHEMATICS J2 - DISCRETE APPL MATH VL - 353 PY - 2024 SP - 222 EP - 226 PG - 5 SN - 0166-218X DO - 10.1016/j.dam.2024.04.013 UR - https://m2.mtmt.hu/api/publication/35492943 ID - 35492943 N1 - Refers to “An algorithm to find maximum area polygons circumscribed about a convex polygon” [Discrete Appl. Math. 255 (2019) 98–108] (https://doi.org/10.1016/j.dam.2018.08.017) [30339321] Funding text: We express our sincere gratitude to Nicolas Bonneel, who directed our attention to the contradiction between the result of Zaremba in [3] and our result in [1] . LA - English DB - MTMT ER - TY - GEN AU - Hermann, Felix AU - González, Casanova Adrián AU - dos, Santos Renato Soares AU - Tóbiás, András József AU - Wakolbinger, Anton TI - From clonal interference to Poissonian interacting trajectories PY - 2024 SP - 1 EP - 38 PG - 38 UR - https://m2.mtmt.hu/api/publication/35297550 ID - 35297550 N1 - https://doi.org/10.48550/arXiv.2407.00793 LA - English DB - MTMT ER - TY - JOUR AU - Katona, Gyula Y. AU - Khan, Humara TI - An Efficient Algorithm to Compute the Toughness in Graphs with Bounded Treewidth JF - GRAPHS AND COMBINATORICS J2 - GRAPH COMBINATOR VL - 40 PY - 2024 IS - 5 PG - 11 SN - 0911-0119 DO - 10.1007/s00373-024-02828-y UR - https://m2.mtmt.hu/api/publication/35192732 ID - 35192732 N1 - Export Date: 30 August 2024 Correspondence Address: Katona, G.Y.; Department of Computer Science and Information Theory, Hungary; email: katona.gyula@vik.bme.hu AB - 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. LA - English DB - MTMT ER - TY - JOUR AU - Schlotter, Ildikó Anna AU - Biró, Péter AU - Fleiner, Tamás TI - The Core of Housing Markets from an Agent’s Perspective. Is It Worth Sprucing up Your Home? TS - Is It Worth Sprucing up Your Home? JF - MATHEMATICS OF OPERATIONS RESEARCH J2 - MATH OPER RES PY - 2024 PG - 27 SN - 0364-765X DO - 10.1287/moor.2023.0092 UR - https://m2.mtmt.hu/api/publication/35191119 ID - 35191119 N1 - Funding Agency and Grant Number: Hungarian Scientific Research Fund [K124171, K128611]; Hungarian Academy of Sciences under its Momentum Programme [LP2021-2]; Janos Bolyai Research Scholarship; National Research Development and Innovation Office [BME NC TKP2020, OTKA K143858]; Higher Education Excellence Program of the Ministry of Human Capacities in the frame of the Artificial Intelligence research area of the Budapest University of Technology and Economics (BME FIKP-MI/SC); OTKA [K143858]; Hungarian Academy of Sciences [LP2021-2] Funding text: This work was supported by the Hungarian Scientific Research Fund [Grants K124171, K128611] . I. Schlotter is supported by the Hungarian Academy of Sciences under its Momentum Programme (LP2021-2) and its Janos Bolyai Research Scholarship. The research reported in this paper and carried out by T. Fleiner at the Budapest University of Technology and Economics was supported by the "TKP2020, National Challenges Program" of the National Research Development and Innovation Office [BME NC TKP2020 and OTKA K143858] and by the Higher Education Excellence Program of the Ministry of Human Capacities in the frame of the Artificial Intelligence research area of the Budapest University of Technology and Economics (BME FIKP-MI/SC) . P. Biro gratefully acknowledges financial support from the Hungarian Scientific Research Fund, OTKA [Grant K143858] and the Hungarian Academy of Sciences [Momentum Grant LP2021-2] . AB - 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. LA - English DB - MTMT ER - TY - JOUR AU - Gerbner, Dániel AU - Hama Karim, Hilal TI - Stability from graph symmetrization arguments in generalized Turán problems JF - JOURNAL OF GRAPH THEORY J2 - J GRAPH THEOR VL - 107 PY - 2024 IS - 4 SP - 681 EP - 692 PG - 12 SN - 0364-9024 DO - 10.1002/jgt.23151 UR - https://m2.mtmt.hu/api/publication/35159616 ID - 35159616 N1 - Export Date: 5 August 2024 CODEN: JGTHD Correspondence Address: Hama Karim, H.; Department of Computer Science and Information Theory, Műegyetem rkp. 3, Hungary; email: hilal.hamakarim@edu.bme.hu Funding details: National Research, Development and Innovation Office Funding details: SNN 129364, FK 132060, KKP‐133819 Funding text 1: Research of D\\u00E1niel Gerbner was supported by the National Research, Development and Innovation Office\\u2014NKFIH under the grants SNN 129364, FK 132060, and KKP\\u2010133819. Research of Hilal Hama Karim was supported by the National Research, Development and Innovation Office\\u2014NKFIH under the grant FK 132060. AB - 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. LA - English DB - MTMT ER - TY - JOUR AU - Kocsis, Anett AU - Matolcsi, Dávid AU - Sándor, Csaba AU - Tőtős, György TI - Multiplicative complements, II. JF - JOURNAL OF NUMBER THEORY J2 - J NUMBER THEORY VL - 265 PY - 2024 SP - 1 EP - 19 PG - 19 SN - 0022-314X DO - 10.1016/j.jnt.2024.05.014 UR - https://m2.mtmt.hu/api/publication/35159588 ID - 35159588 N1 - Eötvös Loránd University, Budapest, Hungary Department of Stochastics, Institute of Mathematics, Budapest University of Technology and Economics, Műegyetem rkp. 3., Budapest, H-1111, Hungary Department of Computer Science and Information Theory, Budapest University of Technology and Economics, Műegyetem rkp. 3., Budapest, H-1111, Hungary MTA-BME Lendület Arithmetic Combinatorics Research Group, MKH, Műegyetem rkp. 3., Budapest, H-1111, Hungary Faculty of Mathematics and Computer Science, Babeş-Bolyai University, Romania Export Date: 5 August 2024 CODEN: JNUTA Correspondence Address: Sándor, C.; Department of Stochastics, Műegyetem rkp. 3., Hungary; email: csandor@math.bme.hu Funding details: Nemzeti Kutatási, Fejlesztési és Innovaciós Alap, NKFIA Funding details: K129335, KKP144059 Funding text 1: The authors would like to thank the referee for careful reading of the paper and for useful comments. Anett Kocsis was supported by the \\u00DANKP-21-1 New National Excellence Program of the Ministry for Innovation and Technology from the source of the National Research, Development and Innovation Fund. D\\u00E1vid Matolcsi was supported by the \\u00DANKP-21-1 New National Excellence Program of the Ministry for Innovation and Technology from the source of the National Research, Development and Innovation Fund. Csaba S\\u00E1ndor was supported by the NKFIH Grants No. K129335. and NKFI KKP144059 \\u201CFractal geometry and applications\\u201D. Funding text 2: The authors would like to thank the referee for careful reading of the paper and for useful comments. Anett Kocsis was supported by the \\u00DANKP-21-1 New National Excellence Program of the Ministry for Innovation and Technology from the source of the National Research, Development and Innovation Fund. D\\u00E1vid Matolcsi was supported by the \\u00DANKP-21-1 New National Excellence Program of the Ministry for Innovation and Technology from the source of the National Research, Development and Innovation Fund. Csaba S\\u00E1ndor was supported by the NKFIH Grants No. K129335, and NKFIH KKP144059 \\u201CFractal geometry and applications\\u201D. AB - 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. LA - English DB - MTMT ER - TY - JOUR AU - Bacsó, Gábor AU - Patkós, Balázs AU - Tuza, Zsolt AU - Vizer, Máté TI - The Robust Chromatic Number of Graphs JF - GRAPHS AND COMBINATORICS J2 - GRAPH COMBINATOR VL - 40 PY - 2024 IS - 4 PG - 23 SN - 0911-0119 DO - 10.1007/s00373-024-02817-1 UR - https://m2.mtmt.hu/api/publication/35148907 ID - 35148907 N1 - Funding Agency and Grant Number: Nemzeti Kutatsi Fejlesztsi s Innovcis Hivatal [SNN 129364, FK 132060]; National Research, Development and Innovation Office-NKFIH Funding text: This research was supported in part by the National Research, Development and Innovation Office-NKFIH under the grants SNN 129364 and FK 132060.DAS:Data sharing not applicable to this article as no datasets were generated or analysed during the current study. AB - 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 . LA - English DB - MTMT ER - TY - JOUR AU - Papp, László F. TI - Restricted optimal pebbling is NP-hard JF - DISCRETE APPLIED MATHEMATICS J2 - DISCRETE APPL MATH VL - 357 PY - 2024 SP - 258 EP - 263 PG - 6 SN - 0166-218X DO - 10.1016/j.dam.2024.06.013 UR - https://m2.mtmt.hu/api/publication/35085705 ID - 35085705 N1 - Export Date: 5 July 2024 CODEN: DAMAD Funding details: Ministry of Innovation, Science and Technology, MOST Funding details: National Research, Development and Innovation Office Funding text 1: This research was supported by the Ministry of Innovation and Technology and the National Research, Development and Innovation Office within the Artificial Intelligence National Laboratory of Hungary. AB - 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 LA - English DB - MTMT ER - TY - JOUR AU - Schlotter, Ildikó Anna AU - Cechlárová, Katarína AU - Trellová, Diana TI - Parameterized complexity of candidate nomination for elections based on positional scoring rules JF - AUTONOMOUS AGENTS AND MULTI-AGENT SYSTEMS J2 - AUTON AGENTS MULTI-AG VL - 38 PY - 2024 IS - 2 PG - 36 SN - 1387-2532 DO - 10.1007/s10458-024-09658-5 UR - https://m2.mtmt.hu/api/publication/35083842 ID - 35083842 AB - 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. LA - English DB - MTMT ER -