Source author record

Elad Aigner-Horev

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computer Science and Game Theory Data Structures and Algorithms

Catalog footprint

Research overview

13works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Cycle lengths in randomly perturbed graphs

Let $G$ be an $n$ -vertex graph, where $δ(G) \geq δn$ for some $δ:= δ(n)$ . A result of Bohman, Frieze and Martin from 2003 asserts that if $α(G) = O \left(δ^2 n \right)$ , then perturbing $G$ via the addition of $ω\left(\frac{\log(1/δ)}{δ^3} \right)$ random edges, asymptotically almost surely (a.a.s. hereafter) results in a Hamiltonian graph. This bound on the size of the random perturbation is only tight when $δ$ is independent of $n$ and deteriorates as to become uninformative when $δ= Ω\left(n^{-1/3} \right)$ . We prove several improvements and extensions of the aforementioned result. First, keeping the bound on $α(G)$ as above and allowing for $δ= Ω(n^{-1/3})$ , we determine the correct order of magnitude of the number of random edges whose addition to $G$ a.a.s. results in a pancyclic graph. Our second result ventures into significantly sparser graphs $G$ ; it delivers an almost tight bound on the size of the random perturbation required to ensure pancyclicity a.a.s., assuming $δ(G) = Ω\left((α(G) \log n)^2 \right)$ and $α(G) δ(G) = O(n)$ . Assuming the correctness of Chvátal's toughness conjecture, allows for the mitigation of the condition $α(G) = O \left(δ^2 n \right)$ imposed above, by requiring $α(G) = O(δ(G))$ instead; our third result determines, for a wide range of values of $δ(G)$ , the correct order of magnitude of the size of the random perturbation required to ensure the a.a.s. pancyclicity of $G$ . For the emergence of nearly spanning cycles, our fourth result determines, under milder conditions, the correct order of magnitude of the size of the random perturbation required to ensure that a.a.s. $G$ contains such a cycle.

preprint2022arXiv

Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division

A matching in a bipartite graph with parts X and Y is called envy-free if no unmatched vertex in X is a adjacent to a matched vertex in Y. Every perfect matching is envy-free, but envy-free matchings exist even when perfect matchings do not. We prove that every bipartite graph has a unique partition such that all envy-free matchings are contained in one of the partition sets. Using this structural theorem, we provide a polynomial-time algorithm for finding an envy-free matching of maximum cardinality. For edge-weighted bipartite graphs, we provide a polynomial-time algorithm for finding a maximum-cardinality envy-free matching of minimum total weight. We show how envy-free matchings can be used in various fair division problems with either continuous resources ("cakes") or discrete ones. In particular, we propose a symmetric algorithm for proportional cake-cutting, an algorithm for 1-out-of-(2n-2) maximin-share allocation of discrete goods, and an algorithm for 1-out-of-floor(2n/3) maximin-share allocation of discrete bads among n agents.

preprint2022arXiv

Large rainbow cliques in randomly perturbed dense graphs

For two graphs $G$ and $H$ , write $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ if $G$ has the property that every {\sl proper} colouring of its edges yields a {\sl rainbow} copy of $H$ . We study the thresholds for such so-called {\sl anti-Ramsey} properties in randomly perturbed dense graphs, which are unions of the form $G \cup \mathbb{G}(n,p)$ , where $G$ is an $n$ -vertex graph with edge-density at least $d$ , and $d$ is a constant that does not depend on $n$ . Our results in this paper, combined with our results in a companion paper, determine the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} K_s$ for every $s$ . In this paper, we show that for $s \geq 9$ the threshold is $n^{-1/m_2(K_{\left\lceil s/2 \right\rceil})}$ ; in fact, our $1$ -statement is a supersaturation result. This turns out to (almost) be the threshold for $s=8$ as well, but for every $4 \leq s \leq 7$ , the threshold is lower; see our companion paper for more details. In this paper, we also consider the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} C_{2\ell - 1}$ , and show that the threshold for this property is $n^{-2}$ for every $\ell \geq 2$ ; in particular, it does not depend on the length of the cycle $C_{2\ell - 1}$ . It is worth mentioning that for even cycles, or more generally for any fixed bipartite graph, no random edges are needed at all.

preprint2022arXiv

Small rainbow cliques in randomly perturbed dense graphs

