|
Office: J65, ETH Main Building (HG)
My research is in the field of extremal and probabilistic combinatorics and its applications to theoretical computer science. I'm interested in the following topics: Extremal graph and hypergraph theory, Ramsey theory, Property testing, Random graphs
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
N. Alon, I. Balla, L.
Gishboliner, A. Mond and F. Mousset
The
Minrank of Random Graphs over Arbitrary Fields
Israel
Journal of Mathematics, 2019, 1-15
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, to appear
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), to appear
L. Gishboliner and A. Shapira
Hypergraph Removal with Polynomial Bounds
Submitted
L. Gishboliner, A. Shapira and Y. Wigderson
An Efficient Asymmetric Removal Lemma and its Limitations
Submitted
L. Gishboliner, Z. Jin and B. Sudakov
The Minimum Degree Removal Lemma Thresholds
Submitted
D. Bradac, M. Christoph and L. Gishboliner
Minimum Degree Threshold for H-factors with High Discrepancy
Submitted
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, to appear
L. Gishboliner, N. Kushnir and A. Shapira
Testing versus Estimation of Graph Properties, Revisited
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, to appear.
L. Gishboliner and B. Simic
Polynomial Removal Lemma for Ordered Matchings
Submitted
L. Gishboliner, Z. Jin and B. Sudakov
Ramsey Problems for Monotone Paths in Graphs and Hyper-
graphs
Submitted
L. Gishboliner, Y. Levanzov and A. Shapira
Trimming Forests is Hard (Unless They Are Made of
Stars)
Submitted
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
Submitted