Lior Gishboliner

activity

20132026

most citedColour-biased Hamilton cycles in random graphs

7 citations · 19 across the 40 of their papers we have counts for

collaborators

62 papers

math.CO2026

NP-Hardness of Generalized-Turán Graph Modification Problems

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

For graphs $G, T$ and a graph-family $H$ , let $e x (G, T, H)$ denote the maximum possible number of copies of $T$ in an $H$ -free subgraph of $G$ . Alon and…

math.CO2026

Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs

Lior Gishboliner, Xiangyu Li

We prove the following two upper bounds for ordered Ramsey numbers: (1) Every ordered forest $F$ on $n$ vertices satisfies $R_{<} (F, F) = O (n^{1 + ⌈ l o g χ_{<} (F)⌉})$ . This in p…

math.CO2026

Extremal numbers of acyclic matrices

Lior Gishboliner, Xiangyu Li

For a zero-one matrix $P$ , let $Ex (n, P)$ denote the maximum number of ones in an $n \times n$ zero-one matrix avoiding $P$ . We prove that $$\operatorname{Ex}(n,P) \le…

math.CO2026

NP-Hardness of the $H$ -Free Edge-Deletion Problem

Lior Gishboliner, Ethan Honest

For a graph $H$ , the $H$ -freeness edge-deletion problem is the algorithmic problem of finding, for an input graph $G$ , the minimum number of edges of $G$ whose deletion turns $G$ i…

math.CO2026

Homomorphism and VC-dimension thresholds: spectra and separations

Lior Gishboliner, Xinqi Huang, Hong Liu

Minimum-degree thresholds ask when excluding a fixed graph $H$ forces a dense graph to admit a simple global description. For each fixed chromatic number, the chromatic threshold h…

math.CO2026

A Simple Counting Argument for Dense Linear Hypergraphs

Lior Gishboliner, József Solymosi

In connection to the Brown-Erdős-Sós conjecture, we give a short local averaging proof of a density theorem for linear uniform hypergraphs. Let $r \geq 3$ , $k \geq 3$ , and suppose th…

math.CO2026

Multicolor $K_{r}$ -Tilings with High Discrepancy

Henry Chan, Daniel Cheng, Lior Gishboliner +1

We study the minimum degree threshold $δ_{r, q}$ guaranteeing the existence of $K_{r}$ -tilings of high discrepancy in any $q$ -edge-coloring. Balogh, Csaba, Pluhár and Treglown handled…

math.CO2026

Subgraph discrepancies in the complete graph

Micha Christoph, Lior Gishboliner, Michael Krivelevich

Given a 2-edge-coloring $f : E (K_{n}) \to {\pm 1}$ , the discrepancy of a subgraph $F \subseteq K_{n}$ is defined as $\sum_{e \in E (F)} f (e)$ . Erdős, Füredi, Lo…

math.CO2026

Set mappings for general graphs

Lior Gishboliner, Zhihan Jin, Benny Sudakov

The study of extremal problems for set mappings has a long history. It was introduced in 1958 by Erdős and Hajnal, who considered the case of cliques in graphs and hypergraphs. Rec…

cs.DS2025

Polynomial Property Testing

Lior Gishboliner, Asaf Shapira

Property testers are fast, randomized "election polling"-type algorithms that determine if an input (e.g., graph or hypergraph) has a certain property or is $ε$ -far from…

math.CO2025

Regularity for hypergraphs with bounded VC $_{2}$ dimension

Lior Gishboliner, Asaf Shapira, Yuval Wigderson

While Szemerédi's graph regularity lemma is an indispensable tool for studying extremal problems in graph theory, using it comes with a hefty price, since a worst-case graph may on…

math.CO2025

Is it easy to regularize a hypergraph with easy links?

Lior Gishboliner, Asaf Shapira, Yuval Wigderson

A partition of a (hyper)graph is $ε$ -homogenous if the edge densities between almost all clusters are either at most $ε$ or at least $1 - ε$ . Suppose a…

math.CO2025

The spanning tree spectrum: improved bounds and simple proofs

Noga Alon, Matija Bucić, Lior Gishboliner

The number of spanning trees of a graph $G$ , denoted $τ (G)$ , is a well studied graph parameter with numerous connections to other areas of mathematics. In a recent remarkable paper…

math.CO2025

Steiner triple systems with high discrepancy

Lior Gishboliner, Stefan Glock, Amedeo Sgueglia

In this paper, we initiate the study of discrepancy questions for combinatorial designs. Specifically, we show that, for every fixed $r \geq 3$ and $n \equiv 1, 3 (mod 6)$ , any $r$ -co…

math.CO2025

Disperse Hypergraphs

