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 (2014), 397-416
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) (2018), 545-559
L. Gishboliner and A. Shapira
Removal Lemmas with Polynomial Bounds
International Math Research Notices (IMRN) 2021, 14409-14444
Proc of STOC 2017, 510-522
L. Gishboliner and A. Shapira
Efficient Removal without Efficient Regularity
Combinatorica 39 (2019), 639-658
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 (2019), 110-134
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 (2019), 41-77
L. Gishboliner and A. Shapira
A Generalized Turan Problem and its Applications
International Math Research Notices (IMRN) 11 (2020), 3417-3452
Proc of STOC 2018, 760-772
L. Gishboliner and A. Shapira
Testing Graphs against an Unknown Distribution
Israel Journal of Mathematics 245 (2021), 787-837
Proc of STOC 2019, 535-546
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 (2020), 892-919
Proc of SODA 2020, 718-737
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 (2023), 1-35
L. Gishboliner, A. Shapira and H. Stagni
Testing Linear Inequalities of Subgraph Statistics
Random Structures and Algorithms, 58 (2021), 468-479
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 (2022), 289-307
S. K. Bera, L. Gishboliner, Y. Levanzov, C. Seshadhri and A. Shapira
Counting Subgraphs in Degenerate Graphs
Journal of the ACM 69 (2022), 1-21
L. Gishboliner and A. Shapira
Constructing Dense Grid-Free Linear 3-Graphs
Proc. of the American Math Society 150 (2022), 69-74
L. Gishboliner, Y. Levanzov, A. Shapira and R. Yuster
Counting Homomorphic Cycles in Degenerate Graphs
Proc. of SODA 2022, 417-430
ACM Transactions on Algorithms, to appear
L. Gishboliner, R. Steiner and T. Szabó
Oriented Cycles in Digraphs of Large Outdegree
Combinatorica 2022, 1-43
L. Gishboliner, R. Steiner and T. Szabó
Dichromatic Number and Forced Subdivisions
Journal of Combinatorial Theory Ser. B, 153 (2022) 1-30
L. Gishboliner
Modifying a Graph's Degree Sequence and the Testablity of Degree Sequence Properties
Manuscript
L. Gishboliner, M. Krivelevich and P. Michaeli
Discrepancies of Spanning Trees and Hamilton Cycles
Journal of Combinatorial Theory Ser. B, 154 (2022), 262-291
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
L. Gishboliner, M. Krivelevich and P. Michaeli
Oriented Discrepancy of Hamilton Cycles
Journal of Graph Theory 103 (2023), 780-792
D. Bradac, L. Gishboliner, O. Janzer and B. Sudakov
Asymptotics of the Hypergraph Bipartite Turan Problem
Combinatorica, 2023, 1-18
L. Gishboliner and B. Sudakov
Maximal Chordal Subgraphs
Combinatorics, Probability and Computing 32(5), 724–741, 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 and A. Shapira
Hypergraph Removal with Polynomial Bounds
Mathematical Proceedings of the Cambridge Philisophical Society, to appear
L. Gishboliner, A. Shapira and Y. Wigderson
An Efficient Asymmetric Removal Lemma and its Limitations
Forum of Mathematics, Sigma, to appear
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, to appear
Also in Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023) (pp. 46:1–46:18)
L. Gishboliner and A. Shapira
On Rodl’s Theorem for Cographs
Electronic Journal of Combinatorics 30(4), 2023
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
L. Gishboliner, Z. Jin and B. Sudakov
Difference-Isomorphic Graph Families
Submitted
L. Gishboliner, S. Glock and A. Sgueglia
Tight Hamilton Cycles with High Discrepancy
Combinatorics, Probability and Computing, to appear
F. Arnold, L. Gishboliner and B. Sudakov
Two Erdos-Hajnal-Type Theorems for Forbidden Order-Size Pairs
Submitted
L. Gishboliner, O. Janzer and B. Sudakov
Induced Subgraphs of K_r-Free Graphs and the Erdos-Rogers Problem
Submitted
L. Gishboliner, Y. Levanzov and A. Shapira
Hardness of Hypergraph Edge Modification Problems
Submitted