Source author record

Kayla Wright

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO math.AC

Catalog footprint

Research overview

2works

2topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Quivers from non-orientable surfaces

We associate a quiver to a quasi-triangulation of a non-orientable marked surface and define a notion of quiver mutation that is compatible with quasi-cluster algebra mutation defined by Dupont and Palesi. Moreover, we use our quiver to show the unistructurality of the quasi-cluster algebra arising from the Mobius strip.

preprint2016arXiv

Triangulating Almost-Complete Graphs

A triangle decomposition of a graph $G$ is a partition of the edges of $G$ into triangles. Two necessary conditions for $G$ to admit such a decomposition are that $|E(G)|$ is a multiple of three and that the degree of any vertex in $G$ is even; we call such graphs tridivisible. Kirkman's work on Steiner triple systems established that for $G \simeq K_n$ , $G$ admits a triangle decomposition precisely when $G$ is tridivisible. In 1970, Nash-Williams conjectured that tridivisiblity is also sufficient for "almost-complete" graphs, which for this talk's purposes we interpret as any graph $G$ on $n$ vertices with $δ(G) \geq (1 -ε)n, E(G) \geq (1 - ξ)\binom{n}{2}$ for some appropriately small constants $ε, ξ$ . Nash-Williams conjectured that $ε= ξ=1/4$ would suffice; in 1991, Gustavsson demonstrated in his dissertation that $ε= ξ< 10^{-24}$ suffices for all $n \equiv 3, 9 \mod 18$ , and in 2015 Keevash's work on the existence conjecture for combinatorial designs established that some value of $ε$ existed for any $n$ . In this paper, we prove that for any $ε< \frac{1}{432}$ , there is a constant $ξ$ such that any $G$ with $δ(G) \geq (1 - ε)n$ and $|E(G)| \geq (1 - ξ)\binom{n}{2}$ admits such a decomposition, and offer an algorithm that explicitly constructs such a triangulation. Moreover, we note that our algorithm runs in polynomial time on such graphs. (This last observation contrasts with Holyer's result that finding triangle decompositions in general is a NP-complete problem.)

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.