For two graphs $G$ and $H$ , write $G \stackrel{\mathrm{rbw}}{\longrightarrow} H$ if $G$ has the property that every \emph{proper} colouring of its edges yields a \emph{rainbow} copy of $H$ . We study the thresholds for such so-called \emph{anti-Ramsey} properties in randomly perturbed dense graphs, which are unions of the form $G \cup \mathbb{G}(n,p)$ , where $G$ is an $n$ -vertex graph with edge-density at least $d >0$ , and $d$ is independent of $n$ . In a companion article, we proved that the threshold for the property $G \cup \mathbb{G}(n,p) \stackrel{\mathrm{rbw}}{\longrightarrow} K_\ell$ is $n^{-1/m_2(K_{\left\lceil \ell/2 \right\rceil})}$ , whenever $\ell \geq 9$ . For smaller $\ell$ , the thresholds behave more erratically, and for $4 \le \ell \le 7$ they deviate downwards significantly from the aforementioned aesthetic form capturing the thresholds for \emph{large} cliques. In particular, we show that the thresholds for $\ell \in \{4, 5, 7\}$ are $n^{-5/4}$ , $n^{-1}$ , and $n^{-7/15}$ , respectively. For $\ell \in \{6, 8\}$ we determine the threshold up to a $(1 + o(1))$ -factor in the exponent: they are $n^{-(2/3 + o(1))}$ and $n^{-(2/5 + o(1))}$ , respectively. For $\ell = 3$ , the threshold is $n^{-2}$ ; this follows from a more general result about odd cycles in our companion paper.

preprint2020arXiv

Rainbow Hamilton cycles in randomly coloured randomly perturbed dense graphs

Given an $n$ -vertex graph $G$ with minimum degree at least $d n$ for some fixed $d > 0$ , the distribution $G \cup \mathbb{G}(n,p)$ over the supergraphs of $G$ is referred to as a (random) {\sl perturbation} of $G$ . We consider the distribution of edge-coloured graphs arising from assigning each edge of the random perturbation $G \cup \mathbb{G}(n,p)$ a colour, chosen independently and uniformly at random from a set of colours of size $r := r(n)$ . We prove that such edge-coloured graph distributions a.a.s. admit rainbow Hamilton cycles whenever the edge-density of the random perturbation satisfies $p := p(n) \geq C/n$ , for some fixed $C > 0$ , and $r = (1 + o(1))n$ . The number of colours used is clearly asymptotically best possible. In particular, this improves upon a recent result of Anastos and Frieze (2019) in this regard. As an intermediate result, which may be of independent interest, we prove that randomly edge-coloured sparse pseudo-random graphs a.a.s. admit an almost spanning rainbow path.

preprint2016arXiv

Extremal results for odd cycles in sparse pseudorandom graphs

We consider extremal problems for subgraphs of pseudorandom graphs. For graphs $F$ and $Γ$ the generalized Turán density $π_F(Γ)$ denotes the density of a maximum subgraph of $Γ$ , which contains no copy of~ $F$ . Extending classical Turán type results for odd cycles, we show that $π_{F}(Γ)=1/2$ provided $F$ is an odd cycle and $Γ$ is a sufficiently pseudorandom graph. In particular, for $(n,d,λ)$ -graphs $Γ$ , i.e., $n$ -vertex, $d$ -regular graphs with all non-trivial eigenvalues in the interval $[-λ,λ]$ , our result holds for odd cycles of length $\ell$ , provided $λ^{\ell-2}\ll \frac{d^{\ell-1}}n\log(n)^{-(\ell-2)(\ell-3)}\,.$ Up to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szabó, and Vu, who addressed the case when $F$ is a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free $(n,d,λ)$ -graphs) shows that our assumption on $Γ$ is best possible up to the polylog-factor for every odd $\ell\geq 5$ .

preprint2015arXiv

The structure of 2-separations of infinite matroids

Generalizing a well known theorem for finite matroids, we prove that for every (infinite) connected matroid M there is a unique tree T such that the nodes of T correspond to minors of M that are either 3-connected or circuits or cocircuits, and the edges of T correspond to certain nested 2-separations of M. These decompositions are invariant under duality.

preprint2012arXiv

Infinite matroid union

We consider the problem of determining whether the union of two infinite matroids is a matroid. We introduce a superclass of the finitary matroids, the nearly finitary matroids, and prove that the union of two nearly finitary matroids is a nearly finitary matroid. On the other hand, we prove that the union of two arbitrary infinite matroids is not necessarily a matroid. Indeed, we show (under a weak additional assumption) that the nearly finitary matroids are essentially the largest class of matroids for which one can have a union theorem. We then extend the base packing theorem for finite matroids to finite families of co-finitary matroids. This, in turn, yields a matroidal proof for the tree-packing results for infinite graphs due to Diestel and Tutte.

preprint2012arXiv

On the intersection of infinite matroids

We show that the infinite matroid intersection conjecture of Nash-Williams implies the infinite Menger theorem proved recently by Aharoni and Berger. We prove that this conjecture is true whenever one matroid is nearly finitary and the second is the dual of a nearly finitary matroid, where the nearly finitary matroids form a superclass of the finitary matroids. In particular, this proves the infinite matroid intersection conjecture for finite-cycle matroids of 2-connected, locally finite graphs with only a finite number of vertex-disjoint rays.

