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 -