اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدBishellable drawings of $K_n$
146
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Harary--Hill conjecture, still open after more than 50 years, asserts that the crossing number of the complete graph $K_n$ is $ H(n) = frac 1 4 leftlfloorfrac{mathstrut n}{mathstrut 2}rightrfloor leftlfloorfrac{mathstrut n-1}{mathstrut 2}rightrfloor leftlfloorfrac{mathstrut n-2}{mathstrut 2}rightrfloor leftlfloorfrac{mathstrut n-3}{mathstrut 2}right rfloor$. Abrego et al. introduced the notion of shellability of a drawing $D$ of $K_n$. They proved that if $D$ is $s$-shellable for some $sgeqlfloorfrac{n}{2}rfloor$, then $D$ has at least $H(n)$ crossings. This is the first combinatorial condition on a drawing that guarantees at least $H(n)$ crossings. In this work, we generalize the concept of $s$-shellability to bishellability, where the former implies the latter in the sense that every $s$-shellable drawing is, for any $b leq s-2$, also $b$-bishellable. Our main result is that $(lfloor frac{n}{2} rfloor!-!2)$-bishellability of a drawing $D$ of $K_n$ also guarantees, with a simpler proof than for $s$-shellability, that $D$ has at least $H(n)$ crossings. We exhibit a drawing of $K_{11}$ that has $H(11)$ crossings, is 3-bishellable, and is not $s$-shellable for any $sgeq5$. This shows that we have properly extended the class of drawings for which the Harary-Hill Conjecture is proved. Moreover, we provide an infinite family of drawings of $K_n$ that are $(lfloor frac{n}{2} rfloor!-!2)$-bishellable, but not $s$-shellable for any $sgeqlfloorfrac{n}{2}rfloor$.
قيم البحث
اقرأ أيضاً
In studying properties of simple drawings of the complete graph in the sphere, two natural questions arose for us: can an edge have multiple segments on the boundary of the same face? and is each face the intersection of sides of 3-cycles? The second
is asserted to be obvious in two previously published articles, but when asked, authors of both papers were unable to provide a proof. We present a proof. The first is quite easily proved and the technique yields a third, even simpler, fact: no three edges at a vertex all have internal points incident with the same face.
Motivated by the successful application of geometry to proving the Harary-Hill Conjecture for pseudolinear drawings of $K_n$, we introduce pseudospherical drawings of graphs. A spherical drawing of a graph $G$ is a drawing in the unit sphere $mathbb{
S}^2$ in which the vertices of $G$ are represented as points -- no three on a great circle -- and the edges of $G$ are shortest-arcs in $mathbb{S}^2$ connecting pairs of vertices. Such a drawing has three properties: (1) every edge $e$ is contained in a simple closed curve $gamma_e$ such that the only vertices in $gamma_e$ are the ends of $e$; (2) if $e e f$, then $gamma_ecapgamma_f$ has precisely two crossings; and (3) if $e e f$, then $e$ intersects $gamma_f$ at most once, either in a crossing or an end of $e$. We use Properties (1)--(3) to define a pseudospherical drawing of $G$. Our main result is that, for the complete graph, Properties (1)--(3) are equivalent to the same three properties but with precisely two crossings in (2) replaced by at most two crossings. The proof requires a result in the geometric transversal theory of arrangements of pseudocircles. This is proved using the surprising result that the absence of special arcs ( coherent spirals) in an arrangement of simple closed curves characterizes the fact that any two curves in the arrangement have at most two crossings. Our studies provide the necessary ideas for exhibiting a drawing of $K_{10}$ that has no extension to an arrangement of pseudocircles and a drawing of $K_9$ that does extend to an arrangement of pseudocircles, but no such extension has all pairs of pseudocircles crossing twice.
K{a}rolyi, Pach, and T{o}th proved that every 2-edge-colored straight-line drawing of the complete graph contains a monochromatic plane spanning tree. It is open if this statement generalizes to other classes of drawings, specifically, to simple draw
ings of the complete graph. These are drawings where edges are represented by Jordan arcs, any two of which intersect at most once. We present two partial results towards such a generalization. First, we show that the statement holds for cylindrical simple drawings. (In a cylindrical drawing, all vertices are placed on two concentric circles and no edge crosses either circle.) Second, we introduce a relaxation of the problem in which the graph is $k$-edge-colored, and the target structure must be hypochromatic, that is, avoid (at least) one color class. In this setting, we show that every $lceil (n+5)/6rceil$-edge-colored monotone simple drawing of $K_n$ contains a hypochromatic plane spanning tree. (In a monotone drawing, every edge is represented as an $x$-monotone curve.)
In 2015 Bloom and Liebenau proved that $K_n$ and $K_n+K_{n-1}$ possess the same $2$-Ramsey graphs for all $ngeq 3$ (with a single exception for $n=3$). In the following we give a simple proof that $K_n$ and $K_n+K_{n-1}$ possess the same $r$-Ramsey graphs for all $n, rgeq 3$.
Waiter-Client games are played on some hypergraph $(X,mathcal{F})$, where $mathcal{F}$ denotes the family of winning sets. For some bias $b$, during each round of such a game Waiter offers to Client $b+1$ elements of $X$, of which Client claims one f
or himself while the rest go to Waiter. Proceeding like this Waiter wins the game if she forces Client to claim all the elements of any winning set from $mathcal{F}$. In this paper we study fast strategies for several Waiter-Client games played on the edge set of the complete graph, i.e. $X=E(K_n)$, in which the winning sets are perfect matchings, Hamilton cycles, pancyclic graphs, fixed spanning trees or factors of a given graph.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