preprint2010arXiv

Almost Series-Parallel graphs: structure and colorability

The series-parallel (SP) graphs are those containing no topological $K_{_4}$ and are considered trivial. We relax the prohibition distinguishing the SP graphs by forbidding only embeddings of $K_{_4}$ whose edges with both ends 3-valent (skeleton hereafter) induce a graph isomorphic to certain prescribed subgraphs of $K_{_4}$ . In particular, we describe the structure of the graphs containing no embedding of $K_{_4}$ whose skeleton is isomorphic to $P_{_3}$ or $P_{_4}$ . Such "almost series-parallel graphs" (ASP) still admit a concise description. Amongst other things, their description reveals that: 1. Essentially, the 3-connected ASP graphs are those obtained from the 3-connected cubic graphs by replacing each vertex with a triangle (e.g., the 3-connected claw-free graphs). 2. Except for $K_{_6}$ , the ASP graphs are 5-colorable in polynomial time. Distinguishing between the 5-chromatic and the 4-colorable ASP graphs is $NP$ -hard. 3. The ASP class is significantly richer than the SP class: 4-vertex-colorability, 3-edge-colorability, and Hamiltonicity are $NP$ -hard for ASP graphs. Our interest in such ASP graphs arises from a previous paper of ours: "{\sl On the colorability of graphs with forbidden minors along paths and circuits}, Discrete Math. (to appear)".

preprint2010arXiv

Extremal results regarding $K_6$ -minors in graphs of girth at least 5

We prove that every 6-connected graph of girth $\geq 6$ has a $K_6$ -minor and thus settle the Jorgensen conjecture for graphs of girth $\geq 6$ . Relaxing the assumption on the girth, we prove that every 6-connected $n$ -vertex graph of size $\geq 3 1/5 n-8$ and of girth $\geq 5$ contains a $K_6$ -minor.

preprint2010arXiv

Subdivisions in apex graphs

The Kelmans-Seymour conjecture states that the 5-connected nonplanar graphs contain a subdivided $K_{_5}$ . Certain questions of Mader propose a "plan" towards a possible resolution of this conjecture. One part of this plan is to show that a 5-connected nonplanar graph containing $K^-_{_4}$ or $K_{_{2,3}}$ as a subgraph has a subdivided $K_{_5}$ . Recently, Ma and Yu showed that a 5-connected nonplanar graph containing $K^-_{_4}$ as a subgraph has a subdivided $K_{_5}$ . We take interest in $K_{_{2,3}}$ and prove that a 5-connected nonplanar apex graph containing $K_{_{2,3}}$ as a subgraph has a subdivided $K_{_5}$

preprint2010arXiv

The Kelmans-Seymour conjecture for apex graphs

We provide a short proof that a 5-connected nonplanar apex graph contains a subdivided $K_{_5}$ or a $K^-_{_4}$ (= $K_{_4}$ with a single edge removed) as a subgraph. Together with a recent result of Ma and Yu that {\sl every nonplanar 5-connected graph containing $K^-_{_4}$ as a subgraph has a subdivided $K_{_5}$ }; this settles the Kelmans-Seymour conjecture for apex graphs.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Elad Aigner-Horev

Research overview

Is this your work?

13 publications

Cycle lengths in randomly perturbed graphs

Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division

Large rainbow cliques in randomly perturbed dense graphs

Small rainbow cliques in randomly perturbed dense graphs

Rainbow Hamilton cycles in randomly coloured randomly perturbed dense graphs

Extremal results for odd cycles in sparse pseudorandom graphs

The structure of 2-separations of infinite matroids

Infinite matroid union

On the intersection of infinite matroids

Almost Series-Parallel graphs: structure and colorability

Extremal results regarding $K_6$ -minors in graphs of girth at least 5

Subdivisions in apex graphs

The Kelmans-Seymour conjecture for apex graphs

See the researcher in context

Building this map preview

Elad Aigner-Horev

Research overview

Is this your work?

13 publications

Cycle lengths in randomly perturbed graphs

Envy-free Matchings in Bipartite Graphs and their Applications to Fair Division

Large rainbow cliques in randomly perturbed dense graphs

Small rainbow cliques in randomly perturbed dense graphs

Rainbow Hamilton cycles in randomly coloured randomly perturbed dense graphs

Extremal results for odd cycles in sparse pseudorandom graphs

The structure of 2-separations of infinite matroids

Infinite matroid union

On the intersection of infinite matroids

Almost Series-Parallel graphs: structure and colorability

Extremal results regarding K6K_6K6​-minors in graphs of girth at least 5

Subdivisions in apex graphs

The Kelmans-Seymour conjecture for apex graphs

See the researcher in context

Building this map preview

Extremal results regarding $K_6$ -minors in graphs of girth at least 5