Source author record

Eli Berger

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

9works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Fractionally balanced hypergraphs and rainbow KKM theorems

A d-partite hypergraph is called *fractionally balanced* if there exists a non-negative, not identically zero, function on its edge set that has constant degrees in each vertex side. Using a topological version of Hall's theorem we prove lower bounds on the matching number of such hypergraphs. These bounds yield rainbow versions of the KKM theorem for products of simplices, which in turn are used to obtain some results on multiple-cake division, and on rainbow matchings in families of d-intervals.

preprint2020arXiv

Cooperative colorings of trees and of bipartite graphs

Given a system $(G_1, \ldots ,G_m)$ of graphs on the same vertex set $V$ , a cooperative coloring is a choice of vertex sets $I_1, \ldots ,I_m$ , such that $I_j$ is independent in $G_j$ and $\bigcup_{j=1}^{m}I_j = V$ . For a class $\mathcal{G}$ of graphs, let $m_{\mathcal{G}}(d)$ be the minimal $m$ such that every $m$ graphs from $\mathcal{G}$ with maximum degree $d$ have a cooperative coloring. We prove that $Ω(\log\log d) \le m_\mathcal{T}(d) \le O(\log d)$ and $Ω(\log d)\le m_\mathcal{B}(d) \le O(d/\log d)$ , where $\mathcal{T}$ is the class of trees and $\mathcal{B}$ is the class of bipartite graphs.

preprint2020arXiv

Finding an induced path that is not a shortest path

We give a polynomial-time algorithm that, with input a graph $G$ and two vertices $u,v$ of $G$ , decides whether there is an induced $uv$ -path that is longer than the shortest $uv$ -path.

preprint2016arXiv

Degree conditions for matchability in $3$ -partite hypergraphs

We study conjectures relating degree conditions in $3$ -partite hypergraphs to the matching number of the hypergraph, and use topological methods to prove special cases. In particular, we prove a strong version of a theorem of Drisko \cite{drisko} (as generalized by the first two authors \cite{ab}), that every family of $2n-1$ matchings of size $n$ in a bipartite graph has a partial rainbow matching of size $n$ . We show that milder restrictions on the sizes of the matchings suffice. Another result that is strengthened is a theorem of Cameron and Wanless \cite{CamWan}, that every Latin square has a diagonal (permutation submatrix) in which no symbol appears more than twice. We show that the same is true under the weaker condition that the square is row-Latin.

preprint2016arXiv

Fair representation by independent sets

For a hypergraph $H$ let $β(H)$ denote the minimal number of edges from $H$ covering $V(H)$ . An edge $S$ of $H$ is said to represent {\em fairly} (resp. {\em almost fairly}) a partition $(V_1,V_2, \ldots, V_m)$ of $V(H)$ if $|S\cap V_i|\ge \lfloor\frac{|V_i|}{β(H)}\rfloor$ (resp. $|S\cap V_i|\ge \lfloor\frac{|V_i|}{β(H)}\rfloor-1$ ) for all $i \le m$ . In matroids any partition of $V(H)$ can be represented fairly by some independent set. We look for classes of hypergraphs $H$ in which any partition of $V(H)$ can be represented almost fairly by some edge. We show that this is true when $H$ is the set of independent sets in a path, and conjecture that it is true when $H$ is the set of matchings in $K_{n,n}$ . We prove that partitions of $E(K_{n,n})$ into three sets can be represented almost fairly. The methods of proofs are topological.

preprint2016arXiv

On a conjecture of Stein

Stein proposed the following conjecture: if the edge set of $K_{n,n}$ is partitioned into $n$ sets, each of size $n$ , then there is a partial rainbow matching of size $n-1$ . He proved that there is a partial rainbow matching of size $n(1-\frac{D_n}{n!})$ , where $D_n$ is the number of derangements of $[n]$ . This means that there is a partial rainbow matching of size about $(1- \frac{1}{e})n$ . Using a topological version of Hall's theorem we improve this bound to $\frac{2}{3}n$ .

preprint2015arXiv

