Source author record

Matthew Yancey

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

ResearcherUnclaimed source record

math.CO Discrete Mathematics Machine Learning Social and Information Networks

Catalog footprint

Research overview

10works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Bipartite Communities

For a given graph, $G$ , let $A$ be the adjacency matrix, $D$ is the diagonal matrix of degrees, $L' = D - A$ is the combinatorial Laplacian, and $L = D^{-1/2}L'D^{-1/2}$ is the normalized Laplacian. Recently, the eigenvectors corresponding to the smallest eigenvalues of $L$ and $L'$ have been of great interest because of their application to community detection, which is a nebulously defined problem that essentially seeks to find a vertex set $S$ such that there are few edges incident with exactly one vertex of $S$ . The connection between community detection and the second smallest eigenvalue (and the corresponding eigenvector) is well-known. The $k$ smallest eigenvalues have been used heuristically to find multiple communities in the same graph, and a justification with theoretical rigor for the use of $k \geq 3$ eigenpairs has only been found very recently. The largest eigenpair of $L$ has been used more classically to solve the MAX-CUT problem, which seeks to find a vertex set $S$ that maximizes the number of edges incident with exactly one vertex of $S$ . Very recently Trevisan presented a connection between the largest eigenvalue of $L$ and a recursive approach to the MAX-CUT problem that seeks to find a "bipartite community" at each stage. This is related to Kleinberg's HITS algorithm that finds the largest eigenvalue of $A^TA$ . We will provide a justification with theoretical rigor for looking at the $k$ largest eigenvalues of $L$ to find multiple bipartite communities in the same graph, and then provide a heuristic algorithm to find strong bipartite communities that is based on the intuition developed by the theoretical methods. Finally, we will present the results of applying our algorithm to various data-mining problems.

preprint2016arXiv

Bipartite noisy hypercubes have large higher-order Cheeger separation

The expansion of a graph is typically associated with its spectral properties - testing whether a graph is an expander is usually done using Cheeger's inequality. One can also use multiple eigenvalues in a higher-order Cheeger's inequality to test a deeper set of properties on the graph. However Cheeger's inquality, and the higher-order Cheeger's inequality, can be imprecise tools. Recently Lee, Gharan, and Trevisan constructed the Noisy Hypercube to prove the sharpness of the gap between spectral expansion and edge expansion in the higher-order Cheeger's inequality. We are concerned with the dual problem: using the upper end of the Laplacian spectrum to test a graph's bipartite nature. This has been shown to have several applications, and recently a dual version of Cheeger's inequality and a dual version of the higher-order Cheeger's inequality have been presented. We construct the Bipartite Noisy Hypercube and use it to prove the sharpness of the gap between spectral bipartite expansion and bipartite edge expansion in the dual version of the dual higher-order Cheeger's inequality.

preprint2016arXiv

Skill-Based Differences in Spatio-Temporal Team Behavior in Defence of The Ancients 2

Multiplayer Online Battle Arena (MOBA) games are among the most played digital games in the world. In these games, teams of players fight against each other in arena environments, and the gameplay is focused on tactical combat. Mastering MOBAs requires extensive practice, as is exemplified in the popular MOBA Defence of the Ancients 2 (DotA 2). In this paper, we present three data-driven measures of spatio-temporal behavior in DotA 2: 1) Zone changes; 2) Distribution of team members and: 3) Time series clustering via a fuzzy approach. We present a method for obtaining accurate positional data from DotA 2. We investigate how behavior varies across these measures as a function of the skill level of teams, using four tiers from novice to professional players. Results indicate that spatio-temporal behavior of MOBA teams is related to team skill, with professional teams having smaller within-team distances and conducting more zone changes than amateur teams. The temporal distribution of the within-team distances of professional and high-skilled teams also generally follows patterns distinct from lower skill ranks.

preprint2015arXiv

Coloring the square of a sparse graph $G$ with almost $Δ(G)$ colors

For a graph $G$ , let $G^2$ be the graph with the same vertex set as $G$ and $xy \in E(G^2)$ when $x \neq y$ and $d_G(x,y) \leq 2$ . Bonamy, Lévêque, and Pinlou conjectured that if $mad (G) < 4 - \frac{2}{c+1}$ and $Δ(G)$ is large, then $χ_\ell(G^2) \leq Δ(G) + c$ . We prove that if $c \geq 3$ , $mad (G) < 4 - \frac{4}{c+1}$ , and $Δ(G)$ is large, then $χ_\ell(G^2) \leq Δ(G) + c$ . Dvořák, Krá\soft{l}, Nejedlý, and Škrekovski conjectured that $χ(G^2) \leq Δ(G) +2$ when $Δ(G)$ is large and $G$ is planar with girth at least $5$ ; our result implies $χ(G^2) \leq Δ(G) +6$ .

preprint2015arXiv

I,F-partitions of Sparse Graphs

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].

preprint2013arXiv

Planar 4-critical graphs with four triangles

