اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدTilings in graphons
69
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
We introduce a counterpart to the notion of vertex disjoint tilings by copy of a fixed graph F to the setting of graphons. The case F=K_2 gives the notion of matchings in graphons. We give a transference statement that allows us to switch between the finite and limit notion, and derive several favorable properties, including the LP-duality counterpart to the classical relation between the fractional vertex covers and fractional matchings/tilings, and discuss connections with property testing. As an application of our theory, we determine the asymptotically almost sure F-tiling number of inhomogeneous random graphs mathbb{G}(n,W). As another application, in an accompanying paper [Hladky, Hu, Piguet: Komloss tiling theorem via graphon covers, preprint] we give a proof of a strengthening of a theorem of Komlos [Komlos: Tiling Turan Theorems, Combinatorica, 2000].
قيم البحث
اقرأ أيضاً
We determine the asymptotic behaviour of the chromatic number of exchangeable random graphs defined by step-regulated graphons. Furthermore, we show that the upper bound holds for a general graphon. We also extend these results to sparse random graphs obtained by percolations on graphons.
A combinatorial substitution is a map over tilings which allows to define sets of tilings with a strong hierarchical structure. In this paper, we show that such sets of tilings are sofic, that is, can be enforced by finitely many local constraints. T
his extends some similar previous results (Mozes90, Goodman-Strauss98) in a much shorter presentation.
For a $k$-vertex graph $F$ and an $n$-vertex graph $G$, an $F$-tiling in $G$ is a collection of vertex-disjoint copies of $F$ in $G$. For $rin mathbb{N}$, the $r$-independence number of $G$, denoted $alpha_r(G)$ is the largest size of a $K_r$-free se
t of vertices in $G$. In this paper, we discuss Ramsey--Turan-type theorems for tilings where one is interested in minimum degree and independence number conditions (and the interaction between the two) that guarantee the existence of optimal $F$-tilings. For cliques, we show that for any $kgeq 3$ and $eta>0$, any graph $G$ on $n$ vertices with $delta(G)geq eta n$ and $alpha_k(G)=o(n)$ has a $K_k$-tiling covering all but $lfloortfrac{1}{eta}rfloor(k-1)$ vertices. All conditions in this result are tight; the number of vertices left uncovered can not be improved and for $eta<tfrac{1}{k}$, a condition of $alpha_{k-1}(G)=o(n)$ would not suffice. When $eta>tfrac{1}{k}$, we then show that $alpha_{k-1}(G)=o(n)$ does suffice, but not $alpha_{k-2}(G)=o(n)$. These results unify and generalise previous results of Balogh-Molla-Sharifzadeh, Nenadov-Pehova and Balogh-McDowell-Molla-Mycroft on the subject. We further explore the picture when $F$ is a tree or a cycle and discuss the effect of replacing the independence number condition with $alpha^*(G)=o(n)$ (meaning that any pair of disjoint linear sized sets induce an edge between them) where one can force perfect $F$-tilings covering all the vertices. Finally we discuss the consequences of these results in the randomly perturbed setting.
A semi-regular tiling of the hyperbolic plane is a tessellation by regular geodesic polygons with the property that each vertex has the same vertex-type, which is a cyclic tuple of integers that determine the number of sides of the polygons surroundi
ng the vertex. We determine combinatorial criteria for the existence, and uniqueness, of a semi-regular tiling with a given vertex-type, and pose some open questions.
Let $vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph on $n=4m$ vertices with minimum total degree $(11/12+o(1))n$ can be partitioned into vertex disjoint $vec{T}_4$s, and this bound is asymptotically tight. W
e also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint $vec{T}_k$s.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
