關於有唯一禁子圖的改邊問題的多項式核心無H加/删/加删邊問題求是否可能加/删/加删至多k條邊於一圖使其無任何與H同構的誘導子圖。此乃計算機科學基本問題之一，其研究廣泛。此題對任意固定H為NP完全且固定參數可解。本文研究無H改邊問題之多項式核心；其存在視H之結構而定。之分類在當H為一圈，路徑或三聯通圖時則完全，當H為删一邊於完全圖之結果時則近完全，當H為樹時則部分此結果加強對無H改邊問題之認識。本文的思路與工具益未來研究，或有助於無H改邊問題多項式核心存在二分定理之發現。 / The H-free edge completion (deletion, editing) problem asks whether it is possible to add to (delete from, add to and delete from) a graph at most k edges so that no induced sub graph isomorphic to H remains. These problems are fundamental in computer science and were studied extensively. They are NP-complete and fixed-parameter tractable for every fixed H. / In this thesis, we study polynomial kernels for H-free edge modification problems, as their existence depends on the structure of H. We characterise their existence completely when H is a path, cycle or 3-connected graph, almost completely when H is one edge short of a complete graph, and partially when H is a tree. / These results enhance our understanding of H-free edge modification problems significantly. Our ideas and tools can be useful to future studies and may lead eventually to a dichotomy theorem on the existence of polynomial kernels for H-free edge modification problems. / Detailed summary in vernacular field only. / Cai, Yufei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2012. / Includes bibliographical references (leaves 97-99). / Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web. / Abstracts also in Chinese. / Chapter 1 --- Preliminaries --- p.1 / Chapter 1.1 --- Edge modification problems and kernelisation --- p.2 / Chapter 1.2 --- Main results --- p.4 / Chapter 1.3 --- The lack of polynomial kernels --- p.5 / Chapter 1.4 --- Conventions and organisation --- p.8 / Chapter 2 --- Component Design --- p.11 / Chapter 2.1 --- Weighted satisficability on selective formulas --- p.12 / Chapter 2.2 --- 4-cycle --- p.15 / Chapter 2.3 --- The general scheme of component design --- p.20 / Chapter 2.4 --- Applications --- p.26 / Chapter 3 --- Local Alteration --- p.31 / Chapter 3.1 --- Bigger forbidden subgraphs from smaller ones --- p.32 / Chapter 3.2 --- Lifting the quarantine --- p.37 / Chapter 4 --- Circuit Implementation --- p.43 / Chapter 4.1 --- Monotone circuits --- p.44 / Chapter 4.2 --- Centralisation --- p.45 / Chapter 4.3 --- Implementation --- p.48 / Chapter 5 --- Kernel for Diamond-Free Edge Deletion --- p.55 / Chapter 5.1 --- Diamond-graphs --- p.56 / Chapter 5.2 --- The invariant things --- p.59 / Chapter 5.3 --- Correctness --- p.61 / Chapter 5.4 --- Lockets --- p.64 / Chapter 5.5 --- Representative systems of diamonds --- p.68 / Chapter 5.6 --- Kernel size --- p.70 / Chapter 6 --- Conclusions --- p.73 / Chapter 6.1 --- 3-connected forbidden subgraphs --- p.74 / Chapter 6.2 --- Cycles, paths and nearly complete graphs --- p.76 / Chapter 6.3 --- Trees --- p.77 / Chapter 6.4 --- Open problems --- p.79 / Chapter A --- List of Trees --- p.81 / Chapter B --- List of Problems --- p.83 / Chapter C --- Glossary --- p.87 / Chapter D --- Bibliography --- p.96

