Combinatorial group

We are shocked by the aggression happening to Ukraine. As citizens we try to help her people with our private means. As professional mathematicians, we welcome suggestions that might help our fellow Ukrainian colleagues (students or researchers) in any way. Some funds are available to this end (here). Do not hesitate to contact us!


Outputs by projects

Random Discrete Structures of the Czech Science Foundation

Embedding, Packing and Limits in Graphs of the Czech Science Foundation

Structural properties of visibility in terrains and farthest color Voronoi diagrams of the Czech Science Foundation

Extremal graph theory and applications of the Czech Science Foundation

Mimoradna financni dotace urcena na rozvoj spoluprace s prednimi vedecko-vyzkumnymi pracovisti v Izraeli of the Czech Academy of Sciences

Outputs by members

For outputs of the members of the group, please refer to their individual web-pages (see here), where you can find as well their publications which were not achieved at the Institute of Computer Sciences.

Publication produced at the Institute of Computer Sciences

Preprints

On the total versions of 1-2-3-conjecture for graphs and hypergraphs, A. Davoodi, L. Maherani

On the anti-Ramsey threshold for non-balanced graphs, P. Araújo, T. Martins, L. Mattos, W. Mendonça, L. Moreira, and G. O. Mota

From flip processes to dynamical systems on graphons, F. Garbe, J. Hladký, M. Šileikis, F. Skerman

On a Conjecture of Erdos on Size Ramsey Number of Star Forests, A. Davoodi, R. Javadi, A. Kamranian, G. Raeisi

The tree packing conjecture for trees of almost linear maximum degree, P. Allen, J. Böttcher, D. Clemens, J. Hladký, D. Piguet, A. Taraz

On sufficient conditions for Hamiltonicity in dense graphs, R. Lang, N. Sanhueza-Matamala

Towards a hypergraph version of the Pósa-Seymour conjecture, M. Pavez-Signé, N. Sanhueza-Matamala, M. Stein

Deviation probabilities for arithmetic progressions and irregular discrete structures, S. Griffiths, C. Koch, M. Secco

Dirac-type conditions for spanning bounded-degree hypertrees, M. Pavez-Signé, N. Sanhueza-Matamala, M. Stein

A fractal perspective on optimal antichains and intersecting subsets of the unit n-cube, K. Engel, T. Mitsis, C. Pelekis

Balanced supersaturation for degenerate hypergraphs, J. Corsten, T. Tran

Accepted papers

Cycle decompositions in 3-uniform hypergraphs, S. Piga, N. Sanhueza-Matamala, accepted to Combinatorica

Sampling and Sparsification for Approximating the Packedness of Trajectories and Detecting Gatherings, S. Aghamolaei, V. Keikha, M. Ghodsi, A. Mohades, International Journal of Data Science and Analytics, to appear.

Published papers

Ramsey goodness of trees in random graphs, P. Araújo, Luiz Moreira, and Matı́as Pavez-Signé, accepted to Random Structures & Algorithms (2022+), early view

Sandwiching biregular random graphs, T. Klimošová, C. Reiher, A. Ruciński, M. Šileikis, Combinatorics, Probability and Computing, Vol. 32-1, pp. 1-44 (2023)

Cut distance identifying graphon parameters over weak* limits, M. Doležal, J. Grebík, J. Hladký, I. Rocha, V. Rozhoň, Journal of Combinatorial Theory, Series A, Volume 189 (2022) 105615

Minimum degree conditions for tight Hamilton cycles, R. Lang, N. Sanhueza-Matamala, Journal of the London Mathematical Society, Volume 105, Issue 4, pp. 2249-2323 (2022)

Counting extensions revisited, M. Šileikis, L. Warnke, accepted to Random Structures & Algorithms, Volume 61, Issue 1, pp. 3-30 (2022), DOI:10.1002/rsa.21050

Fractional Isomorphism of Graphons, J. Grebík, I. Rocha, Combinatorica, Volume 42, pp. 365-404 (2022)

