Matching Items (18)

132775-Thumbnail Image.png

Skipping Turns on the Ordering Game

Description

In the ordering game on a graph G, Alice and Bob take turns placing the vertices of G into a linear ordering. The score of the game is the maximum number of neighbors that any vertex has before it in

In the ordering game on a graph G, Alice and Bob take turns placing the vertices of G into a linear ordering. The score of the game is the maximum number of neighbors that any vertex has before it in the ordering. Alice's goal in the ordering game is to minimize the score, while Bob's goal is to maximize it. The game coloring number is the least score that Alice can always guarantee in the ordering game, no matter how Bob plays. This paper examines what happens to the game coloring number if Alice or Bob skip turns on the ordering game. Preliminary definitions and examples are provided to give context to the ordering game. These include a polynomial time algorithm to compute the coloring number, a non-competitive version of the game coloring number. The notion of the preordered game is introduced as the primary tool of the paper, along with its naturally defined preordered game coloring number. To emphasize the complex relationship between the coloring number and the preordered game coloring number, a non-polynomial time strategy is given to Alice and Bob that yields the preordered game coloring number on any graph. Additionally, the preordered game coloring number is shown to be monotonic, one of the most useful properties for turn-skipping. Techniques developed throughout the paper are then used to determine that Alice cannot reduce the score and Bob cannot improve the score by skipping any number of their respective turns. This paper can hopefully be used as a stepping stone towards bounding the score on graphs when vertices are removed, as well as in deciphering further properties of the asymmetric marking game.

Contributors

Created

Date Created
2019-05

134602-Thumbnail Image.png

Virtual Reality Visualization of Constructive Solid Geometry Utilizing an HTC Vive

Description

This project created a tool for visualizing constructive solid geometry (CSG) using an HTC Vive virtual reality
headset. This tool provides functionality for surface triangulation
of a variety of three-dimensional primitive solids. Then with those
solids it can perform the

This project created a tool for visualizing constructive solid geometry (CSG) using an HTC Vive virtual reality
headset. This tool provides functionality for surface triangulation
of a variety of three-dimensional primitive solids. Then with those
solids it can perform the core CSG operations—intersection,
union and complement—to create more complex objects. This
tool also parses in Silo data files to allow the visualization
of scientific models like the Annular Core Research Reactor.
This project is useful for both education and visualization. This
project will be used by scientists to visualize and understand
their simulation results, and used as a museum exhibit to engage
the next generation of scientists in computer modeling.

Contributors

Agent

Created

Date Created
2017-05

136340-Thumbnail Image.png

An exploration of proofs of the Szemerédi regularity lemma

Description

This paper focuses on the Szemerédi regularity lemma, a result in the field of extremal graph theory. The lemma says that every graph can be partitioned into bounded equal parts such that most edges of the graph span these partitions,

This paper focuses on the Szemerédi regularity lemma, a result in the field of extremal graph theory. The lemma says that every graph can be partitioned into bounded equal parts such that most edges of the graph span these partitions, and these edges are distributed in a fairly uniform way. Definitions and notation will be established, leading to explorations of three proofs of the regularity lemma. These are a version of the original proof, a Pythagoras proof utilizing elemental geometry, and a proof utilizing concepts of spectral graph theory. This paper is intended to supplement the proofs with background information about the concepts utilized. Furthermore, it is the hope that this paper will serve as another resource for students and others to begin study of the regularity lemma.

Contributors

Created

Date Created
2015-05

137483-Thumbnail Image.png

It Takes Five: Basketball Teams Using Network Metrics

Description

Analytic research on basketball games is growing quickly, specifically in the National Basketball Association. This paper explored the development of this analytic research and discovered that there has been a focus on individual player metrics and a dearth of quantitative