Chan Hoi-Yeung = 網絡與競爭系統的物理 : 個體為本模型中的網絡效應 / 陳凱揚. / Thesis submitted in: September 2005. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2006. / Includes bibliographical references (leaves 191-197). / Text in English; abstracts in English and Chinese. / Chan Hoi-Yeung = Wang luo yu jing zheng xi tong de wu li : ge ti wei ben mo xing zhong de wang luo xiao ying / Chen Kaiyang. / Abstract --- p.i / Acknowledgments --- p.v / Contents --- p.vii / Chapter 1 --- Overview --- p.1 / Chapter I --- Networks --- p.3 / Chapter 2 --- Networks in nature --- p.4 / Chapter 2.1 --- Introduction --- p.4 / Chapter 2.2 --- Terminology of the networks studies --- p.6 / Chapter 2.2.1 --- Nodes --- p.6 / Chapter 2.2.2 --- Links --- p.6 / Chapter 2.2.3 --- Adjacency matrix --- p.9 / Chapter 2.2.4 --- Connectivity --- p.10 / Chapter 2.2.5 --- Clustering coefficient --- p.11 / Chapter 2.2.6 --- Shortest path --- p.11 / Chapter 2.2.7 --- Connectivity correlation --- p.12 / Chapter 2.3 --- Topology in the real-world networks --- p.13 / Chapter 2.3.1 --- The Internet --- p.13 / Chapter 2.3.2 --- The WWW --- p.15 / Chapter 2.3.3 --- Collaboration networks --- p.15 / Chapter 2.3.4 --- Food webs --- p.16 / Chapter 2.3.5 --- Power grids --- p.17 / Chapter 2.4 --- Discussion --- p.17 / Chapter 3 --- Review on Network Models --- p.19 / Chapter 3.1 --- Introduction --- p.19 / Chapter 3.2 --- Graph Theory --- p.20 / Chapter 3.2.1 --- Classical random graph --- p.20 / Chapter 3.3 --- Evolving networks --- p.23 / Chapter 3.3.1 --- Random growing network --- p.23 / Chapter 3.3.2 --- Fitness growing network --- p.25 / Chapter 3.3.3 --- Barabasi-Albert model --- p.27 / Chapter 3.3.4 --- Fitness model --- p.31 / Chapter 3.4 --- Lattice --- p.33 / Chapter 3.4.1 --- Regular hypercubic lattices (Periodic) --- p.33 / Chapter 3.4.2 --- Regular hypercubic lattices (Free boundary conditions) . --- p.35 / Chapter 3.5 --- Discussion --- p.35 / Chapter 4 --- Network Properties --- p.38 / Chapter 4.1 --- More derivations on existing models --- p.38 / Chapter 4.1.1 --- Classical random graphs --- p.38 / Chapter 4.1.2 --- Barabasi-Albert model --- p.40 / Chapter 4.1.3 --- Fitness Model --- p.42 / Chapter 4.1.4 --- Regular hypercubic lattices (Periodic) --- p.45 / Chapter 4.2 --- New model --- p.48 / Chapter 4.2.1 --- Fitness-BA hybrid model --- p.48 / Chapter 4.3 --- Link removal --- p.55 / Chapter 4.3.1 --- Introduction --- p.55 / Chapter 4.3.2 --- Formalism in connectivity --- p.55 / Chapter 4.3.3 --- Pruned BA Model --- p.56 / Chapter 4.4 --- Link addition --- p.58 / Chapter 4.4.1 --- Introduction --- p.58 / Chapter 4.4.2 --- Regular hypercubic lattices (Periodic) --- p.58 / Chapter 4.5 --- Discussion --- p.60 / Chapter II --- Games --- p.62 / Chapter 5 --- Review on Agent-based models of competing population --- p.63 / Chapter 5.1 --- Introduction --- p.63 / Chapter 5.2 --- The El Farol Bar attendance problem --- p.65 / Chapter 5.2.1 --- Model --- p.65 / Chapter 5.2.2 --- Strategies --- p.66 / Chapter 5.2.3 --- Discussion --- p.66 / Chapter 5.3 --- Minority game --- p.67 / Chapter 5.3.1 --- Model --- p.67 / Chapter 5.3.2 --- Strategies --- p.68 / Chapter 5.3.3 --- Attendance --- p.69 / Chapter 5.3.4 --- History and quasi-Eulerian state --- p.69 / Chapter 5.3.5 --- Success rate and Hamming distance --- p.71 / Chapter 5.3.6 --- Volatility --- p.73 / Chapter 5.3.7 --- Crowd-anticrowd theory --- p.75 / Chapter 5.3.8 --- Discussion --- p.76 / Chapter 6 --- B-A-R model : Dynamics --- p.78 / Chapter 6.1 --- Model --- p.78 / Chapter 6.2 --- Results: Plateaux and periodicity --- p.81 / Chapter 6.3 --- A microscopic view: Agents' decisions and strategy performance --- p.86 / Chapter 6.4 --- A macroscopic view: Bit-string patterns --- p.92 / Chapter 6.4.1 --- The history space --- p.92 / Chapter 6.4.2 --- Bit-string statistics of different states --- p.94 / Chapter 6.5 --- The (max = 1 states --- p.97 / Chapter 6.5.1 --- Values of wm3iX --- p.97 / Chapter 6.5.2 --- "Strategy ranking evolvement: ni, (w)" --- p.101 / Chapter 6.5.3 --- Substates . --- p.105 / Chapter 7 --- B-A-R model : Formalism --- p.108 / Chapter 7.1 --- Resource level at transitions of Cmax = 0 state --- p.108 / Chapter 7.2 --- Resource levels at transitions of Cmax 二 1 states --- p.109 / Chapter 7.2.1 --- Method --- p.109 / Chapter 7.2.2 --- Lmin for upper substate --- p.110 / Chapter 7.2.3 --- Lmin for lower substate --- p.113 / Chapter 7.3 --- Discussion --- p.116 / Chapter 8 --- B-A-R model : Statistics --- p.121 / Chapter 8.1 --- Problem --- p.121 / Chapter 8.2 --- Bit-string statistics --- p.122 / Chapter 8.2.1 --- Allowed transitions --- p.122 / Chapter 8.2.2 --- Grouping the history space --- p.122 / Chapter 8.2.3 --- "Grouping the states, Cmax" --- p.127 / Chapter 8.2.4 --- "Labelling each state, /(C)" --- p.129 / Chapter 8.3 --- Discussion --- p.130 / Chapter III --- Networked games --- p.131 / Chapter 9 --- Networked minority game --- p.132 / Chapter 9.1 --- Model --- p.132 / Chapter 9.2 --- Preliminary results: Agents' success rates --- p.133 / Chapter 9.3 --- Ranking the strategies --- p.135 / Chapter 9.3.1 --- Ranking pattern --- p.136 / Chapter 9.3.2 --- Fraction of strategies in each rank --- p.140 / Chapter 9.4 --- Number of agents using a best strategy belonging to rank r --- p.141 / Chapter 9.4.1 --- Unconnected population --- p.141 / Chapter 9.4.2 --- Networked population . --- p.142 / Chapter 9.5 --- Application: Mean success rate --- p.143 / Chapter 9.6 --- Mean success rate of agents with degree k --- p.147 / Chapter 9.7 --- Application in other networks --- p.149 / Chapter 9.8 --- Discussion --- p.151 / Chapter 10 --- Interacting agents: Networked B-A-R model --- p.154 / Chapter 10.1 --- Model --- p.154 / Chapter 10.2 --- The quasi-Eulerian state (wmax = 1/2 state) --- p.155 / Chapter 10.3 --- The emergent states --- p.159 / Chapter 10.3.1 --- General results --- p.159 / Chapter 10.3.2 --- The Cmax = 0 state --- p.160 / Chapter 10.3.3 --- The Cmax = 1 state --- p.161 / Chapter 10.4 --- Discussion --- p.162 / Chapter IV --- Conclusion --- p.164 / Chapter 11 --- Conclusion --- p.165 / Chapter V --- Appendices --- p.172 / Chapter A --- List of symbols --- p.173 / Chapter A.1 --- Networks --- p.173 / Chapter A.2 --- Games --- p.174 / Chapter A.3 --- Networked games --- p.176 / Chapter B --- Distance distribution in classical random graphs --- p.177 / Chapter B.1 --- Method --- p.177 / Chapter B.2 --- Distance distribution --- p.177 / Chapter B.3 --- Behaviour at small L --- p.178 / Chapter B.4 --- Behaviour at large L --- p.179 / Chapter C --- Co-ordination number in infinite hypercubic lattice --- p.181 / Chapter C.1 --- Method --- p.181 / Chapter C.1.1 --- ID lattice --- p.181 / Chapter C.1.2 --- 2D square lattice --- p.182 / Chapter C.1.3 --- Higher dimension hypercubic lattices --- p.183 / Chapter C.2 --- Coefficients --- p.185 / Chapter D --- Connectivity distribution in fitness-BA hybrid model --- p.187 / Chapter D.1 --- Mean field approach --- p.187 / Chapter D.2 --- Connectivity distribution --- p.188 / Chapter D.3 --- Power-law exponent --- p.190 / Bibliography --- p.191

