TY - JOUR AU - Csóka, Endre AU - Pongrácz, András TI - Local algorithms for the maximum flow and minimum cut in bounded-degree networks JF - JOURNAL OF GRAPH THEORY J2 - J GRAPH THEOR VL - Accepted: 2025 PY - 2026 SP - & PG - 27 SN - 0364-9024 UR - https://m2.mtmt.hu/api/publication/36404839 ID - 36404839 LA - English DB - MTMT ER - TY - JOUR AU - Csóka, Endre TI - Variants of local algorithms on sparse graphs JF - JOURNAL OF GRAPH THEORY J2 - J GRAPH THEOR VL - accepted: 2025 PY - 2026 SP - & SN - 0364-9024 UR - https://m2.mtmt.hu/api/publication/37074711 ID - 37074711 LA - English DB - MTMT ER - TY - JOUR AU - Csóka, Endre TI - Block Partitions in Higher Dimensions JF - DISCRETE AND COMPUTATIONAL GEOMETRY J2 - DISCRETE COMPUT GEOM VL - Published: 03 April 2025 PY - 2025 SP - & PG - 6 SN - 0179-5376 DO - 10.1007/s00454-025-00732-7 UR - https://m2.mtmt.hu/api/publication/36590811 ID - 36590811 LA - English DB - MTMT ER - TY - CONF AU - Nagy, Zoltán Lóránt AU - Bärnkopf, Pál AU - Z., Paulovics AU - Csóka, Endre AU - Fekete, Panna Tímea AU - L., Szemerédi. TI - Friendly partitions of regular graphs T2 - Booklet Summit280 PY - 2024 SP - 40 UR - https://m2.mtmt.hu/api/publication/35203325 ID - 35203325 AB - An internal or friendly partition of a graph is a partition of the vertices into two nonempty sets A∪B so that every vertex has at least as many neighbours in its own class as in the other one. For regular graphs, this means |N(v)∩A| ≥ deg(v)/2 for all elements v ∈ A and |N(v) ∩ B| ≥ deg(v)/2 for all elements v ∈ B. An old conjecture attributed to DeVos states that for fixed d, such a partition exists for all d-regular graphs, apart from finitely many counterexamples. This has been resolved for d ∈ {3, 4, 6}. (We remark that this is also closely related to an conjecture of Zolt´an F¨uredi, on friendly bisection of the Erd˝os-R´enyi random graph). In this talk I will give a survey of related results and highlight the following contributions, mostly related to the open d = 5 case: Theorem 0.0.8 In each n-vertex 5-regular graph, the intersection of 3-cohesive sets with minimum size contains at most n/4 + 1 vertices. Here the term k-cohesive was introduced by Ban and Linial [?] for vertex sets spanning a graph of minimum degree at least k. Note that for 5-regular graph admitting friendly partitions, the intersection of 3-cohesive sets with minimum size contains exactly zero vertices. The result relies on the combination of algebraic techniques (the Alon-Friedland-Kalai theorem, an application of the Combontorial Nullstellensatz) with combinatorial and random techniques. 40 Theorem 0.0.9 Asymptotically almost every 5-regular graph has an internal (friendly) partition. This would follow from a strengthening of the upper bound of the minimum bisection width problem for 5-regular random graphs, and refines the random process of Diaz, Serna and Wormald and their differential equation method as well. Finally we study the problem for the incidence graphs of projective planes, show several connections and applications, and point out the possible room for improvement in finding partitions where the spanning graphs of the two parts have minimum degree greater than the half of the average degree. The talk is based on a project joint work with P. Barnkopf, Z. Paulovics, E. Csóka, P. Fekete, L. Szemerédi. LA - English DB - MTMT ER - TY - JOUR AU - Csóka, Endre AU - Hubai, Tamás AU - Lovász, László TI - Locally common graphs JF - JOURNAL OF GRAPH THEORY J2 - J GRAPH THEOR VL - 102 PY - 2023 IS - 3 SP - 472 EP - 483 PG - 12 SN - 0364-9024 DO - 10.1002/jgt.22881 UR - https://m2.mtmt.hu/api/publication/33086820 ID - 33086820 N1 - Combinatorics and Applications Research Division, Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Computer Science, Institute of Mathematics, Eötvös Loránd University, Budapest, Hungary Export Date: 8 November 2022 CODEN: JGTHD Correspondence Address: Csóka, E.; Combinatorics and Applications Research Division, Hungary; email: csokaendre@gmail.com Funding details: KKP 138270 Funding details: European Research Council, ERC, 810115 Funding text 1: The research was supported by European Research Council Synergy grant No. 810115. Endre Csóka was supported by the NRDI grant KKP 138270. We would like to thank the anonymous referees for their helpful comments. Open Access Funding provided by EISZ ‐ Eotvos Lorand University. AB - Goodman proved that the sum of the number of triangles in a graph on nodes and its complement is at least ; in other words, this sum is minimized, asymptotically, by a random graph with edge density 1/2. Erdős conjectured that a similar inequality will hold for in place of , but this was disproved by Thomason. But an analogous statement does hold for some other graphs, which are called common graphs. Characterization of common graphs seems, however, out of reach. Franek and Rödl proved that is common in a weaker, local sense. Using the language of graph limits, we study two versions of locally common graphs. We sharpen a result of Jagger, Štovíček and Thomason by showing that no graph containing can be locally common, but prove that all such graphs are weakly locally common. We also show that not all connected graphs are weakly locally common. LA - English DB - MTMT ER - TY - JOUR AU - Csóka, Endre AU - Łukasz, Grabowski TI - On directed analogues of expander and hyperfinite graph sequences JF - COMBINATORICS PROBABILITY & COMPUTING J2 - COMB PROBAB COMPUT VL - 31 PY - 2022 IS - 2 SP - 184 EP - 197 PG - 14 SN - 0963-5483 DO - 10.1017/S0963548321000225 UR - https://m2.mtmt.hu/api/publication/32588884 ID - 32588884 N1 - Export Date: 12 January 2022 Correspondence Address: Grabowski, Ł.; Department of Mathematics and Statistics, United Kingdom; email: lukasz.grabowski@lancaster.ac.uk AB - We introduce and study analogues of expander and hyperfinite graph sequences in the context of directed acyclic graphs, which we call 'extender' and 'hypershallow' graph sequences, respectively. Our main result is a probabilistic construction of non-hypershallow graph sequences. © The Author(s), 2021. Published by Cambridge University Press. LA - English DB - MTMT ER - TY - JOUR AU - Csóka, Endre AU - Blázsik, Zoltán AU - Király, Zoltán AU - Lenger, Dániel Antal TI - Upper bounds for the necklace folding problems JF - JOURNAL OF COMBINATORIAL THEORY SERIES B J2 - J COMB THEORY B VL - 157 PY - 2022 SP - 123 EP - 143 PG - 21 SN - 0095-8956 DO - 10.1016/j.jctb.2022.05.012 UR - https://m2.mtmt.hu/api/publication/33056151 ID - 33056151 N1 - Alfréd Rényi Institute, Budapest, Hungary ELKH–ELTE Geometric and Algebraic Combinatorics Research Group, Budapest, Hungary Department of Computer Science, ELTE Eötvös Loránd University, Budapest, Hungary Export Date: 18 August 2022 CODEN: JCBTB Funding details: ERC-2018-SYG 810115 Funding details: Hungarian Scientific Research Fund, OTKA, FK 132524, SNN 132625 Funding details: Nemzeti Kutatási Fejlesztési és Innovációs Hivatal, NKFIH Funding text 1: The research was supported by Dynasnet European Research Council Synergy project (ERC-2018-SYG 810115).The research was supported by the Hungarian National Research, Development and Innovation Office, OTKA grant no. SNN 132625.This research was partially supported by the Hungarian National Research, Development and Innovation Office, OTKA grant no. FK 132524. AB - A necklace can be considered as a cyclic list of n red and n blue beads in an arbitrary order. In the necklace folding problem the goal is to find a large crossing-free matching of pairs of beads of different colors in such a way that there exists a “folding” of the necklace, that is a partition into two contiguous arcs, which splits the beads of any matching edge into different arcs. We give counterexamples for some conjectures about the necklace folding problem, also known as the separated matching problem. The main conjecture (given independently by three sets of authors) states that [Formula presented], where μ is the ratio of the maximum number of matched beads to the total number of beads. We refute this conjecture by giving a construction which proves that μ≤2−2<0.5858≪0.66. Our construction also applies to the homogeneous model when we match beads of the same color. Moreover, we also consider the problem where the two color classes do not necessarily have the same size. © 2022 Elsevier Inc. LA - English DB - MTMT ER - TY - CHAP AU - Czifra, Domonkos AU - Csóka, Endre AU - Zombori, Zsolt AU - Makay, Géza ED - Burelli, Paolo ED - Sicart, Miguel TI - Towards solving the 7-in-a-row game T2 - 2021 IEEE Conference on Games (CoG) PB - Institute of Electrical and Electronics Engineers (IEEE) CY - New York, New York SN - 9781665438865 PY - 2021 SP - 01 EP - 08 PG - 8 DO - 10.1109/CoG52621.2021.9618991 UR - https://m2.mtmt.hu/api/publication/32574859 ID - 32574859 N1 - Alfréd Rényi Institute of Mathematics, Budapest, Hungary University of Szeged, Szeged, Hungary Conference code: 175285 Export Date: 10 February 2023 Funding details: Horizon 2020 Framework Programme, H2020, 810115 Funding details: European Commission, EC Funding details: European Social Fund, ESF, 2018-1.2.1-NKP-00008, EFOP-3.6.3-VEKOP-16-2017-00002 Funding text 1: This work was supported by the European Union, co-financed by the European Social Fund (EFOP-3.6.3-VEKOP-16-2017-00002), the ERC DY-NASNET Grant (ERC-2018-SYG 810115), as well as by the Hungarian National Excellence Grant 2018-1.2.1-NKP-00008. It was also supported by the Hungarian Ministry of Innovation and Technology NRDI Office within the framework of the Artificial Intelligence National Laboratory Program. LA - English DB - MTMT ER - TY - JOUR AU - Csóka, Endre AU - Harangi, Viktor AU - Virág, Bálint TI - Entropy and expansion JF - ANNALES DE L INSTITUT HENRI POINCARE-PROBABILITES ET STATISTIQUES J2 - ANN I H POINCARE-PR VL - 56 PY - 2020 IS - 4 SP - 2428 EP - 2444 PG - 17 SN - 0246-0203 DO - 10.1214/19-AIHP1044 UR - https://m2.mtmt.hu/api/publication/31151049 ID - 31151049 N1 - Funding Agency and Grant Number: Marie Sklodowska-Curie Individual Fellowship [750857]; ERCEuropean Research Council (ERC) [InvGroGra 648017]; MTA Renyi Lendulet Veletlen Spektrum Kutatocsoport; Canada Research Chair programCanada Research Chairs; NSERC Discovery Accelerator grant Funding text: Endre Csoka was supported by Marie Sklodowska-Curie Individual Fellowship grant no. 750857 and partially supported by ERC Consolidator Grant InvGroGra 648017. Balint Virag and Viktor Harangi were supported by "MTA Renyi Lendulet Veletlen Spektrum Kutatocsoport". Balint Virag was also supported by the Canada Research Chair program, the NSERC Discovery Accelerator grant, and the ERC Consolidator Grant InvGroGra 648017. MTA Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Mathematics, University of Toronto, Toronto, Canada Export Date: 1 February 2021 CODEN: AHPBA Funding details: Natural Sciences and Engineering Research Council of Canada, NSERC Funding details: H2020 Marie Skłodowska-Curie Actions, MSCA, 750857 Funding details: European Research Council, ERC, 648017 Funding text 1: Endre Csóka was supported by Marie Skłodowska-Curie Individual Fellowship grant no. 750857 and partially supported by ERC Consolidator Grant InvGroGra 648017. Bálint Virág and Viktor Harangi were supported by “MTA Rényi Lendület Véletlen Spektrum Kutatócsoport”. Bálint Virág was also supported by the Canada Research Chair program, the NSERC Discovery Accelerator grant, and the ERC Consolidator Grant InvGroGra 648017. MTA Alfréd Rényi Institute of Mathematics, Budapest, Hungary Department of Mathematics, University of Toronto, Toronto, Canada Export Date: 5 February 2021 CODEN: AHPBA Funding details: Natural Sciences and Engineering Research Council of Canada, NSERC Funding details: H2020 Marie Skłodowska-Curie Actions, MSCA, 750857 Funding details: European Research Council, ERC, 648017 Funding text 1: Endre Csóka was supported by Marie Skłodowska-Curie Individual Fellowship grant no. 750857 and partially supported by ERC Consolidator Grant InvGroGra 648017. Bálint Virág and Viktor Harangi were supported by “MTA Rényi Lendület Véletlen Spektrum Kutatócsoport”. Bálint Virág was also supported by the Canada Research Chair program, the NSERC Discovery Accelerator grant, and the ERC Consolidator Grant InvGroGra 648017. LA - English DB - MTMT ER - TY - JOUR AU - Bárány, Imre AU - Csóka, Endre AU - Károlyi, Gyula AU - Tóth, Géza TI - Block partitions: an extended view JF - ACTA MATHEMATICA HUNGARICA J2 - ACTA MATH HUNG VL - 155 PY - 2018 IS - 1 SP - 36 EP - 46 PG - 11 SN - 0236-5294 DO - 10.1007/s10474-018-0802-2 UR - https://m2.mtmt.hu/api/publication/3395278 ID - 3395278 N1 - Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 13 Reáltanoda street, Budapest, 1053, Hungary Department of Mathematics, University College London, Gower Street, London, WC1E 6BT, United Kingdom Institute of Mathematics, Eötvös University, 1/C Pázmány P. sétány, Budapest, 1117, Hungary Export Date: 3 January 2019 Correspondence Address: Tóth, G.; Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 13 Reáltanoda street, Hungary; email: toth@renyi.hu Funding details: 267165 Funding details: TÉT 12 MX-1-2013-0006 Funding details: K 111827 Funding details: 648017 Funding details: 750857 Funding details: K 116769 Funding details: 306493 Funding text 1: ∗Corresponding author. †IB was supported by ERC Advanced Research Grant no 267165 (DISCONV) and by National Research, Development and Innovation Office NKFIH Grants K 111827 and K 116769. ‡ECs was supported by ERC grants 306493 and 648017 and by Marie Curie Fellowship, grant No. 750857. §GyK was partially supported by bilateral research grant TÉT 12 MX-1-2013-0006. ¶GT was supported by the National Research, Develpoment and Innovation Office NKFIH Grant K 111827. Key words and phrases: sequence, block partition, transversal. Mathematics Subject Classification: primary 05A18, secondary 52C99. Funding Agency and Grant Number: ERC Advanced Research Grant [267165]; National Research, Development and Innovation Office NKFIH [K 111827, K 116769]; ERC [306493, 648017]; Marie Curie Fellowship [750857]; National Research, Develpoment and Innovation Office NKFIH Grant [K 111827]; [TET 12 MX-1-2013-0006] Funding text: IB was supported by ERC Advanced Research Grant no 267165 (DISCONV) and by National Research, Development and Innovation Office NKFIH Grants K 111827 and K 116769.; ECs was supported by ERC grants 306493 and 648017 and by Marie Curie Fellowship, grant No. 750857.; GyK was partially supported by bilateral research grant TET 12 MX-1-2013-0006.; GT was supported by the National Research, Develpoment and Innovation Office NKFIH Grant K 111827. Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 13 Reáltanoda street, Budapest, 1053, Hungary Department of Mathematics, University College London, Gower Street, London, WC1E 6BT, United Kingdom Institute of Mathematics, Eötvös University, 1/C Pázmány P. sétány, Budapest, 1117, Hungary Export Date: 16 September 2019 Correspondence Address: Tóth, G.; Alfréd Rényi Institute of Mathematics, Hungarian Academy of Sciences, 13 Reáltanoda street, Hungary; email: toth@renyi.hu Funding details: 267165 Funding details: TÉT 12 MX-1-2013-0006, K 111827, 648017, 750857, K 116769, 306493 Funding text 1: ∗Corresponding author. †IB was supported by ERC Advanced Research Grant no 267165 (DISCONV) and by National Research, Development and Innovation Office NKFIH Grants K 111827 and K 116769. ‡ECs was supported by ERC grants 306493 and 648017 and by Marie Curie Fellowship, grant No. 750857. §GyK was partially supported by bilateral research grant TÉT 12 MX-1-2013-0006. ¶GT was supported by the National Research, Develpoment and Innovation Office NKFIH Grant K 111827. Key words and phrases: sequence, block partition, transversal. Mathematics Subject Classification: primary 05A18, secondary 52C99. AB - Given a sequence , a block B of S is a subsequence . The size b of a block B is the sum of its elements. It is proved in [1] that for each positive integer n, there is a partition of S into n blocks B (1), B (n) with for every i, j. In this paper, we consider a generalization of the problem in higher dimensions. LA - English DB - MTMT ER -