Muutke küpsiste eelistusi

E-raamat: 50 years of Combinatorics, Graph Theory, and Computing [Taylor & Francis e-raamat]

Translated by ,
  • Taylor & Francis e-raamat
  • Hind: 240,04 €*
  • * hind, mis tagab piiramatu üheaegsete kasutajate arvuga ligipääsu piiramatuks ajaks
  • Tavahind: 342,91 €
  • Säästad 30%

50 Years of Combinatorics, Graph Theory, and Computing advances research in discrete mathematics by providing current research surveys, each written by experts in their subjects.

The book also celebrates outstanding mathematics from 50 years at the Southeastern International Conference on Combinatorics, Graph Theory & Computing (SEICCGTC). The conference is noted for the dissemination and stimulation of research, while fostering collaborations among mathematical scientists at all stages of their careers.

The authors of the chapters highlight open questions. The sections of the book include: Combinatorics; Graph Theory; Combinatorial Matrix Theory; Designs, Geometry, Packing and Covering. Readers will discover the breadth and depth of the presentations at the SEICCGTC, as well as current research in combinatorics, graph theory and computer science.

Features:

  • Commemorates 50 years of the Southeastern International Conference on Combinatorics, Graph Theory & Computing with research surveys
  • Surveys highlight open questions to inspire further research
  • Chapters are written by experts in their fields
    • Extensive bibliographies are provided at the end of each chapter
  • Preface xv
    Editors xxiii
    Contributors xxv
    1 Personal Reflections of the SEICCGTC: Origins and Beyond
    1(18)
    K.B. Reid
    1.1 Introduction
    1(1)
    1.2 Description of This
    Chapter
    2(1)
    1.3 Impressions of the Combinatorial Research Atmosphere in the Late 1960's
    3(3)
    1.4 Brief Biographies of Early Conference Organizers
    6(3)
    1.5 Conference Facts
    9(2)
    1.6 Some Non-Conference Activities at the Conferences
    11(2)
    1.7 Conference "Firsts"
    13(1)
    1.8 Some Mathematics from the Fifth Conference (1974)
    14(5)
    I Combinatorics 19(90)
    2 Some of My Favorite Problems (I)
    21(16)
    Ron Graham
    2.1 Introduction
    21(1)
    2.2 Prologue
    21(1)
    2.3 Universal Cycles
    22(2)
    2.4 Combs
    24(2)
    2.5 The Middle Binomial Coefficient (2nn)
    26(2)
    2.6 The Steiner Ratio Problem
    28(2)
    2.7 A Curious 'Inversion' in Complexity Theory
    30(2)
    2.8 A Final Problem
    32(5)
    3 Variations on the Sequenceable Theme
    37(18)
    Brian Alspach
    3.1 Introduction
    37(3)
    3.2 Strongly Sequenceable Groups
    40(1)
    3.3 Orthogonal Decompositions
    41(1)
    3.4 Abelian Groups
    42(2)
    3.5 A Poset Formulation
    44(2)
    3.6 The Poset Approach
    46(1)
    3.7 Partial Steiner Triple Systems
    47(3)
    3.8 Other Decompositions
    50(1)
    3.9 Sequencing Edges
    50(5)
    4 A Survey of Stack Sortable Permutations
    55(18)
    Miklos Bona
    4.1 Introduction
    55(1)
    4.2 Three Equivalent Definitions
    56(2)
    4.2.1 The Original Definition
    56(1)
    4.2.2 The Original Definition Revisited
    56(1)
    4.2.3 The Definition Using Trees
    57(1)
    4.3 Enumeration Formulas
    58(7)
    4.3.1 Exact Formulas
    58(2)
    4.3.2 A Surprising Connection with the Pattern 1324
    60(1)
    4.3.3 Bounds
    61(1)
    4.3.3.1 Stack Words
    61(1)
    4.3.3.2 Computing the Upper Bound for W3 (n)
    63(2)
    4.4 The Generating Function of the Numbers Wt (n)
    65(2)
    4.5 Descents
    67(3)
    4.6 Further Directions
    70(3)
    5 Dimension for Posets and Chromatic Number for Graphs
    73(24)
    William T. Trotter
    5.1 Introduction
    73(3)
    5.1.1 Basic Concepts and Results for Dimension
    74(2)
    5.2 Stability Analysis
    76(7)
    5.2.1 Stability Analysis for Dimension
    79(2)
    5.2.2 Open Problems for Stability Analysis
    81(1)
    5.2.3 Open Problems on Size
    82(1)
    5.3 Maximum Degree
    83(5)
    5.4 Blocks in Posets and Graphs
    88(9)
    5.4.1 Open Problems Involving Cover Graphs
    90(7)
    6 Erdo's Magic
    97(12)
    Joel Spencer
    6.1 Introduction
    97(1)
    6.2 Independent Sets
    98(1)
    6.3 Avoiding Monochromatic Sets
    99(3)
    6.4 Six Suffice
    102(2)
    6.5 QuasiRandomness
    104(1)
    6.6 Graphons
    105(4)
    II Graph Theory 109(102)
    7 Developments on Saturated Graphs
    111(24)
    Ronald J. Gould
    7.1 Introduction
    111(2)
    7.2 Saturation Numbers
    113(5)
    7.2.1 Trees and Forests
    114(3)
    7.2.2 Cycles
    117(1)
    7.2.3 Partite Graphs
    117(1)
    7.3 Limits On The Saturation Function
    118(1)
    7.4 Hypergraphs
    119(1)
    7.5 Saturation Spectrum
    120(4)
    7.6 Variations
    124(12)
    7.6.1 Weak Saturation
    124(3)
    7.6.2 Edge-Colored Saturation
    127(1)
    7.6.3 Other Variations and Results
    128(7)
    8 Magic Labeling Basics
    135(20)
    W.D. Wallis
    8.1 Magic Labeling
    136(2)
    8.1.1 Labelings
    136(1)
    8.1.2 The Classical Magic Arrays
    136(1)
    8.1.3 Magic Labeling
    137(1)
    8.2 Edge-Magic Total Labelings
    138(7)
    8.2.1 Basic Ideas
    138(1)
    8.2.1.1 Definitions
    138(1)
    8.2.1.2 Some Elementary Counting
    138(1)
    8.2.1.3 Duality
    140(1)
    8.2.2 Cliques and Complete Graphs
    140(1)
    8.2.2.1 Sidon Sequences
    140(1)
    8.2.2.2 Complete Subgraphs
    142(1)
    8.2.3 Cycles
    143(1)
    8.2.3.1 Generalizations of Cycles
    143(1)
    8.2.4 Complete Bipartite Graphs
    143(1)
    8.2.5 Trees
    144(1)
    8.3 Vertex-Magic Total Labelings
    145(10)
    8.3.1 Basic Ideas
    145(1)
    8.3.1.1 Definitions
    145(1)
    8.3.1.2 Basic Counting
    145(2)
    8.3.2 Regular Graphs
    147(1)
    8.3.3 Some Standard Graphs
    147(1)
    8.3.3.1 Cycles and Paths
    147(1)
    8.3.3.2 Complete Graphs and Complete Bipartite Graphs
    147(1)
    8.3.3.3 Construction of VMTLs of Km,n
    149(1)
    8.3.3.4 Joins
    149(1)
    8.3.4 Graphs with Vertices of Degree One
    149(6)
    9 Block Colorings of Graph Decompositions
    155(16)
    E.B. Matson
    C.A. Rodger
    9.1 Introduction
    155(4)
    9.2 Graph Decompositions
    159(2)
    9.3 Amalgamations and Recent Results
    161(5)
    9.4 Open Problems
    166(5)
    10 Reconfiguration of Colourings and Dominating Sets in Graphs
    171(22)
    C.M. Mynhardt
    S. Nasserasr
    10.1 Introduction
    171(2)
    10.2 Complexity
    173(1)
    10.3 Reconfiguration of Colourings
    174(7)
    10.3.1 The k-Colouring Graph
    174(5)
    10.3.2 Reconfiguration of Homomorphisms
    179(1)
    10.3.3 The k-Edge-Colouring Graph
    180(1)
    10.4 Reconfiguration of Dominating Sets
    181(13)
    10.4.1 The k-Dominating Graph
    181(3)
    10.4.2 The k-Total-Dominating Graph
    184(1)
    10.4.3 Jump y-Graphs
    185(1)
    10.4.4 Slide y-Graphs
    186(1)
    10.4.5 Irredundance
    186(7)
    11 Edge Intersection Graphs of Paths on a Grid
    193(18)
    Martin Charles Golumbic
    Gila Morgenstern
    11.1 Introduction
    194(1)
    11.2 The Bend Number of Known Classes of Graphs
    194(2)
    11.3 B1-Subclass Characterizations
    196(5)
    11.4 The Strong Helly Number of B1-EPG Representations
    201(1)
    11.5 Algorithmic Aspects of EPG Graphs
    202(2)
    11.6 Boundary Generated B1-EPG Graphs
    204(2)
    11.7 Concluding Remarks and Further Reading
    206(5)
    III Combinatorial Matrix Theory 211(80)
    12 A Jaunt in Spectral Graph Theory
    213(26)
    Steve Butler
    12.1 Introduction
    214(1)
    12.2 A Menagerie of Matrices
    214(9)
    12.2.1 The Adjacency Matrix
    214(2)
    12.2.2 The Laplacian Matrix and Signless Laplacian Matrix
    216(2)
    12.2.3 The Probability Transition Matrix and the Normalized Laplacian
    218(3)
    12.2.4 The Distance Matrix
    221(1)
    12.2.5 The Seidel Matrix
    222(1)
    12.2.6 The Quantum Walk Matrix
    223(1)
    12.3 Strengths and Weaknesses of Different Matrices
    223(7)
    12.3.1 Combining Spectra
    224(1)
    12.3.2 Graph Operations
    224(2)
    12.3.3 A Line Graph Excursion
    226(1)
    12.3.4 Graphs Determined by Their Spectrum
    227(1)
    12.3.5 Interlacing
    228(1)
    12.3.6 Graphs that Have a Common Spectrum
    228(2)
    12.4 Connectivity
    230(4)
    12.4.1 Bottlenecks and Cheeger Constants
    230(1)
    12.4.2 Discrepancy and the Value of Normalizing
    231(2)
    12.4.3 Ramanujan Graphs
    233(1)
    12.4.4 Quasirandom Graphs
    233(1)
    12.5 Starting Your Odyssey in Spectral Graph Theory
    234(5)
    13 The Inverse Eigenvalue Problem of a Graph
    239(24)
    Leslie Hogben
    Jephian C.H. Lin
    Bryan L. Shader
    13.1 Introduction
    239(3)
    13.2 Ancillary Problems
    242(4)
    13.2.1 Maximum Nullity and Minimum Rank
    243(1)
    13.2.2 Variants of Maximum Nullity and Minimum Rank
    244(1)
    13.2.3 The Minimum Number of Distinct Eigenvalues
    245(1)
    13.3 Strong Properties and Minor Monotonicity
    246(6)
    13.3.1 Applications of the Strong Properties
    247(3)
    13.3.2 Tangent Spaces and the Implicit Function Theorem
    250(2)
    13.4 Zero Forcing, Propagation Time, and Throttling
    252(5)
    13.4.1 Zero Forcing and Its Variants
    252(3)
    13.4.2 Propagation Time
    255(1)
    13.4.3 Throttling
    256(1)
    13.5 Concluding Remarks and Open Problems
    257(6)
    14 Rank Functions
    263(14)
    LeRoy B. Beasley
    14.1 Introduction
    263(1)
    14.2 Preliminaries
    264(2)
    14.3 Matrix Ranks
    266(3)
    14.4 Rank Functions in Graph Theory
    269(3)
    14.4.1 Minimum Rank
    269(1)
    14.4.2 Rank Functions on Graphs Defined by Coverings
    270(2)
    14.4.3 Rank Functions on Graphs Not Defined by Coverings
    272(1)
    14.5 Equivalent Rank Functions
    272(5)
    15 Permutation Matrices and Beyond: An Essay
    277(14)
    Richard A. Brualdi
    15.1 Permutation Matrices
    277(1)
    15.2 Beyond Permutation Matrices
    278(8)
    15.3 Some Favorite Matrices in These Classes
    286(5)
    IV Designs, Geometry, Packing and Covering 291(118)
    16 Some New Families of 2-Resolutions
    293(8)
    Michael Hurley
    Oscar Lopez
    Spyros S. Magliveras
    16.1 Introduction
    293(1)
    16.2 Preliminaries
    294(1)
    16.3 Incidence Matrices
    295(2)
    16.4 The Half-Affine Group
    297(1)
    16.5 A New Family of 2-Resolutions
    297(2)
    16.6 Conclusion
    299(2)
    17 Graphical Designs
    301(18)
    Donald L. Kreher
    17.1 Introduction
    301(1)
    17.2 Graphical Designs
    302(1)
    17.3 Orbits of Sn Acting on E(Kn)
    302(2)
    17.4 Steiner Graphical Designs
    304(6)
    17.5 Steiner Bigraphical Designs
    310(1)
    17.5.1 Remarks on the 5-(16, {6,8}, 1) Design
    311(1)
    17.6 Steiner Graphical Designs of Type nr
    311(1)
    17.7 Higher Index
    312(2)
    17.8 Historical Remarks
    314(5)
    18 There Must be Fifty Ways to Miss a Cover
    319(16)
    Charles J. Colbourn
    Violet R. Syrotiuk
    18.1 Introduction
    319(1)
    18.2 Combinatorics of Interaction Testing
    320(3)
    18.2.1 Covering Arrays
    321(1)
    18.2.2 Locating and Detecting Arrays
    321(1)
    18.2.3 Prior Work
    322(1)
    18.3 A Construction from One-factorizations
    323(7)
    18.4 Concluding Remarks
    330(5)
    19 Combinatorial Designs and Cryptography, Revisited
    335(24)
    Douglas R. Stinson
    19.1 Introduction
    336(1)
    19.2 The One-time Pad and Shannon's Theory
    337(2)
    19.3 Threshold Schemes and Ramp Schemes
    339(4)
    19.3.1 Ramp Schemes
    341(2)
    19.4 All-or-Nothing Transforms
    343(4)
    19.4.1 Binary AONT with t = 2
    344(2)
    19.4.2 General AONT with t = 2
    346(1)
    19.5 Algebraic Manipulation Detection Codes
    347(7)
    19.5.1 Weak and Strong AMD Codes
    347(1)
    19.5.2 An Application of AMD Codes to Threshold Schemes
    348(1)
    19.5.3 Combinatorial Analysis of AMD Codes
    349(3)
    19.5.4 Nonuniform AMD Codes
    352(2)
    19.6 Conclusion and Open Problems
    354(5)
    20 A Survey of Scalar Multiplication Algorithms
    359(28)
    Koray Karabina
    20.1 Introduction
    359(6)
    20.1.1 Cryptographic Applications
    360(1)
    20.1.2 Multidimensional Scalar Multiplication and Endomorphisms
    361(1)
    20.1.3 Signed Digit Recodings and Differential Additions
    362(1)
    20.1.4 Side Channel Attacks and Regular Recodings
    363(1)
    20.1.5 Organization of the
    Chapter
    363(2)
    20.2 Variable Scalar and Variable Base
    365(10)
    20.2.1 Width-w Window Methods
    365(4)
    20.2.2 Signed Digit Recoding Methods
    369(3)
    20.2.3 Regular Recoding Methods
    372(3)
    20.3 Variable Scalar and Fixed Base
    375(12)
    20.3.1 Split and Comb Methods
    376(3)
    20.3.2 A Euclidean Type Algorithm
    379(1)
    20.3.3 Regular Recoding Methods
    380(7)
    21 Arcs, Caps, Generalisations: Results and Problems
    387(22)
    Joseph A. Thas
    21.1 Introduction
    387(1)
    21.2 k-Arcs of PG(2, q)
    388(1)
    21.3 Complete Arcs
    389(2)
    21.4 k-Caps and Ovoids
    391(2)
    21.5 Ovoids and Inversive Planes
    393(1)
    21.6 k-Caps and Cap-Codes
    394(1)
    21.7 k-Caps in PG(n,q),n > or = to 3
    395(2)
    21.8 Generalised k-Arcs and Generalised k-Caps
    397(1)
    21.9 Generalised Ovals and Ovoids
    398(2)
    21.10 Regular Pseudo-Ovals and Pseudo-Ovoids
    400(1)
    21.11 Translation Duals
    400(1)
    21.12 Characterisations of Pseudo-Ovals and Pseudo-Ovoids
    401(2)
    21.13 Problems
    403(6)
    21.13.1 Problems on Arcs
    403(1)
    21.13.2 Problems on Caps
    403(1)
    21.13.3 Problems on Generalised k-Arcs and Generalised k-Caps
    403(6)
    Index 409
    Fan Chung received her PhD from University of Pennsylvania in 1974. She is a Distinguished Professor of Mathematics, Professor of Computer Science and Engineering, and the Paul Erds Professor in Combinatorics at the University of California, San Diego. She has written three books, Spectral Graph Theory, Complex Graphs and Networks (with Lincoln Lu), and Erds on Graphs (with Ron Graham) and almost 300 papers. She is a member of the American Academy of Arts and Sciences, is an academician of Academic Sinica, and is a fellow of the American Mathematical Society and the Society for Industrial and Applied Mathematics. Her website is http://math.ucsd.edu/~fan/.

    Ron Graham received his Ph. D. from the University of California at Berkeley in

    1962. He holds the Irvin and Joan Jacobs Endowed Chair Professorship in the Computer Science and Engineering department of University of California at San Diego and was formerly at AT&T Bell Laboratories and Rutgers University. He has more than 350 publications. He is a member of the National Academy of Sciences and is a Fellow of the Association of Computing Machinery and the American Mathematical Society. He was the president of the American Mathematical Society from 1993 to 1995 and the president of the Mathematical Association of America from 2003 to 2005. His website is https://cseweb.ucsd.edu/~rgraham/.

    Frederick Hoffman received his PhD from University of Virginia in 1964. He was a Founding Fellow of The Institute of Combinatorics and its Applications and serves on its Council. He has directed thirty-nine of the Southeastern International Conferences on Combinatorics, Graph Theory and Computing. He served as President and Governor of the Florida Section of the Mathematical Association of America and chaired the national MAA committee on mini-courses. He has published more than 20 papers. His website is http://www.math.fau.edu/people/faculty/

    hoffman.php.

    Leslie Hogben received her PhD from Yale in 1978. She is the Dio Lewis Holl Chair in Applied Mathematics, a Professor of Mathematics, and an Associate Dean of the College of Liberal Arts and Sciences at Iowa State University, and the Associate Director for Diversity of the American Institute of Mathematics. She is the author of more than 100 papers and is the editor of the books Handbook of Linear Algebra and Recent Trends in Combinatorics (with Andrew Beveridge, Jerrold R. Griggs, Gregg Musiker, Presad Tetali). She serves on the Scientific Review Panel of the Atlantic Association for Mathematical Research (Canada) and the editorial boards of several journals. Her webpage is https://orion.math.iastate.edu/lhogben/

    homepage.html.

    Ronald C. Mullin received his PhD from the University of Waterloo in 1964.

    He is a Distinguished Professor of Combinatorics and Optimization (Emeritus)

    at University of Waterloo and Professor of Mathematics Emeritus at Florida Atlantic University. He is the author of more than 180 papers. He is the first recipient of the Stanton Medal, which is awarded by the Institute for Combinatorics and its Applications (ICA). His website is https://uwaterloo.ca/

    combinatorics-and-optimization/about/people/rcmullin.

    Douglas B. West received his PhD from MIT in 1978. After retiring from the faculty at the University of Illinois, in 2012 he moved to Zhejiang Normal University under the 1000 Talents Plan. He has written about 250 papers and the books Introduction to Graph Theory and Combinatorial Mathematics. He is the Editor-in-Chief of the journal Discrete Mathematics and an Associate Editor of Order and the American Mathematical Monthly. His website is https://faculty.math.illinois.edu/

    ~west/.