Universal arrays, M. Pavez-Signé, D. A. Quiroz, N. Sanhueza-Matamala, Discrete Mathematics Volume 334, Issue 12 (2021), 112626

Longest paths in random hypergraphs, O. Cooley, F. Garbe, E. K. Hng, M. Kang, N. Sanhueza-Matamala, J. Zalla, SIAM Journal on Discrete Mathematics 35(4) (2021), 2430–2458

Clustering geometrically-modeled points in the aggregated uncertainty model, V. Keikha, S. Aghamolaei, A. Mohades, M. Ghodsi, Fundamenta Informaticae, Vol. 184, Issue 3, 27 January 2022, pp. 205-231.

A limit theorem for small cliques in inhomogeneous random graphs, J. Hladký, C. Pelekis, M. Šileikis, Journal of Graph Theory, Vol. 97, Issue 4, pp. 578-599 (2021)

Largest and smallest area triangles on imprecise points, V. Keikha, M. Löffler, A. Mohades, Computational Geometry: Theory and Applications, Vol. 95, April 2021, 101742.

Color-spanning localized query, A. Acharyya, A. Maheshwari, S.C. Nandy, Theoretical Computer Science, Vol. 861, 12 March 2021, pp. 85-101.

Tilings in graphons, J. Hladký, P. Hu, D. Piguet, European Journal of Combinatorics, Volume 93, March 2021, 103284

Improvements on Spectral Bisection, I. Rocha, Electronic Journal of Linear Algebra, Volume 36, pp. 857-877, December 2020.

Measurable versions of Vizing's theorem J. Grebík, O. Pikhurko, Advances in Mathematics, Volume 374, November 2020

Liar's domination in unit disk graphs, R.K. Jallu, S.K. Jena, G.K. Das, Theoretical Computer Science, Vol. 845, 12 December 2020, pp. 38-49.

Structure and Supersaturation for Intersecting Families, J. Balogh, S. Das, H. Liu, M. Sharifzadeh, T. Tran, Electron. J. Comb., Volume 26, Issue 2 (2019).

Hamiltonicity for convex shape Delaunay and Gabriel graphs, P. Bose, P. Cano, M. Saumell, R.I. Silveira, Computational Geometry: Theory and Applications, Vol. 89, August 2020, 101629.

Brouwer's conjecture holds asymptotically almost surely I. Rocha, Linear Algebra Appl. 597 (2020) 198–205

Relating the cut distance and the weak* topology for graphons, M. Doležal, J. Grebík, J. Hladký, I. Rocha, V. Rozhoň, Journal of Combinatorial Theory, Series B, Volume 147, March 2021, Pages 252-298.

Independent sets, cliques, and colorings in graphons, J. Hladký, I. Rocha, special issue of European Journal on Combinatorics for EUROCOMB'17, Volume 88, August 2020, 103108.

A version of the Loebl-Komlós-Sós conjecture for skewed trees, T. Klimošová, D. Piguet, V. Rozhoň, special issue of European Journal on Combinatorics for EUROCOMB'17, Volume 88, August 2020, 103106.

Upper tail bounds for Stars, M. Šileikis, L. Warnke, The Electronic Journal of Combinatorics, Volume 27, Issue 1 (2020)

A central limit theorem for almost local additive tree functionals, D. Ralaivaosaona, M. Šileikis, S. Wagner, Algorithmica dedicated to a selection of papers from the conference AofA 2018, 82, pages 642–679 (2020).

Packing degenerate graphs, P. Allen, J. Böttcher, J. Hladký, D. Piguet, Advances in Mathematics, Vol. 354, Art. 106739

A counterexample to the DeMarco-Kahn Upper Tail Conjecture, M. Šileikis, L. Warnke, Random Structures & Algorithms, Volume 55, Issue 4, December 2019, Pages 775-794

A Note on the Minimum Number of Edges in Hypergraphs with Property O, G. Kronenberg, C. Kusch, A. Lamaison, P. Micek, T. Tran, European Journal of Combinatorics, Volume 81, October 2019, Pages 172-177