No description available.

No description available.

No description available.

Mathematical concepts have aided the progression of many different fields of study. Math is not only helpful in science and engineering, but also in the humanities and social sciences. Therefore, it seemed quite natural to apply my preliminary work with set intersections to voting theory, and that application has helped to focus my thesis. Rather than studying set intersections in general, I am attempting to study set intersections and what they mean in a voting situation. This can lead to better ways to model preferences and to predict which campaign platforms will be most popular. Because I feel that allowing people to only vote for one candidate results in a loss of too much information, I consider approval voting, where people can vote for as many platforms as they like.

Kolmogorov complexity is a theory based on the premise that the complexity of a binary string can be measured by its compressibility; that is, a string’s complexity is the length of the shortest program that produces that string. We explore applications of this measure to graph theory.

Graph Theory is the mathematical study of the structure of abstract relationships between objects. Although these constructions (graphs) are themselves purely theoretical, their ability to model pair-wise relationships in systems of arbitrary complexity yields abundant direct correspondence with numerous important physical and societal systems in the real world. Additionally, the simple discrete nature of fundamental graph structures allows for easy pseudo-geometric visualization of graphs in a wide variety of ways. Taken together, these two properties suggest that graph theory teaching, research, and applications would benefit greatly from the use of a unified software environment for graph construction, interaction, and visualization. Based on this need, a comprehensive survey was undertaken of existing graph theory software packages, programs, and libraries to determine the suitability of each for use as a graph theory teaching and research tool. Some of the desired components (especially in the realm of graph visualization) were found to be implemented in several current tools and systems, but no single system was located with the ability to perform all such functions together in a coordinated way. Graph Shop (the Graph Theory Workshop) is a new software package for graph theory research and applications. It was designed to be usable by students and graph theory beginners yet powerful enough to assist with advanced graph theory research. It runs on a variety of platforms and is available for free under the GNU GPL open source license.

No description available.

No description available.