Analytic research on basketball games is growing quickly, specifically in the National Basketball Association. This paper explored the development of this analytic research and discovered that there has been a focus on individual player metrics and a dearth of quantitative team characterizations and evaluations. Consequently, this paper continued the exploratory research of Fewell and Armbruster's "Basketball teams as strategic networks" (2012), which modeled basketball teams as networks and used metrics to characterize team strategy in the NBA's 2010 playoffs. Individual players and outcomes were nodes and passes and actions were the links. This paper used data that was recorded from playoff games of the two 2012 NBA finalists: the Miami Heat and the Oklahoma City Thunder. The same metrics that Fewell and Armbruster used were explained, then calculated using this data. The offensive networks of these two teams during the playoffs were analyzed and interpreted by using other data and qualitative characterization of the teams' strategies; the paper found that the calculated metrics largely matched with our qualitative characterizations of the teams. The validity of the metrics in this paper and Fewell and Armbruster's paper was then discussed, and modeling basketball teams as multiple-order Markov chains rather than as networks was explored.

Contributors

Agent

Created

Date Created
2013-05

152048-Thumbnail Image.png

On tiling directed graphs with cycles and tournaments

Description

A tiling is a collection of vertex disjoint subgraphs called tiles. If the tiles are all isomorphic to a graph $H$ then the tiling is an $H$-tiling. If a graph $G$ has an $H$-tiling which covers all of the vertices

A tiling is a collection of vertex disjoint subgraphs called tiles. If the tiles are all isomorphic to a graph $H$ then the tiling is an $H$-tiling. If a graph $G$ has an $H$-tiling which covers all of the vertices of $G$ then the $H$-tiling is a perfect $H$-tiling or an $H$-factor. A goal of this study is to extend theorems on sufficient minimum degree conditions for perfect tilings in graphs to directed graphs. Corrádi and Hajnal proved that every graph $G$ on $3k$ vertices with minimum degree $delta(G)ge2k$ has a $K_3$-factor, where $K_s$ is the complete graph on $s$ vertices. The following theorem extends this result to directed graphs: If $D$ is a directed graph on $3k$ vertices with minimum total degree $delta(D)ge4k-1$ then $D$ can be partitioned into $k$ parts each of size $3$ so that all of parts contain a transitive triangle and $k-1$ of the parts also contain a cyclic triangle. The total degree of a vertex $v$ is the sum of $d^-(v)$ the in-degree and $d^+(v)$ the out-degree of $v$. Note that both orientations of $C_3$ are considered: the transitive triangle and the cyclic triangle. The theorem is best possible in that there are digraphs that meet the minimum degree requirement but have no cyclic triangle factor. The possibility of added a connectivity requirement to ensure a cycle triangle factor is also explored. Hajnal and Szemerédi proved that if $G$ is a graph on $sk$ vertices and $delta(G)ge(s-1)k$ then $G$ contains a $K_s$-factor. As a possible extension of this celebrated theorem to directed graphs it is proved that if $D$ is a directed graph on $sk$ vertices with $delta(D)ge2(s-1)k-1$ then $D$ contains $k$ disjoint transitive tournaments on $s$ vertices. We also discuss tiling directed graph with other tournaments. This study also explores minimum total degree conditions for perfect directed cycle tilings and sufficient semi-degree conditions for a directed graph to contain an anti-directed Hamilton cycle. The semi-degree of a vertex $v$ is $min{d^+(v), d^-(v)}$ and an anti-directed Hamilton cycle is a spanning cycle in which no pair of consecutive edges form a directed path.

Contributors

Agent

Created

Date Created
2013

150038-Thumbnail Image.png

Optimal degree conditions for spanning subgraphs

Description

In a large network (graph) it would be desirable to guarantee the existence of some local property based only on global knowledge of the network. Consider the following classical example: how many connections are necessary to guarantee that the network

In a large network (graph) it would be desirable to guarantee the existence of some local property based only on global knowledge of the network. Consider the following classical example: how many connections are necessary to guarantee that the network contains three nodes which are pairwise adjacent? It turns out that more than n^2/4 connections are needed, and no smaller number will suffice in general. Problems of this type fall into the category of ``extremal graph theory.'' Generally speaking, extremal graph theory is the study of how global parameters of a graph are related to local properties. This dissertation deals with the relationship between minimum degree conditions of a host graph G and the property that G contains a specified spanning subgraph (or class of subgraphs). The goal is to find the optimal minimum degree which guarantees the existence of a desired spanning subgraph. This goal is achieved in four different settings, with the main tools being Szemeredi's Regularity Lemma; the Blow-up Lemma of Komlos, Sarkozy, and Szemeredi; and some basic probabilistic techniques.

