Preface |
|
xv | |
Editors |
|
xxiii | |
Contributors |
|
xxv | |
|
1 Personal Reflections of the SEICCGTC: Origins and Beyond |
|
|
1 | (18) |
|
|
|
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) |
|
|
9 | (2) |
|
1.6 Some Non-Conference Activities at the Conferences |
|
|
11 | (2) |
|
|
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) |
|
|
|
21 | (1) |
|
|
21 | (1) |
|
|
22 | (2) |
|
|
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) |
|
|
32 | (5) |
|
3 Variations on the Sequenceable Theme |
|
|
37 | (18) |
|
|
|
37 | (3) |
|
3.2 Strongly Sequenceable Groups |
|
|
40 | (1) |
|
3.3 Orthogonal Decompositions |
|
|
41 | (1) |
|
|
42 | (2) |
|
|
44 | (2) |
|
|
46 | (1) |
|
3.7 Partial Steiner Triple Systems |
|
|
47 | (3) |
|
|
50 | (1) |
|
|
50 | (5) |
|
4 A Survey of Stack Sortable Permutations |
|
|
55 | (18) |
|
|
|
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) |
|
|
58 | (7) |
|
|
58 | (2) |
|
4.3.2 A Surprising Connection with the Pattern 1324 |
|
|
60 | (1) |
|
|
61 | (1) |
|
|
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) |
|
|
67 | (3) |
|
|
70 | (3) |
|
5 Dimension for Posets and Chromatic Number for Graphs |
|
|
73 | (24) |
|
|
|
73 | (3) |
|
5.1.1 Basic Concepts and Results for Dimension |
|
|
74 | (2) |
|
|
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) |
|
|
83 | (5) |
|
5.4 Blocks in Posets and Graphs |
|
|
88 | (9) |
|
5.4.1 Open Problems Involving Cover Graphs |
|
|
90 | (7) |
|
|
97 | (12) |
|
|
|
97 | (1) |
|
|
98 | (1) |
|
6.3 Avoiding Monochromatic Sets |
|
|
99 | (3) |
|
|
102 | (2) |
|
|
104 | (1) |
|
|
105 | (4) |
II Graph Theory |
|
109 | (102) |
|
7 Developments on Saturated Graphs |
|
|
111 | (24) |
|
|
|
111 | (2) |
|
|
113 | (5) |
|
|
114 | (3) |
|
|
117 | (1) |
|
|
117 | (1) |
|
7.3 Limits On The Saturation Function |
|
|
118 | (1) |
|
|
119 | (1) |
|
|
120 | (4) |
|
|
124 | (12) |
|
|
124 | (3) |
|
7.6.2 Edge-Colored Saturation |
|
|
127 | (1) |
|
7.6.3 Other Variations and Results |
|
|
128 | (7) |
|
|
135 | (20) |
|
|
|
136 | (2) |
|
|
136 | (1) |
|
8.1.2 The Classical Magic Arrays |
|
|
136 | (1) |
|
|
137 | (1) |
|
8.2 Edge-Magic Total Labelings |
|
|
138 | (7) |
|
|
138 | (1) |
|
|
138 | (1) |
|
8.2.1.2 Some Elementary Counting |
|
|
138 | (1) |
|
|
140 | (1) |
|
8.2.2 Cliques and Complete Graphs |
|
|
140 | (1) |
|
|
140 | (1) |
|
8.2.2.2 Complete Subgraphs |
|
|
142 | (1) |
|
|
143 | (1) |
|
8.2.3.1 Generalizations of Cycles |
|
|
143 | (1) |
|
8.2.4 Complete Bipartite Graphs |
|
|
143 | (1) |
|
|
144 | (1) |
|
8.3 Vertex-Magic Total Labelings |
|
|
145 | (10) |
|
|
145 | (1) |
|
|
145 | (1) |
|
|
145 | (2) |
|
|
147 | (1) |
|
8.3.3 Some Standard Graphs |
|
|
147 | (1) |
|
|
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) |
|
|
149 | (1) |
|
8.3.4 Graphs with Vertices of Degree One |
|
|
149 | (6) |
|
9 Block Colorings of Graph Decompositions |
|
|
155 | (16) |
|
|
|
|
155 | (4) |
|
|
159 | (2) |
|
9.3 Amalgamations and Recent Results |
|
|
161 | (5) |
|
|
166 | (5) |
|
10 Reconfiguration of Colourings and Dominating Sets in Graphs |
|
|
171 | (22) |
|
|
|
|
171 | (2) |
|
|
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) |
|
|
185 | (1) |
|
|
186 | (1) |
|
|
186 | (7) |
|
11 Edge Intersection Graphs of Paths on a Grid |
|
|
193 | (18) |
|
|
|
|
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) |
|
|
|
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) |
|
|
222 | (1) |
|
12.2.6 The Quantum Walk Matrix |
|
|
223 | (1) |
|
12.3 Strengths and Weaknesses of Different Matrices |
|
|
223 | (7) |
|
|
224 | (1) |
|
|
224 | (2) |
|
12.3.3 A Line Graph Excursion |
|
|
226 | (1) |
|
12.3.4 Graphs Determined by Their Spectrum |
|
|
227 | (1) |
|
|
228 | (1) |
|
12.3.6 Graphs that Have a Common Spectrum |
|
|
228 | (2) |
|
|
230 | (4) |
|
12.4.1 Bottlenecks and Cheeger Constants |
|
|
230 | (1) |
|
12.4.2 Discrepancy and the Value of Normalizing |
|
|
231 | (2) |
|
|
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) |
|
|
|
|
|
239 | (3) |
|
|
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) |
|
|
255 | (1) |
|
|
256 | (1) |
|
13.5 Concluding Remarks and Open Problems |
|
|
257 | (6) |
|
|
263 | (14) |
|
|
|
263 | (1) |
|
|
264 | (2) |
|
|
266 | (3) |
|
14.4 Rank Functions in Graph Theory |
|
|
269 | (3) |
|
|
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) |
|
|
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) |
|
|
|
|
|
293 | (1) |
|
|
294 | (1) |
|
|
295 | (2) |
|
16.4 The Half-Affine Group |
|
|
297 | (1) |
|
16.5 A New Family of 2-Resolutions |
|
|
297 | (2) |
|
|
299 | (2) |
|
|
301 | (18) |
|
|
|
301 | (1) |
|
|
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) |
|
|
312 | (2) |
|
|
314 | (5) |
|
18 There Must be Fifty Ways to Miss a Cover |
|
|
319 | (16) |
|
|
|
|
319 | (1) |
|
18.2 Combinatorics of Interaction Testing |
|
|
320 | (3) |
|
|
321 | (1) |
|
18.2.2 Locating and Detecting Arrays |
|
|
321 | (1) |
|
|
322 | (1) |
|
18.3 A Construction from One-factorizations |
|
|
323 | (7) |
|
|
330 | (5) |
|
19 Combinatorial Designs and Cryptography, Revisited |
|
|
335 | (24) |
|
|
|
336 | (1) |
|
19.2 The One-time Pad and Shannon's Theory |
|
|
337 | (2) |
|
19.3 Threshold Schemes and Ramp Schemes |
|
|
339 | (4) |
|
|
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) |
|
|
|
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) |
|
|
|
387 | (1) |
|
|
388 | (1) |
|
|
389 | (2) |
|
|
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) |
|
|
400 | (1) |
|
21.12 Characterisations of Pseudo-Ovals and Pseudo-Ovoids |
|
|
401 | (2) |
|
|
403 | (6) |
|
|
403 | (1) |
|
|
403 | (1) |
|
21.13.3 Problems on Generalised k-Arcs and Generalised k-Caps |
|
|
403 | (6) |
Index |
|
409 | |