اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدGraphs of low average degree without independent transversals
299
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 the average degree of vertices in each block is at most $t/4$, then an independent transversal of $mathcal P$ exists. We present a construction showing that this result is optimal: for any $varepsilon > 0$ and sufficiently large $t$, there is a family of forests with vertex partitions whose block size is at least $t$, average degree of vertices in each block is at most $(frac14+varepsilon)t$, and there is no independent transversal. This unexpectedly shows that methods related to entropy compression such as the Rosenfeld-Wanles-Wood scheme or the Local Cut Lemma are tight for this problem. Further constructions are given for variants of the problem, including the hypergraph version.
قيم البحث
اقرأ أيضاً
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 trans
versal? 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.
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
s, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.
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
hat (i) $f_G(n,n-1)=n-1$ for all graphs $Ginmathcal{D}(2)$ and (ii) $f_{C_t}(n,n)=n$ for $tge 2n+1$. Lv and Lu (2020) showed that the conjecture (ii) holds when $t=2n+1$. In this article, we show that the conjecture (ii) holds for $tgefrac{1}{3}n^2+frac{44}{9}n$. Let $C_t$ be a cycle of length $t$ with vertices being arranged in a clockwise order. An ordered set $I=(a_1,a_2,ldots,a_n)$ on $C_t$ is called a $2$-jump independent $n$-set of $C_t$ if $a_{i+1}-a_i=2pmod{t}$ for any $1le ile n-1$. We also show that a collection of 2-jump independent $n$-sets $mathcal{F}$ of $C_t$ with $|mathcal{F}|=n$ admits a rainbow independent $n$-set, i.e. (ii) holds if we restrict $mathcal{F}$ on the family of 2-jump independent $n$-sets. Moreover, we prove that if the conjecture (ii) holds, then (i) holds for all graphs $Ginmathcal{D}(2)$ with $c_e(G)le 4$, where $c_e(G)$ is the number of components of $G$ isomorphic to cycles of even lengths.
We prove an asymptotically tight lower bound on the average size of independent sets in a triangle-free graph on $n$ vertices with maximum degree $d$, showing that an independent set drawn uniformly at random from such a graph has expected size at le
ast $(1+o_d(1)) frac{log d}{d}n$. This gives an alternative proof of Shearers upper bound on the Ramsey number $R(3,k)$. We then prove that the total number of independent sets in a triangle-free graph with maximum degree $d$ is at least $exp left[left(frac{1}{2}+o_d(1) right) frac{log^2 d}{d}n right]$. The constant $1/2$ in the exponent is best possible. In both cases, tightness is exhibited by a random $d$-regular graph. Both results come from considering the hard-core model from statistical physics: a random independent set $I$ drawn from a graph with probability proportional to $lambda^{|I|}$, for a fugacity parameter $lambda>0$. We prove a general lower bound on the occupancy fraction (normalized expected size of the random independent set) of the hard-core model on triangle-free graphs of maximum degree $d$. The bound is asymptotically tight in $d$ for all $lambda =O_d(1)$. We conclude by stating several conjectures on the relationship between the average and maximum size of an independent set in a triangle-free graph and give some consequences of these conjectures in Ramsey theory.
A rainbow matching in an edge-colored graph is a matching in which no two edges have the same color. The color degree of a vertex v is the number of different colors on edges incident to v. Kritschgau [Electron. J. Combin. 27(2020)] studied the exist
ence of rainbow matchings in edge-colored graph G with average color degree at least 2k, and proved some sufficient conditions for a rainbow marching of size k in G. The sufficient conditions include that |V(G)|>=12k^2+4k, or G is a properly edge-colored graph with |V(G)|>=8k. In this paper, we show that every edge-colored graph G with |V(G)|>=4k-4 and average color degree at least 2k-1 contains a rainbow matching of size k. In addition, we also prove that every strongly edge-colored graph G with average degree at least 2k-1 contains a rainbow matching of size at least k. The bound is sharp for complete graphs.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