Contributors

Agent

Created

Date Created
2011

149332-Thumbnail Image.png

The first-fit algorithm uses many colors on some interval graphs

Description

Graph coloring is about allocating resources that can be shared except where there are certain pairwise conflicts between recipients. The simplest coloring algorithm that attempts to conserve resources is called first fit. Interval graphs are used in models for scheduling

Graph coloring is about allocating resources that can be shared except where there are certain pairwise conflicts between recipients. The simplest coloring algorithm that attempts to conserve resources is called first fit. Interval graphs are used in models for scheduling (in computer science and operations research) and in biochemistry for one-dimensional molecules such as genetic material. It is not known precisely how much waste in the worst case is due to the first-fit algorithm for coloring interval graphs. However, after decades of research the range is narrow. Kierstead proved that the performance ratio R is at most 40. Pemmaraju, Raman, and Varadarajan proved that R is at most 10. This can be improved to 8. Witsenhausen, and independently Chrobak and Slusarek, proved that R is at least 4. Slusarek improved this to 4.45. Kierstead and Trotter extended the method of Chrobak and Slusarek to one good for a lower bound of 4.99999 or so. The method relies on number sequences with a certain property of order. It is shown here that each sequence considered in the construction satisfies a linear recurrence; that R is at least 5; that the Fibonacci sequence is in some sense minimally useless for the construction; and that the Fibonacci sequence is a point of accumulation in some space for the useful sequences of the construction. Limitations of all earlier constructions are revealed.

Contributors

Agent

Created

Date Created
2010

151429-Thumbnail Image.png

On-line coloring of partial orders, circular arc graphs, and trees

Description

A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually

A central concept of combinatorics is partitioning structures with given constraints. Partitions of on-line posets and on-line graphs, which are dynamic versions of the more familiar static structures posets and graphs, are examined. In the on-line setting, vertices are continually added to a poset or graph while a chain partition or coloring (respectively) is maintained. %The optima of the static cases cannot be achieved in the on-line setting. Both upper and lower bounds for the optimum of the number of chains needed to partition a width $w$ on-line poset exist. Kierstead's upper bound of $\frac{5^w-1}{4}$ was improved to $w^{14 \lg w}$ by Bosek and Krawczyk. This is improved to $w^{3+6.5 \lg w}$ by employing the First-Fit algorithm on a family of restricted posets (expanding on the work of Bosek and Krawczyk) . Namely, the family of ladder-free posets where the $m$-ladder is the transitive closure of the union of two incomparable chains $x_1\le\dots\le x_m$, $y_1\le\dots\le y_m$ and the set of comparabilities $\{x_1\le y_1,\dots, x_m\le y_m\}$. No upper bound on the number of colors needed to color a general on-line graph exists. To lay this fact plain, the performance of on-line coloring of trees is shown to be particularly problematic. There are trees that require $n$ colors to color on-line for any positive integer $n$. Furthermore, there are trees that usually require many colors to color on-line even if they are presented without any particular strategy. For restricted families of graphs, upper and lower bounds for the optimum number of colors needed to maintain an on-line coloring exist. In particular, circular arc graphs can be colored on-line using less than 8 times the optimum number from the static case. This follows from the work of Pemmaraju, Raman, and Varadarajan in on-line coloring of interval graphs.

Contributors

Agent

Created

Date Created
2012

160061-Thumbnail Image.png

On the existence of loose cycle tilings and rainbow cycles

Description

Extremal graph theory results often provide minimum degree

conditions which guarantee a copy of one graph exists within

another. A perfect $F$-tiling of a graph $G$ is a collection

$\mathcal{F}$ of subgraphs of $G$ such that every element of

$\mathcal{F}$ is isomorphic to $F$

Extremal graph theory results often provide minimum degree

conditions which guarantee a copy of one graph exists within

another. A perfect $F$-tiling of a graph $G$ is a collection

$\mathcal{F}$ of subgraphs of $G$ such that every element of

$\mathcal{F}$ is isomorphic to $F$ and such that every vertex in $G$

is in exactly one element of $\mathcal{F}$. Let $C^{3}_{t}$ denote

the loose cycle on $t = 2s$ vertices, the $3$-uniform hypergraph

