Lior Gishboliner

Last Name

Gishboliner

First Name

Lior

ORCID

0000-0003-0688-8111

Show all metadata

Search Results

Publications1 - 10 of 32

Minimum Degree Threshold for H-factors with High Discrepancy
Bradač, Domagoj; Christoph, Micha; Gishboliner, Lior (2024)
The Electronic Journal of Combinatorics
Given a graph H, a perfect H-factor in a graph G is a collection of vertex-disjoint copies of H spanning G. Kühn and Osthus showed that the minimum degree threshold for a graph G to contain a perfect H-factor is either given by 1−1/χ(H) or by 1−1/χ_cr(H) depending on certain natural divisibility considerations. Given a graph G of order n, a 2-edge-coloring of G and a subgraph G' of G, we say that G' has high discrepancy if it contains significantly (linear in n) more edges of one color than the other. Balogh, Csaba, Pluhár and Treglown asked for the minimum degree threshold guaranteeing that every 2-edge-coloring of G has an H-factor with high discrepancy and they settled the case where H is a clique. Here we completely resolve this question by determining the minimum degree threshold for high discrepancy of H-factors for every graph H.
Canonical Ramsey Numbers of Sparse Graphs
Gishboliner, Lior; Milojević, Aleksa; Sudakov, Benny; et al. (2025)
SIAM Journal on Discrete Mathematics
The canonical Ramsey theorem of Erdős and Rado implies that for any graph Η, any edge-coloring (with an arbitrary number of colors) of a sufficiently large complete graph ΚN contains a monochromatic, lexicographic, or rainbow copy of H. The least such N is called the Erdős-Rado number of H, denoted by ER(H). Erdős-Rado numbers of cliques have received considerable attention, and in this paper we extend this line of research by studying Erdős-Rado numbers of sparse graphs. For example, we prove that if H has bounded degree, then ER(H) is polynomial in | V (H)| if H is bipartite but exponential in general. We also study the closely related problem of constrained Ramsey numbers. For a given tree S and given path Pt, we study the minimum N such that every edge-coloring of KN contains a monochromatic copy of S or a rainbow copy of Pt. We prove a nearly optimal upper bound for this problem, which differs from the best known lower bound by a function of inverse Ackermann type.
On Rodl's Theorem for Cographs
Gishboliner, Lior; Shapira, Asaf (2023)
The Electronic Journal of Combinatorics
A theorem of R & ouml;dl states that for every fixed F and epsilon > 0 there is delta = delta(F)(epsilon) so that every induced F-free graph contains a vertex set of size delta n whose edge density is either at most epsilon or at least 1 - epsilon. R & ouml;dl's proof relied on the regularity lemma, hence it supplied only a tower-type bound for delta. Fox and Sudakov conjectured that delta can be made polynomial in epsilon, and a recent result of Fox, Nguyen, Scott and Seymour shows that this conjecture holds when F = P-4. In fact, they show that the same conclusion holds even if G contains few copies of P-4. In this note we give a short proof of a more general statement.
Counting Homomorphic Cycles in Degenerate Graphs
Gishboliner, Lior; Levanzov, Yevgeny; Shapira, Asaf; et al. (2023)
ACM Transactions on Algorithms
Since counting subgraphs in general graphs is, by and large, a computationally demanding problem, it is natural to try and design fast algorithms for restricted families of graphs. One such family that has been extensively studied is that of graphs of bounded degeneracy (e.g., planar graphs). This line of work, which started in the early 80’s, culminated in a recent work of Gishboliner et al., which highlighted the importance of the task of counting homomorphic copies of cycles (i.e., cyclic walks) in graphs of bounded degeneracy. Our main result in this paper is a surprisingly tight relation between the above task and the well-studied problem of detecting (standard) copies of directed cycles in general directed graphs. More precisely, we prove the following: One can compute the number of homomorphic copies of C2k and C2k+1 in n-vertex graphs of bounded degeneracy in time Õ(ndk), where the fastest known algorithm for detecting directed copies of Ck in general m-edge digraphs runs in time Õ(mdk). Conversely, one can transform any O(nbk) algorithm for computing the number of homomorphic copies of C2k or of C2k+1 in n-vertex graphs of bounded degeneracy, into an Õ(mbk) time algorithm for detecting directed copies of Ck in general m-edge digraphs. We emphasize that our first result does not use a black-box reduction (as opposed to the second result which does). Instead, we design an algorithm for computing the number of Ck-homomorphisms in degenerate graphs and show that one part of its analysis can be reduced to the analysis of the fastest known algorithm for detecting directed cycles in general digraphs, which was carried out in a recent breakthrough of Dalirrooyfard, Vuong and Vassilevska Williams. As a by-product of our algorithm, we obtain a new algorithm for detecting k-cycles in directed and undirected graphs of bounded degeneracy that is faster than all previously known algorithms for 7 ≤ k ≤ 11, and faster for all k ≥ 7 if the matrix multiplication exponent is 2.
Counting subgraphs in degenerate graphs
Bera, Suman; Gishboliner, Lior; Shapira, Asaf; et al. (2022)
Journal of the ACM
Oriented Cycles in Digraphs of Large Outdegree
Gishboliner, Lior; Steiner, Raphael; Szabó, Tibor (2022)
Combinatorica
In 1985, Mader conjectured that for every acyclic digraph F there exists K = K(F) such that every digraph D with minimum out-degree at least K contains a subdivision of F. This conjecture remains widely open, even for digraphs F on five vertices. Recently, Aboulker, Cohen, Havet, Lochet, Moura and Thomassé studied special cases of Mader’s problem and made the following conjecture: for every ℓ ≥ 2 there exists K = K(ℓ) such that every digraph D with minimum out-degree at least K contains a subdivision of every orientation of a cycle of length ℓ. We prove this conjecture and answer further open questions raised by Aboulker et al.
An efficient asymmetric removal lemma and its limitations
Gishboliner, Lior; Shapira, Asaf; Wigderson, Yuval (2025)
Forum of Mathematics, Sigma
Cycles of many lengths in Hamiltonian graphs
Bucić, Matija; Gishboliner, Lior; Sudakov, Benny (2022)
Forum of Mathematics, Sigma
In 1999, Jacobson and Lehel conjectured that, for k >= 3, every k-regular Hamiltonian graph has cycles of Theta(n) many different lengths. This was further strengthened by Verstraete, who asked whether the regularity can be replaced with the weaker condition that the minimum degree is at least 3. Despite attention from various researchers, until now, the best partial result towards both of these conjectures was a root n lower bound on the number of cycle lengths. We resolve these conjectures asymptotically by showing that the number of cycle lengths is at least n(1-0(1)).
A characterization of easily testable induced digraphs and k-colored graphs
Gishboliner, Lior (2022)
European Journal of Combinatorics
We complete the characterization of the digraphs D for which the induced D-removal lemma has polynomial bounds, answering a question of Alon and Shapira. We also study the analogous problem for k-colored complete graphs. In particular, we prove a removal lemma with polynomial bounds for Gallai colorings.
Testing versus estimation of graph properties, revisited
Shapira, Asaf; Kushnir, Nick; Gishboliner, Lior (2024)
Random Structures & Algorithms

Publications1 - 10 of 32

Lior Gishboliner

Last Name

First Name

ORCID

Organisational unit

Filters

Search Results