Cliques in the union of $C_4$ -free graphs

Let $B$ and $R$ be two simple graphs with vertex set $V$ , and let $G(B,R)$ be the simple graph with vertex set $V$ , in which two vertices are adjacent if they are adjacent in at least one of $B$ and $R$ . We prove that if $B$ and $R$ are two $C_4$ -free graphs on the same vertex set $V$ and $G(B,R)$ is the complete graph, then there exists an $B$ -clique $X$ , an $R$ -clique $Y$ and a clique $Z$ in $B$ and $R$ , such that $V=X\cup Y\cup Z$ . Further, if $x\in Z$ then $x$ is one of the vertices of some double $C_5$ in $G(B,R)$ . In particular, if also $G(B,R)$ does not contains a double $C_5$ , then $V$ is obedient. We obtain that if $B$ and $R$ are $C_4$ -free graphs then $ω(G(B,R))\leq ω(B)+ω(R)+\frac{1}{2}\min(ω(B),ω(R))$ and $ω(G(B,R))\leq ω(B)+ω(R)+ω(H(B,R))$ where $H(B,R)$ is the simple graph with vertex set $V$ , in which two vertices are adjacent if they are adjacent in $B$ and $R$ .

preprint2015arXiv

On the Erdős-Hajnal conjecture for six-vertex tournaments

A celebrated unresolved conjecture of Erdős and Hajnal states that for every undirected graph $H$ there exists $ε(H)>0$ such that every undirected graph on $n$ vertices that does not contain $H$ as an induced subgraph contains a clique or stable set of size at least $n^{ε(H)}$ . The conjecture has a directed equivalent version stating that for every tournament $H$ there exists $ε(H)>0$ such that every $H$ -free $n$ -vertex tournament $T$ contains a transitive subtournament of order at least $n^{ε(H)}$ . We say that a tournament is \textit{prime} if it does not have nontrivial homogeneous sets. So far the conjecture was proved only for some specific families of prime tournaments (\cite{chorochudber, choromanski2}) and tournaments constructed according to the so-called \textit{substitution procedure}(\cite{alon}). In particular, recently the conjecture was proved for all five-vertex tournaments (\cite{chorochudber}), but the question about the correctness of the conjecture for all six-vertex tournaments remained open. In this paper we prove that all but at most one six-vertex tournament satisfy the Erdős-Hajnal conjecture. That reduces the six-vertex case to a single tournament.

preprint2015arXiv

Treewidth of grid subsets

Let Q_n be the graph of n times n times n cube with all non-decreasing diagonals (including the facial ones) in its constituent unit cubes. Suppose that a subset S of V(Q_n) separates the left side of the cube from the right side. We show that S induces a subgraph of tree-width at least n/sqrt{18}-1. We use a generalization of this claim to prove that the vertex set of Q_n cannot be partitioned to two parts, each of them inducing a subgraph of bounded tree-width.

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.

Eli Berger

Research overview

Is this your work?

9 publications

Fractionally balanced hypergraphs and rainbow KKM theorems

Cooperative colorings of trees and of bipartite graphs

Finding an induced path that is not a shortest path

Degree conditions for matchability in $3$ -partite hypergraphs

Fair representation by independent sets

On a conjecture of Stein

Cliques in the union of $C_4$ -free graphs

On the Erdős-Hajnal conjecture for six-vertex tournaments

Treewidth of grid subsets

See the researcher in context

Building this map preview

Eli Berger

Research overview

Is this your work?

9 publications

Fractionally balanced hypergraphs and rainbow KKM theorems

Cooperative colorings of trees and of bipartite graphs

Finding an induced path that is not a shortest path

Degree conditions for matchability in 333-partite hypergraphs

Fair representation by independent sets

On a conjecture of Stein

Cliques in the union of C4C_4C4​-free graphs

On the Erdős-Hajnal conjecture for six-vertex tournaments

Treewidth of grid subsets

See the researcher in context

Building this map preview

Degree conditions for matchability in $3$ -partite hypergraphs

Cliques in the union of $C_4$ -free graphs