E-mail:lior.gishboliner@math.ethz.ch

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-416L. 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-559L. Gishboliner and A. Shapira

Removal Lemmas with Polynomial Bounds

International Math Research Notices (IMRN) 2021, 14409-14444

Proc of STOC 2017, 510-522L. Gishboliner and A. Shapira

Efficient Removal without Efficient Regularity

Combinatorica 39 (2019), 639-658

Proc of ITCS 2018, 1-15J. Fox, L. Gishboliner, A. Shapira and R. Yuster

The Removal Lemma for Tournaments

Journal of Combinatorial Theory Ser. B 136 (2019), 110-134M. 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-77L. 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-772N. Alon, I. Balla, L. Gishboliner, A. Mond and F. Mousset

The Minrank of Random Graphs over Arbitrary Fields

Israel Journal of Mathematics, 2019, 1-15L. Gishboliner and A. Shapira

Testing Graphs against an Unknown Distribution

Israel Journal of Mathematics 245 (2021), 787-837

Proc of STOC 2019, 535-546O. 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-737D. 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-35L. 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-9L. Gishboliner, M. Krivelevich and P. Michaeli

Colour-Biased Hamilton Cycles in Random Graphs

Random Structures and Algorithms, 60.3 (2022), 289-307S. K. Bera, L. Gishboliner, Y. Levanzov, C. Seshadhri and A. Shapira

Counting Subgraphs in Degenerate Graphs

Journal of the ACM 69 (2022), 1-21L. Gishboliner and A. Shapira

Constructing Dense Grid-Free Linear 3-Graphs

Proc. of the American Math Society 150 (2022), 69-74L. 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 appearL. Gishboliner, R. Steiner and T. Szabó

Oriented Cycles in Digraphs of Large Outdegree

Combinatorica 2022, 1-43L. Gishboliner, R. Steiner and T. Szabó

Dichromatic Number and Forced Subdivisions

Journal of Combinatorial Theory Ser. B, 153 (2022) 1-30L. Gishboliner

Modifying a Graph's Degree Sequence and the Testablity of Degree Sequence Properties

ManuscriptL. Gishboliner, M. Krivelevich and P. Michaeli

Discrepancies of Spanning Trees and Hamilton Cycles

Journal of Combinatorial Theory Ser. B, 154 (2022), 262-291M. Bucić, L. Gishboliner and B. Sudakov

Cycles of Many Lengths in Hamiltonian Graphs

Forum of Mathematics, Sigma. 2022, p. e70L. Gishboliner, B. Sudakov and I. Tomon

Small Doubling, Atomic Structure and ℓ-Divisible Set Families

Discrete Analysis 2022:11, 16 ppL. 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, 2022L. Gishboliner and I. Tomon

Polynomial Removal Lemmas for Ordered Graphs

Combinatorial Theory, to appearL. Gishboliner, M. Krivelevich and P. Michaeli

Oriented Discrepancy of Hamilton Cycles

Journal of Graph Theory 103 (2023), 780-792D. Bradac, L. Gishboliner, O. Janzer and B. Sudakov

Asymptotics of the Hypergraph Bipartite Turan Problem

Combinatorica, 2023, 1-18L. Gishboliner and B. Sudakov

Maximal Chordal Subgraphs

Combinatorics, Probability and Computing 32(5), 724–741, 2023D. Bradac, L. Gishboliner and B. Sudakov

On Ramsey Size-Linear Graphs and Related Questions

Siam Journal on Discrete Mathematics (SIDMA), to appearL. Gishboliner and A. Shapira

Hypergraph Removal with Polynomial Bounds

SubmittedL. Gishboliner, A. Shapira and Y. Wigderson

An Efficient Asymmetric Removal Lemma and its Limitations

SubmittedL. Gishboliner, Z. Jin and B. Sudakov

The Minimum Degree Removal Lemma Thresholds

SubmittedD. Bradac, M. Christoph and L. Gishboliner

Minimum Degree Threshold for H-factors with High Discrepancy

SubmittedM. 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 appearL. 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

SubmittedL. Gishboliner, Z. Jin and B. Sudakov

Ramsey Problems for Monotone Paths in Graphs and Hyper- graphs

SubmittedL. Gishboliner, Y. Levanzov and A. Shapira

Trimming Forests is Hard (Unless They Are Made of Stars)

SubmittedL. Gishboliner, Z. Jin and B. Sudakov

Difference-Isomorphic Graph Families

SubmittedL. Gishboliner, S. Glock and A. Sgueglia

Tight Hamilton Cycles with High Discrepancy

Submitted