Lior Gishboliner, Ethan Honest

For $ℓ \geq 3$ , an $ℓ$ -uniform hypergraph is disperse if the number of edges induced by any set of $ℓ + 1$ vertices is 0, 1, $ℓ$ or $ℓ + 1$ . We show that every disperse…

math.CO2025

Defect and transference versions of the Alon-Frankl-Lovasz theorem

Lior Gishboliner, Stefan Glock, Peleg Michaeli +1

Confirming a conjecture of Erdős on the chromatic number of Kneser hypergraphs, Alon, Frankl and Lovász proved that in any $q$ -colouring of the edges of the complete $r$ -uniform hy…

math.CO2025

Hardness of Hypergraph Edge Modification Problems

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

For a fixed graph $F$ , let $e x_{F} (G)$ denote the size of the largest $F$ -free subgraph of $G$ . Computing or estimating $e x_{F} (G)$ for various pairs $F, G$ is one of the central proble…

math.CO2025

Asymmetric results about graph homomorphisms

Lior Gishboliner, Eoin Hurley, Yuval Wigderson

Many important results in extremal graph theory can be roughly summarised as "if a triangle-free graph $G$ has certain properties, then it has a homomorphism to a triangle-free gra…

math.CO2024

Canonical Ramsey numbers of sparse graphs

Lior Gishboliner, Aleksa Milojević, Benny Sudakov +1

The canonical Ramsey theorem of Erdős and Rado implies that for any graph $H$ , any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph $K_{N}$ c…

math.CO2024

Induced subgraphs of $K_{r}$ -free graphs and the Erdős--Rogers problem

Lior Gishboliner, Oliver Janzer, Benny Sudakov

For two graphs $F, H$ and a positive integer $n$ , the function $f_{F, H} (n)$ denotes the largest $m$ such that every $H$ -free graph on $n$ vertices contains an $F$ -free induced subgr…

math.CO2024

Two Erdos-Hajnal-type theorems for forbidden order-size pairs

Fabian Arnold, Lior Gishboliner, Benny Sudakov

The celebrated Erdős-Hajnal conjecture says that any graph without a fixed induced subgraph $H$ contains a very large homogeneous set. A direct analog of this conjecture is not tru…

math.CO2023

Difference-Isomorphic Graph Families

Lior Gishboliner, Zhihan Jin, Benny Sudakov

Many well-studied problems in extremal combinatorics deal with the maximum possible size of a family of objects in which every pair of objects satisfies a given restriction. One pr…

math.CO2023★ 3 cited

Tight Hamilton cycles with high discrepancy

Lior Gishboliner, Stefan Glock, Amedeo Sgueglia

In this paper, we study discrepancy questions for spanning subgraphs of $k$ -uniform hypergraphs. Our main result is that, for any integers $k \geq 3$ and $r \geq 2$ , any $r$ -colourin…

math.CO2023

Trimming forests is hard (unless they are made of stars)

Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira

Graph modification problems ask for the minimal number of vertex/edge additions/deletions needed to make a graph satisfy some predetermined property. A (meta) problem of this type,…

NP-Hardness of Generalized-Turán Graph Modification Problems

Upper bounds for ordered Ramsey numbers of forests and bounded-degree graphs

Extremal numbers of acyclic matrices

NP-Hardness of the H-Free Edge-Deletion Problem

Homomorphism and VC-dimension thresholds: spectra and separations

A Simple Counting Argument for Dense Linear Hypergraphs

Multicolor Kr​-Tilings with High Discrepancy

Subgraph discrepancies in the complete graph

Set mappings for general graphs

Polynomial Property Testing

Regularity for hypergraphs with bounded VC2​ dimension

Is it easy to regularize a hypergraph with easy links?

The spanning tree spectrum: improved bounds and simple proofs

Steiner triple systems with high discrepancy

Disperse Hypergraphs

Defect and transference versions of the Alon-Frankl-Lovasz theorem

Hardness of Hypergraph Edge Modification Problems

Asymmetric results about graph homomorphisms

Canonical Ramsey numbers of sparse graphs

Induced subgraphs of Kr​-free graphs and the Erdős--Rogers problem

Two Erdos-Hajnal-type theorems for forbidden order-size pairs

Difference-Isomorphic Graph Families

Tight Hamilton cycles with high discrepancy

Trimming forests is hard (unless they are made of stars)

NP-Hardness of the $H$ -Free Edge-Deletion Problem

Multicolor $K_{r}$ -Tilings with High Discrepancy

Regularity for hypergraphs with bounded VC $_{2}$ dimension

Induced subgraphs of $K_{r}$ -free graphs and the Erdős--Rogers problem