Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userBishellable drawings of $K_n$
146
0
0.0
(
0
)
Added by
Birgit Vogtenhuber
Publication date
2015
fields
Informatics Engineering
and research's language is
English
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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 drawings 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 for 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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
