My research interests are in extremal and probabilistic combinatorics, Ramsey theory, and applications of these to theoretical computer science.
My research interests are in extremal and probabilistic combinatorics, Ramsey theory, and applications of these to theoretical computer science.
L. Gishboliner and A. Shapira
Deterministic vs Non-Deterministic Graph Property Testing
Israel Journal of Mathematics 204, 397-416, 2014
L. Gishboliner, M. Krivelevich and G. Kronenberg
On MAXCUT in Strictly Supercritical Random Graphs, and Coloring of Random Graphs and Random Tournaments
Random Structures and Algorithms, 52(4), 545-559, 2018
L. Gishboliner and A. Shapira
Efficient Removal without Efficient Regularity
Combinatorica 39, 639-658, 2019
Also in Proc of ITCS 2018, 1-15
J. Fox, L. Gishboliner, A. Shapira and R. Yuster
The Removal Lemma for Tournaments
Journal of Combinatorial Theory Ser. B 136, 110-134, 2019
M. Bednarska-Bzdega, O. Ben-Eliezer, L. Gishboliner and T. Tran
On the Separation Conjecture in Avoider-Enforcer Games
Journal of Combinatorial Theory Ser. B 138, 41-77, 2019
L. Gishboliner and A. Shapira
A Generalized Turan Problem and its Applications
International Math Research Notices (IMRN) 11, 3417-3452, 2020
Also in Proc of STOC 2018, 760-772
N. Alon, I. Balla, L. Gishboliner, A. Mond and F. Mousset
The Minrank of Random Graphs over Arbitrary Fields
Israel Journal of Mathematics 235(1), 63-77, 2020
O. Ben-Eliezer, L. Gishboliner, D. Hefetz and M. Krivelevich
Very Fast Construction of Bounded-Degree Spanning Graphs via the Semi-Random Graph Process
Random Structures and Algorithms 57, 892-919, 2020
Also in Proc of SODA 2020, 718-737
L. Gishboliner and A. Shapira
Removal Lemmas with Polynomial Bounds
International Math Research Notices (IMRN) 2021, 14409-14444
Also in Proc of STOC 2017, 510-522
L. Gishboliner and A. Shapira
Testing Graphs against an Unknown Distribution
Israel Journal of Mathematics 245, 787-837, 2021
Also in Proc of STOC 2019, 535-546
L. Gishboliner, A. Shapira and H. Stagni
Testing Linear Inequalities of Subgraph Statistics
Random Structures and Algorithms, 58, 468-479, 2021
Also in Proc. of ITCS 2020, 1-9
L. Gishboliner, M. Krivelevich and P. Michaeli
Colour-Biased Hamilton Cycles in Random Graphs
Random Structures and Algorithms, 60.3, 289-307, 2022
S. K. Bera, L. Gishboliner, Y. Levanzov, C. Seshadhri and A. Shapira
Counting Subgraphs in Degenerate Graphs
Journal of the ACM 69, 1-21, 2022
L. Gishboliner and A. Shapira
Constructing Dense Grid-Free Linear 3-Graphs
Proc. of the American Math Society 150, 69-74, 2022
L. Gishboliner, R. Steiner and T. Szabó
Oriented Cycles in Digraphs of Large Outdegree
Combinatorica 42(Suppl 1), pp.1145-1187, 2022
L. Gishboliner, R. Steiner and T. Szabó
Dichromatic Number and Forced Subdivisions
Journal of Combinatorial Theory Ser. B, 153, 1-30, 2022
L. Gishboliner, M. Krivelevich and P. Michaeli
Discrepancies of Spanning Trees and Hamilton Cycles
Journal of Combinatorial Theory Ser. B, 154, 262-291, 2022
M. Bucić, L. Gishboliner and B. Sudakov
Cycles of Many Lengths in Hamiltonian Graphs
Forum of Mathematics, Sigma. 2022, p. e70
L. Gishboliner, B. Sudakov and I. Tomon
Small Doubling, Atomic Structure and ℓ-Divisible Set Families
Discrete Analysis 2022:11, 16 pp
L. Gishboliner and I. Tomon
On 3-Graphs with no Four Vertices Spanning Exactly Two Edges
Bulletin of the London Mathematical Society 54, 2117–2134, 2022
L. Gishboliner
A Characterization of Easily Testable Induced Digraphs and k-Colored Graphs
European Journal of Combinatorics, 103, 103516, 2022
L. Gishboliner and I. Tomon
Polynomial Removal Lemmas for Ordered Graphs
Combinatorial Theory 2(3), 2022
D. Conlon, L. Gishboliner, Y. Levanzov and A. Shapira
A New Bound for the Brown-Erdős-Sós Problem
Journal of Combinatorial Theory Ser. B 158, 1-35, 2023
L. Gishboliner, Y. Levanzov, A. Shapira and R. Yuster
Counting Homomorphic Cycles in Degenerate Graphs
ACM Transactions on Algorithms 19(1), 1-22, 2023.
Also in Proc. of SODA 2022, 417-430
L. Gishboliner, M. Krivelevich and P. Michaeli
Oriented Discrepancy of Hamilton Cycles
Journal of Graph Theory 103, 780-792, 2023
D. Bradac, L. Gishboliner, O. Janzer and B. Sudakov
Asymptotics of the Hypergraph Bipartite Turan Problem
Combinatorica 43.3: 429-446, 2023
L. Gishboliner and B. Sudakov
Maximal Chordal Subgraphs
Combinatorics, Probability and Computing 32(5), 724-741, 2023
L. Gishboliner and A. Shapira
On Rodl’s Theorem for Cographs
Electronic Journal of Combinatorics 30(4), 2023
D. Bradac, L. Gishboliner and B. Sudakov
On Ramsey Size-Linear Graphs and Related Questions
Siam Journal on Discrete Mathematics (SIDMA) 38.1: 225-242, 2024
L. Gishboliner, Z. Jin and B. Sudakov
The Minimum Degree Removal Lemma Thresholds
Journal of Combinatorial Theory Ser. B 166: 203-221, 2024
D. Bradac, M. Christoph and L. Gishboliner
Minimum Degree Threshold for H-factors with High Discrepancy
Electronic Journal of Combinatorics 31(3), 2024
M. Axenovich, D. Bradac, L. Gishboliner, D. Mubayi and L. Weber
Large Cliques or Co-Cliques in Hypergraphs with Forbidden Order-Size Pairs
Combinatorics, Probability and Computing 33(3), 286-299, 2024
L. Gishboliner, N. Kushnir and A. Shapira
Testing versus Estimation of Graph Properties, Revisited
Random Structures and Algorithms 65(3), pp.460-487, 2024.
L. Gishboliner and B. Simic
Polynomial Removal Lemma for Ordered Matchings
Electronic Journal of Combinatorics 31(4), 2024
L. Gishboliner, Z. Jin and B. Sudakov
Ramsey Problems for Monotone Paths in Graphs and Hypergraphs
Combinatorica 44, 509–529, 2024
L. Gishboliner, Y. Levanzov and A. Shapira
Trimming Forests is Hard (Unless They Are Made of Stars)
Siam Journal on Discrete Mathematics (SIDMA) 38(4), 3028-3042, 2024
L. Gishboliner and A. Shapira
Hypergraph Removal with Polynomial Bounds
Mathematical Proceedings of the Cambridge Philisophical Society 178(3), 321-330, 2025
L. Gishboliner, A. Shapira and Y. Wigderson
An Efficient Asymmetric Removal Lemma and its Limitations
Forum of Mathematics, Sigma 13, p. e38, Cambridge University Press, 2025
L. Gishboliner, S. Glock and A. Sgueglia
Tight Hamilton Cycles with High Discrepancy
Combinatorics, Probability and Computing 34(4), 565--584, 2025
L. Gishboliner, S. Glock and A. Sgueglia
Steiner Triple Systems with High Discrepancy
Journal of Combinatorial Designs 34(1), 5--14, 2025
L. Gishboliner, O. Janzer and B. Sudakov
Induced Subgraphs of K_r-Free Graphs and the Erdos-Rogers Problem
Combinatorica 45(2), 1-20, 2025
L. Gishboliner and A. Shapira
Polynomial Property Testing (survey article)
Computer Science Review 58, p.100806, 2025.
L. Gishboliner and E. Honest
Disperse Hypergraphs
Combinatorics, Probability and Computing 35(1) 89-100, 2026
L. Gishboliner, A. Shapira and Y. Wigderson
Is It Easy to Regularize a Hypergraph with Easy Links?
International Math Research Notices (IMRN) 2026(4), p.rnag018, 2026.
L. Gishboliner, Z. Jin and B. Sudakov
Difference-Isomorphic Graph Families
Journal of Combinatorial Theory Ser. B 180, pp.25-61, 2026
L. Gishboliner, S. Glock, P. Michaeli and A. Sgueglia
Defect and Transference Versions of the Alon-Frankl-Lovasz Theorem
Combinatorics, Probability and Computing, pp.1-12, 2026.
L. Gishboliner, E. Hurley and Y. Wigderson
Asymmetric Results about Graph Homomorphisms
Random Structures & Algorithms, 69(1), p.e70085, 2026.
F. Arnold, L. Gishboliner and B. Sudakov
Two Erdos-Hajnal-Type Theorems for Forbidden Order-Size Pairs
Combinatorial Theory, Ser. B, 182, pp.251-285, 2027.
L. Gishboliner, Z. Jin and B. Sudakov
Set Mappings for General Graphs
Combinatorics, Probability and Computing, to appear
N. Alon, M. Bucic and L. Gishboliner
The Spanning Tree Spectrum: Improved Bounds and Simple Proofs
Proc. of the American Math Society, to appear
M. Christoph, L. Gishboliner and M. Krivelevich
Subgraph Discrepancies in the Complete Graph
Acta Mathematica Hungarica, to appear
L. Gishboliner, Y. Levanzov and A. Shapira
Hardness of Hypergraph Edge Modification Problems
Submitted
H. Chan, D. Cheng, L. Gishboliner and X. Li
Multicolor K_r-Tilings with High Discrepancy
Submitted
L. Gishboliner and J. Solymosi
A Simple Counting Argument for Dense Linear Hypergraphs
Submitted
L. Gishboliner, X. Huang and H. Liu
Homomorphism and VC-Dimension Thresholds: Spectra and Separations
Submitted
L. Gishboliner. Y. Levanzov and A. Shapira
NP-Hardness of Generalized-Turan Graph Modification Problems
Submitted
L. Gishboliner and E. Honest
NP-Hardness of the H-Free Edge-Deletion Problem
Submitted
L. Gishboliner and X. Li
Upper Bounds for Ordered Ramsey Numbers of Forests and Bounded-Degree Graphs
Submitted
L. Gishboliner and X. Li
Extremal Numbers of Acyclic Matrices
Submitted
L. Gishboliner, A. Kravtsov and X. Li
Ordered Trees with Linear Off-Diagonal Ramsey Numbers
Submitted