obtained by replacing the edges $e = \{u, v\}$ of a graph cycle $C$

on $s$ vertices with edge triples $\{u, x_e, v\}$, where $x_e$ is

uniquely assigned to $e$. This dissertation proves for even

$t \geq 6$, that any sufficiently large $3$-uniform hypergraph $H$

on $n \in t \mathbb{Z}$ vertices with minimum $1$-degree

$\delta^1(H) \geq {n - 1 \choose 2} - {\Bsize \choose 2} + c(t,n) +

1$, where $c(t,n) \in \{0, 1, 3\}$, contains a perfect

$C^{3}_{t}$-tiling. The result is tight, generalizing previous

results on $C^3_4$ by Han and Zhao. For an edge colored graph $G$,

let the minimum color degree $\delta^c(G)$ be the minimum number of

distinctly colored edges incident to a vertex. Call $G$ rainbow if

every edge has a unique color. For $\ell \geq 5$, this dissertation

proves that any sufficiently large edge colored graph $G$ on $n$

vertices with $\delta^c(G) \geq \frac{n + 1}{2}$ contains a rainbow

cycle on $\ell$ vertices. The result is tight for odd $\ell$ and

extends previous results for $\ell = 3$. In addition, for even

$\ell \geq 4$, this dissertation proves that any sufficiently large

edge colored graph $G$ on $n$ vertices with

$\delta^c(G) \geq \frac{n + c(\ell)}{3}$, where

$c(\ell) \in \{5, 7\}$, contains a rainbow cycle on $\ell$

vertices. The result is tight when $6 \nmid \ell$. As a related

result, this dissertation proves for all $\ell \geq 4$, that any

sufficiently large oriented graph $D$ on $n$ vertices with

$\delta^+(D) \geq \frac{n + 1}{3}$ contains a directed cycle on

$\ell$ vertices. This partially generalizes a result by Kelly,

K\uhn" and Osthus that uses minimum semidegree rather than minimum

out degree."

Contributors

Agent

Created

Date Created
2019

161588-Thumbnail Image.png

Power System Security Enhancement for Real-Time Operations During Multiple Outages using Network Science

Description

Ensuring reliable operation of large power systems subjected to multiple outages is a challenging task because of the combinatorial nature of the problem. Traditional methods of steady-state security assessment in power systems involve contingency analysis based on AC or DC

Ensuring reliable operation of large power systems subjected to multiple outages is a challenging task because of the combinatorial nature of the problem. Traditional methods of steady-state security assessment in power systems involve contingency analysis based on AC or DC power flows. However, power flow based contingency analysis is not fast enough to evaluate all contingencies for real-time operations. Therefore, real-time contingency analysis (RTCA) only evaluates a subset of the contingencies (called the contingency list), and hence might miss critical contingencies that lead to cascading failures.This dissertation proposes a new graph-theoretic approach, called the feasibility test (FT) algorithm, for analyzing whether a contingency will create a saturated or over-loaded cut-set in a meshed power network; a cut-set denotes a set of lines which if tripped separates the network into two disjoint islands. A novel feature of the proposed approach is that it lowers the solution time significantly making the approach viable for an exhaustive real-time evaluation of the system. Detecting saturated cut-sets in the power system is important because they represent the vulnerable bottlenecks in the network. The robustness of the FT algorithm is demonstrated on a 17,000+ bus model of the Western Interconnection (WI).
Following the detection of post-contingency cut-set saturation, a two-component methodology is proposed to enhance the reliability of large power systems during a series of outages. The first component combines the proposed FT algorithm with RTCA to create an integrated corrective action (iCA), whose goal is to secure the power system against post-contingency cut-set saturation as well as critical branch overloads. The second component only employs the results of the FT to create a relaxed corrective action (rCA) that quickly secures the system against saturated cut-sets.
The first component is more comprehensive than the second, but the latter is computationally more efficient. The effectiveness of the two components is evaluated based upon the number of cascade triggering contingencies alleviated, and the computation time. Analysis of different case-studies on the IEEE 118-bus and 2000-bus synthetic Texas systems indicate that the proposed two-component methodology enhances the scope and speed of power system security assessment during multiple outages.

Contributors

Agent

Created

Date Created
2021