On the separation conjecture in Avoider-Enforcer games, M. Bednarska-Bzdega, O. Ben-Eliezer, L. Gishboliner, T. Tran, J. Combin. Theory Ser. B, Volume 138, September 2019, Pages 41-77.

A local approach to the Erdos-Sos conjecture, V. Rozhoň, SIAM J. Discrete Math, 33(2), 643-664.

Minimal Obstructions for Partial Representations of Interval Graphs P. Klavik, M. Saumell, Electronic Journal of Combinatorics, 25(4) (2018), #P4.55

A median-type condition for graph tiling, D. Piguet, M. Saumell, European Journal of Combinatorics, Volume 77, p.90-101

Layout of random circulant graphs, S. Richter, I. Rocha, Linear Algebra and its Applications, Volume 559, p. 95-113

A generalization of Erdos' matching conjecture, C. Pelekis, I. Rocha, Electronic Journal of Combinatorics, 25(2), P2.21

Komlós's tiling theorem via graphon covers, J. Hladký, P. Hu, D. Piguet, Journal of Graph Theory, Volume 90, Issue 1, January 2019, Pages 24-45

On the structure of large sum-free sets of integers, T. Tran, Isr. J. Math. Volume 228, Issue 1, October 2018, pp 249-292

Colourings without monochromatic disjoint pairs, D. Clemens, S. Das, T. Tran, European Journal of Combinatorics, Volume 70, May 2018, Pages 99-124

The local limit of the uniform spanning tree on dense graphs, J. Hladký, A. Nachmias, T. Tran, Journal of Statistical Physics, Volume 173, Issue 3-4, pp 502-545

Recovering the structure of random linear graphs, I. Rocha, J. Janssen, N. Kalyaniwalla, Linear Algebra and its Applications, 557, 234-264

Peeling Potatoes Near-Optimally in Near-Linear Time, S. Cabello, J. Cibulka, J. Kynčl, M. Saumell, P. Valtr, SIAM J. Comput., 46(5), 1574-1602

Column planarity and partially-simultaneous geometric embedding, L. Barba. W. Evans, M. Hoffmann, V. Kusters, M. Saumell, B. Speckmann, Journal of Graph Algorithms and Applications, Vol. 21, no. 6, pp. 983-1002

The Approximate Loebl-Komlós-Sós Conjecture I: The sparse decomposition, J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. J. Stein, E. Szemerédi, SIAM J. Discrete Math., 31(2), 945-982

The Approximate Loebl-Komlós-Sós Conjecture II: The rough structure of LKS graphs, J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. J. Stein, E. Szemerédi, SIAM J. Discrete Math., 31(2), 983-1016

The Approximate Loebl-Komlós-Sós Conjecture III: The finer structure of LKS graphs, J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. J. Stein, E. Szemerédi, SIAM J. Discrete Math., 31(2), 1017-1071

The Approximate Loebl-Komlós-Sós Conjecture IV: Embedding techniques and the proof of the main result, J. Hladký, J. Komlós, D. Piguet, M. Simonovits, M. J. Stein, E. Szemerédi, SIAM J. Discrete Math., 31(2), 1072-1148

An approximate version of the Tree Packing Conjecture J. Böttcher, J. Hladký, D. Piguet, A. Taraz, Israel Journal of Mathematics, 211 (1) (2016), 391-446

Loebl-Komlos-Sos Conjecture: dense case, J. Hladký, D. Piguet, Journal of Combinatorial Theory, Series B, 116 (2016), 123-190

The approximate Loebl-Komlos-Sos conjecture and embedding trees in sparse graphs J. Hladký, D. Piguet, M. Simonovits, M. Stein, E. Szemerédi, Electronic Research Announcements in Mathematical Sciences, 22 (2015) pages 1-11

Conference Proceedings

On sufficient conditions for Hamiltonicity, R. Lang and N. Sanhueza-Matamala, accepted tp Research Perspectives CRM Barcelona, Proceedings of EUROCOMB 2021