By the Grunbaum-Aksenov Theorem (extending Grotzsch's Theorem) every planar graph with at most three triangles is 3-colorable. However, there are infinitely many planar 4-critical graphs with exactly four triangles. We describe all such graphs. This answers a question of Erdos from 1990.

preprint2012arXiv

Large rainbow matchings in large graphs

A \textit{rainbow subgraph} of an edge-colored graph is a subgraph whose edges have distinct colors. The \textit{color degree} of a vertex $v$ is the number of different colors on edges incident to $v$ . We show that if $n$ is large enough (namely, $n\geq 4.25k^2$ ), then each $n$ -vertex graph $G$ with minimum color degree at least $k$ contains a rainbow matching of size at least $k$ .

preprint2012arXiv

Ore's Conjecture for $k=4$ and Gr\" otzsch Theorem

A graph $G$ is $k$ -{\em critical} if it has chromatic number $k$ , but every proper subgraph of $G$ is $(k-1)$ --colorable. Let $f_k(n)$ denote the minimum number of edges in an $n$ -vertex $k$ -critical graph. In a very recent paper, we gave a lower bound, $f_k(n) \geq F(k,n)$ , that is sharp for every $n=1\,({\rm mod}\, k-1)$ . It is also sharp for $k=4$ and every $n\geq 6$ . In this note, we present a simple proof of the bound for $k=4$ . It implies the case $k=4$ of the conjecture by Ore from 1967 that for every $k\geq 4$ and $n\geq k+2$ , $f_k(n+k-1)=f(n)+\frac{k-1}{2}(k - \frac{2}{k-1})$ . We also show that our result implies a simple short proof of the Gr\" otzsch Theorem that every triangle-free planar graph is 3-colorable.

preprint2012arXiv

Ore's Conjecture on color-critical graphs is almost true

A graph $G$ is $k$ -critical if it has chromatic number $k$ , but every proper subgraph of $G$ is $(k-1)$ --colorable. Let $f_k(n)$ denote the minimum number of edges in an $n$ -vertex $k$ -critical graph. We give a lower bound, $f_k(n) \geq F(k,n)$ , that is sharp for every $n=1 ({\rm mod} k-1)$ . It is also sharp for $k=4$ and every $n\geq 6$ . The result improves the classical bounds by Gallai and Dirac and subsequent bounds by Krivelevich and Kostochka and Stiebitz. It establishes the asymptotics of $f_k(n)$ for every fixed $k$ . It also proves that the conjecture by Ore from 1967 that for every $k\geq 4$ and $n\geq k+2$ , $f_k(n+k-1)=f(n)+\frac{k-1}{2}(k - \frac{2}{k-1})$ holds for each $k\geq 4$ for all but at most $k^3/12$ values of $n$ . We give a polynomial-time algorithm for $(k-1)$ -coloring a graph $G$ that satisfies $|E(G[W])| < F_k(|W|)$ for all $W \subseteq V(G)$ , $|W| \geq k$ . We also present some applications of the result.

preprint2012arXiv

Short proofs of coloring theorems on planar graphs

A recent lower bound on the number of edges in a k-critical n-vertex graph by Kostochka and Yancey yields a half-page proof of the celebrated Grötzsch Theorem that every planar triangle-free graph is 3-colorable. In this paper we use the same bound to give short proofs of other known theorems on 3-coloring of planar graphs, among whose is the Grünbaum-Aksenov Theorem that every planar with at most three triangles is 3-colorable. We also prove the new result that every graph obtained from a triangle-free planar graph by adding a vertex of degree at most four is 3-colorable.

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.

Matthew Yancey

Research overview

Is this your work?

10 publications

Bipartite Communities

Bipartite noisy hypercubes have large higher-order Cheeger separation

Skill-Based Differences in Spatio-Temporal Team Behavior in Defence of The Ancients 2

Coloring the square of a sparse graph $G$ with almost $Δ(G)$ colors

I,F-partitions of Sparse Graphs

Planar 4-critical graphs with four triangles

Large rainbow matchings in large graphs

Ore's Conjecture for $k=4$ and Gr\" otzsch Theorem

Ore's Conjecture on color-critical graphs is almost true

Short proofs of coloring theorems on planar graphs

See the researcher in context

Building this map preview

Matthew Yancey

Research overview

Is this your work?

10 publications

Bipartite Communities

Bipartite noisy hypercubes have large higher-order Cheeger separation

Skill-Based Differences in Spatio-Temporal Team Behavior in Defence of The Ancients 2

Coloring the square of a sparse graph GGG with almost Δ(G)Δ(G)Δ(G) colors

I,F-partitions of Sparse Graphs

Planar 4-critical graphs with four triangles

Large rainbow matchings in large graphs

Ore's Conjecture for k=4k=4k=4 and Gr\" otzsch Theorem

Ore's Conjecture on color-critical graphs is almost true

Short proofs of coloring theorems on planar graphs

See the researcher in context

Building this map preview

Coloring the square of a sparse graph $G$ with almost $Δ(G)$ colors

Ore's Conjecture for $k=4$ and Gr\" otzsch Theorem