|
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 theory, sparse hypergraphs, property testing, Ramsey theory, random graphs, edge modification problems
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
Submitted
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, to appear
L. Gishboliner and I. Tomon
On
3-Graphs with no Four Vertices Spanning Exactly Two Edges
Bulletin of the London Mathematical Society, 2021
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
Submitted
D. Bradac, L. Gishboliner and B. Sudakov
On Ramsey Size-Linear Graphs and Related Questions
Submitted
D. Bradac, L. Gishboliner, O. Janzer and B. Sudakov
Asymptotics of the Hypergraph Bipartite Turan Problem
Submitted
L. Gishboliner and A. Shapira
Hypergraph Removal with Polynomial Bounds
Submitted
L. Gishboliner and B. Sudakov
Maximal Chordal Subgraphs
Submitted