Degree conditions for tight Hamilton cycles, R. Lang and N. Sanhueza-Matamala, accepted tp Research Perspectives CRM Barcelona, Proceedings of EUROCOMB 2021

Dirac-type conditions for spanning bounded-degree hypertrees, M. Pavez-Signé, N. Sanhueza-Matamala, and M. Stein, accepted tp Research Perspectives CRM Barcelona, Proceedings of EUROCOMB 2021.

On the k-colored Rainbow Sets in Fixed Dimensions, V. Keikha, H. Keikha, A. Mohades. Proc. 15th Annual International Conference on Combinatorial Optimization and Applications (COCOA'21); LNCS 13135, pp. 587-601, 2021.

Constrained Hitting Set Problem with Intervals, A. Acharyya, V. Keikha, D. Majumdar, S. Pandit, Proc. 27th International Computing and Combinatorics Conference (COCOON'21); LNCS 13025, pp. 604-616, 2021.

Minimum Color Spanning Circle in Imprecise Setup, A. Acharyya, R.K. Jallu, V. Keikha, M. Löffler, M. Saumell, Proc. 27th International Computing and Combinatorics Conference (COCOON'21); LNCS 13025, pp. 257-268, 2021.

Terrain prickliness: theoretical grounds for high complexity viewsheds, A. Acharyya, R.K. Jallu, M. Löffler, G. Meijer, M. Saumell, R.I. Silveira, F. Stals, Proc. 11th International Conference on Geographic Information Science (GIScience'21), Part II, 10:1-10:16, 2021.

Cause I’m a Genial Imprecise Point: Outlier Detection for Uncertain Data, V. Keikha, H. Keikha, A. Mohades, Proc. 7th Annual International Conference on Algorithms and Discrete Applied Mathematics (CALDAM'21); LNCS 12601, pp. 165-178, 2021.

On the Intersections of Non-homotopic Loops, V. Blažej, M. Opler, M. Šileikis, P. Valtr (2021), In: Mudgal A., Subramanian C.R. (eds) Algorithms and Discrete Applied Mathematics. CALDAM 2021. Lecture Notes in Computer Science, vol 12601. Springer, Cham.

A graphon perspective for fractional isomorphism, J. Grebík, I. Rocha, Acta Mathematica Universitatis Comenianae, Vol 88 No 3 (2019), p.759-765. Proceedings of the 10th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2017.

Hamiltonicity for convex shape Delaunay and Gabriel graphs, P. Bose, P. Cano, M. Saumell, R.I. Silveira, Proc. 16th Algorithms and Data Structures Symposium (WADS'19); LNCS 11646, pp. 196-210, 2019.

Asymptotic Normality of Almost Local Functionals in Conditioned Galton-Watson Trees D. Ralaivaosaona, M. Šileikis, S. Wagner, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018)

Packing degenerate graphs greedily, P. Allen, J. Böttcher, J. Hladký, D. Piguet, Electronic Notes in Discrete Mathematics, Volume 61, August 2017, Pages 45-51. Proceedings of the 9th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2017.

First steps in combinatorial optimization on graphons: Matchings, M. Doležal, J. Hladký, P. Hu, D. Piguet, Electronic Notes in Discrete Mathematics, Volume 61, August 2017, Pages 359-365. Proceedings of the 9th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2017.

A skew version of the Loebl-Komlos-Sos conjecture, T. Klimošová, D. Piguet, V. Rozhoň, Electronic Notes in Discrete Mathematics, Volume 61, August 2017, Pages 743-749. Proceedings of the 9th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2017.

A Median-Type Condition for Graph Tiling,D. Piguet, M. Saumell, Electronic Notes in Discrete Mathematics, Volume 61, August 2017, Pages 979-985. Proceedings of the 9th European Conference on Combinatorics, Graph Theory and Applications, EuroComb 2017.

Spectral Bisection with Two Eigenvectors, I. Rocha, Electronic Notes in Discrete Mathematics, Volume 61, August 2017, Pages 1019-1025