ﻻ يوجد ملخص باللغة العربية
In 1994, ErdH{o}s, Gy{a}rf{a}s and {L}uczak posed the following problem: given disjoint vertex sets $V_1,dots,V_n$ of size~$k$, with exactly one edge between any pair $V_i,V_j$, how large can $n$ be such that there will always be an independent transversal? They showed that the maximal $n$ is at most $(1+o(1))k^2$, by providing an explicit construction with these parameters and no independent transversal. They also proved a lower bound which is smaller by a $2e$-factor. In this paper, we solve this problem by showing that their upper bound construction is best possible: if $nle (1-o(1))k^2$, there will always be an independent transversal. In fact, this result is a very special case of a much more general theorem which concerns independent transversals in arbitrary partite graphs that are `locally sparse, meaning that the maximum degree between each pair of parts is relatively small. In this setting, Loh and Sudakov provided a global emph{maximum} degree condition for the existence of an independent transversal. We show that this can be relaxed to an emph{average} degree condition. We can also use our new theorem to establish tight bounds for a more general version of the ErdH{o}s--Gy{a}rf{a}s--{L}uczak problem and solve a conjecture of Yuster from 1997. This exploits a connection to the Turan numbers of complete bipartite graphs, which might be of independent interest. Finally, we discuss some partial results on the hypergraph variant of the problem, and formulate a conjecture in this case.
An independent transversal of a graph $G$ with a vertex partition $mathcal P$ is an independent set of $G$ intersecting each block of $mathcal P$ in a single vertex. Wanless and Wood proved that if each block of $mathcal P$ has size at least $t$ and
Motivated by a longstanding conjecture of Thomassen, we study how large the average degree of a graph needs to be to imply that it contains a $C_4$-free subgraph with average degree at least $t$. Kuhn and Osthus showed that an average degree bound wh
We consider numbers and sizes of independent sets in graphs with minimum degree at least $d$, when the number $n$ of vertices is large. In particular we investigate which of these graphs yield the maximum numbers of independent sets of different size
Given a graph $G$, let $f_{G}(n,m)$ be the minimal number $k$ such that every $k$ independent $n$-sets in $G$ have a rainbow $m$-set. Let $mathcal{D}(2)$ be the family of all graphs with maximum degree at most two. Aharoni et al. (2019) conjectured t
ErdH{o}s posed the problem of finding conditions on a graph $G$ that imply the largest number of edges in a triangle-free subgraph is equal to the largest number of edges in a bipartite subgraph. We generalize this problem to general cases. Let $delt