اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدRegular partitions of gentle graphs
81
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Szemeredis Regularity Lemma is a very useful tool of extremal combinatorics. Recently, several refinements of this seminal result were obtained for special, more structured classes of graphs. We survey these results in their rich combinatorial context. In particular, we stress the link to the theory of (structural) sparsity, which leads to alternative proofs, refinements and solutions of open problems. It is interesting to note that many of these classes present challenging problems. Nevertheless, from the point of view of regularity lemma type statements, they appear as gentle classes.
قيم البحث
اقرأ أيضاً
A star $k$-coloring is a proper $k$-coloring where the union of two color classes induces a star forest. While every planar graph is 4-colorable, not every planar graph is star 4-colorable. One method to produce a star 4-coloring is to partition the
vertex set into a 2-independent set and a forest; such a partition is called an I,F-partition. We use a combination of potential functions and discharging to prove that every graph with maximum average degree less than $frac{5}{2}$ has an I,F-partition, which is sharp and answers a question of Cranston and West [A guide to the discharging method, arXiv:1306.4434]. This result implies that planar graphs of girth at least 10 are star 4-colorable, improving upon previous results of Bu, Cranston, Montassier, Raspaud, and Wang [Star coloring of sparse graphs, J. Graph Theory 62 (2009), 201-219].
Switches are operations which make local changes to the edges of a graph, usually with the aim of preserving the vertex degrees. We study a restricted set of switches, called triangle switches. Each triangle switch creates or deletes at least one tri
angle. Triangle switches can be used to define Markov chains which generate graphs with a given degree sequence and with many more triangles (3-cycles) than is typical in a uniformly random graph with the same degrees. We show that the set of triangle switches connects the set of all $d$-regular graphs on $n$ vertices, for all $dgeq 3$. Hence, any Markov chain which assigns positive probability to all triangle switches is irreducible on these graphs. We also investigate this question for 2-regular graphs.
The Ising antiferromagnet is an important statistical physics model with close connections to the {sc Max Cut} problem. Combining spatial mixing arguments with the method of moments and the interpolation method, we pinpoint the replica symmetry break
ing phase transition predicted by physicists. Additionally, we rigorously establish upper bounds on the {sc Max Cut} of random regular graphs predicted by Zdeborova and Boettcher [Journal of Statistical Mechanics 2010]. As an application we prove that the information-theoretic threshold of the disassortative stochastic block model on random regular graphs coincides with the Kesten-Stigum bound.
In this paper, we give a new lifting construction of hyperbolic type of strongly regular Cayley graphs. Also we give new constructions of strongly regular Cayley graphs over the additive groups of finite fields based on partitions of subdifference se
ts of the Singer difference sets. Our results unify some recent constructions of strongly regular Cayley graphs related to $m$-ovoids and $i$-tight sets in finite geometry. Furthermore, some of the strongly regular Cayley graphs obtained in this paper are new or nonisomorphic to known strongly regular graphs with the same parameters.
A seminal theorem of Tverberg states that any set of $T(r,d)=(r-1)(d+1)+1$ points in $mathbb{R}^d$ can be partitioned into $r$ subsets whose convex hulls have non-empty $r$-fold intersection. Almost any collection of fewer points in $mathbb{R}^d$ can
not be so divided, and in these cases we ask if the set can nonetheless be $P(r,d)$--partitioned, i.e., split into $r$ subsets so that there exist $r$ points, one from each resulting convex hull, which form the vertex set of a prescribed convex $d$--polytope $P(r,d)$. Our main theorem shows that this is the case for any generic $T(r,2)-2$ points in the plane and any $rgeq 3$ when $P(r,2)=P_r$ is a regular $r$--gon, and moreover that $T(r,2)-2$ is tight. For higher dimensional polytopes and $r=r_1cdots r_k$, $r_i geq 3$, this generalizes to $T(r,2k)-2k$ generic points in $mathbb{R}^{2k}$ and orthogonal products $P(r,2k)=P_{r_1}times cdots times P_{r_k}$ of regular polygons, and likewise to $T(2r,2k+1)-(2k+1)$ points in $mathbb{R}^{2k+1}$ and the product polytopes $P(2r,2k+1)=P_{r_1}times cdots times P_{r_k} times P_2$. As with Tverbergs original theorem, our results admit topological generalizations when $r$ is a prime power, and, using the constraint method of Blagojevic, Frick, and Ziegler, allow for dimensionally restrict
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
