Discrete Mathematics and Applications

Preface......Page 6
Contents......Page 8
1 Introduction, Definitions, Notation......Page 15
2 The Main Result......Page 17
References......Page 20
Combinatorial Identities and Inequalities for Trigonometric Sums......Page 21
1.1 The Combinatorial Identity......Page 22
1.2 Vandermonde's Convolution Formula......Page 23
1.3 Harmonic Numbers......Page 24
1.4 Trigonometric Sums......Page 25
2 Proofs of Theorem 1......Page 28
3 Proof of Theorem 2......Page 31
4 Proof of Theorem 3......Page 32
5 Lemmas......Page 34
6 Proof of Theorem 4......Page 42
7 Proof of Theorem 5......Page 43
References......Page 47
1 Introduction......Page 48
2 k-Partitions of Multisets with Equal Sums......Page 51
3 k-Partitions with Equal Sums of the Set [n]......Page 54
4 A Family of Diophantine Equations Defined by Qk(n)......Page 56
4.1 Proof of Theorem 6......Page 60
4.2 The Proof of Theorem 7......Page 63
5 Final Comments on the Family of Diophantine Equations......Page 66
References......Page 67
1 Introduction......Page 69
2 The Exponent of a Group: General Properties......Page 71
3 Computing the Exponent......Page 72
4 The Automorphism Group......Page 76
4.1.2 `3́9`42`"̇613A``45`47`"603AAut(Z/nZ)......Page 77
4.1.3 `3́9`42`"̇613A``45`47`"603AAut(G) for G Finite and Abelian......Page 78
4.2 The Automorphism Group and the Exponent......Page 79
4.3 The Power Endomorphisms of a Group......Page 81
5 The Automorphism Group of a Direct Product of fe-Groups......Page 86
6 Sets and Sequences of Numbers Associated with a Group......Page 90
7 The Set of Elements of Order k in a Group G......Page 91
7.1 The Greatest Order in a Torsion Group......Page 95
7.2 m2(Sn) and |`3́9`42`"̇613A``45`47`"603AEnd(Sn)|......Page 97
8 Structure Theorems for Groups with a Prescribed Number of Elements of a Given Order......Page 100
9.1 Group Actions......Page 104
9.3 The Number of Conjugacy Classes in Sn......Page 106
9.4 Burnside's Lemma......Page 107
9.5 Frobenius Theorem and Some Applications......Page 108
10 The Order-Counting Sequence......Page 111
10.1 The mk and Θk Invariances for Finite Abelian Groups......Page 112
11 The Exponent of the Group `3́9`42`"̇613A``45`47`"603AGLn(R)......Page 113
11.1 The Group `3́9`42`"̇613A``45`47`"603AGLn(Z/mZ)......Page 114
11.2 The Exponent of `3́9`42`"̇613A``45`47`"603ASL2(Z/2n Z) and `3́9`42`"̇613A``45`47`"603AGL2(Z/2nZ)......Page 116
11.3 The Groups `3́9`42`"̇613A``45`47`"603ASL2(Z/3n Z) and `3́9`42`"̇613A``45`47`"603AGL2(Z/3n Z)......Page 117
References......Page 119
Hankel Tournaments and Special Oriented Graphs......Page 121
1 Introduction......Page 122
2 Locally Transitive Tournaments......Page 125
3 Hankel Cycles......Page 135
4 A Special Hankel Tournament......Page 142
5 Oriented Graphs......Page 145
6 Hankel 2-Tournaments......Page 151
References......Page 164
1 Introduction......Page 165
2 Lower Bound......Page 167
2.1 Proof of Lemma 1......Page 168
3.1 Simple Density Properties......Page 170
3.2 The Verification of P1–P4: Constructing U1......Page 176
3.3 The Verification of P1–P4: Constructing U2......Page 182
3.4 The Verification of P1–P4: Constructing U2......Page 184
3.5 The Verification of P1–P4: Constructing U3......Page 185
References......Page 186
1 Introduction......Page 188
2 The Basics......Page 193
3 Few Rows......Page 194
4 The Connection with Codes......Page 198
5 Asymptotic Bounds and Algorithms......Page 200
6 Concluding Remarks......Page 205
References......Page 206
1 Introduction......Page 209
2 Structural Lemma......Page 210
3 Proof of Theorem 1......Page 212
References......Page 215
1 Introduction......Page 216
2 Counting Prime Differences......Page 219
3 The Hardy–Littlewood Prime Pair Conjecture......Page 223
4 Numerical Tests of the Hardy–Littlewood Conjecture......Page 224
5 Sketch of Solution of the PDC Problem Using Conjecture 1......Page 228
6 Proof of Theorem 1......Page 232
7 Logarithmically Weighted Sums and Products of Primes......Page 238
8 The Prime Difference Champions Go to Infinity......Page 239
References......Page 244
Exponential Variational Integrators Using Constant or Adaptive Time Step......Page 246
1 Introduction......Page 247
2 The Advantages of Variational Integrators......Page 249
3 Exponential Integrators......Page 251
3.2 Estimation of Frequency in Three Dimensional Particle Motions......Page 252
3.3.1 Planar Two-Body Problem......Page 254
3.3.2 The Modified Solar System......Page 256
4 Derivation of Time Adaptive Integrators Through the Geodesic Approach......Page 257
5 Time Adaptive Exponential Variational Integrators......Page 259
6.1 Harmonic Oscillator......Page 261
6.2 Orbits of the Two-Body Problem with Extremely High Eccentricities......Page 263
7 Conclusions......Page 264
Appendix......Page 265
References......Page 266
1 Introduction......Page 268
1.2 Main Result......Page 270
2.1 Setup......Page 271
2.2 Preliminaries......Page 272
3 Case: G[R] Does Not Have a Hamiltonian Path......Page 280
4 Case: G[R] Has a Hamiltonian Path and k ≥ 3......Page 287
5 Case: G[R] Has a Hamiltonian Path and k = 2......Page 302
6 Proof of Theorem 6......Page 311
References......Page 313
1 Introduction......Page 314
2 The Extension T of the Collatz Map......Page 318
3 The Binary Graph Arising from the Map T......Page 325
4 The Sequence of Signs (-1)Ti(n) and the T-Tree G(T)......Page 331
5 Collatz Transition and Cyclotomy......Page 334
6 The New Structure as a Direct System......Page 338
References......Page 346
1 Introduction......Page 347
2 Diffusion Equations and Equilibrium Points......Page 349
2.1 Connectivity and Equilibria......Page 352
2.1.1 Connected and Unconnected Network......Page 353
3.1 Case 1: At Least One Non-zero Element per Line to the Adjacent Operator......Page 355
3.1.1 Conclusion......Page 357
3.2 Case 2: Adjacent Operator with Two Lines Equals to Zero......Page 358
4 Differential Equation and Its Solution......Page 359
5.1 Case 1: Two Real Negatives Eigenvalues and One Zero......Page 361
5.2 Case 2: Two Complex Eigenvalues with Negative Real Part and One Zero......Page 363
5.3 Case 3: Three Real Negative Eigenvalues......Page 365
5.3.1 Conclusion......Page 367
5.4.1 Review Case 5.1......Page 368
6 Case Study in a Banking Network......Page 369
Reference......Page 375
1 Introduction......Page 376
2 Literature Review......Page 378
3 Interbank Networks and Default Contagion......Page 379
4 The Bankruptcy Set of the Institution x......Page 381
4.2 Maximal and Minimal Elements of the Bankruptcy set Ux......Page 382
5 The Contagion Map......Page 385
5.2 The Contagion Vector......Page 387
6 Boolean Dynamical Systems......Page 388
7 Fixed Points of the Function F......Page 390
8 The Global Function......Page 393
9.1 Assessment of Banks......Page 394
9.2 Assessment of Interbank Networks......Page 395
10 Example......Page 396
10.1.1 First Method......Page 398
10.1.2 Second Method......Page 399
10.1.3 Third Method......Page 400
References......Page 401
1 Introduction......Page 403
2 Construction of the Matrix M......Page 406
4 Conclusion of the Proof......Page 408
References......Page 409
1 Introduction......Page 411
3 Diagonal Ramsey Numbers......Page 412
4 Off-Diagonal Ramsey Numbers......Page 413
5 The Erdős–Hajnal Problem......Page 414
6 The Erdős–Rogers Problem......Page 417
7 The Erdős–Gyárfás–Shelah Problem......Page 418
8.2 Independent Neighborhoods......Page 420
8.3 Cycles Versus Cliques......Page 421
8.3.1 Loose Cycles Versus Cliques......Page 422
8.3.2 Tight Cycles Versus Cliques......Page 423
9 Bounded Degree Hypergraphs......Page 424
10.1 Tight-Paths and Cliques in Hypergraphs......Page 425
10.2 Ordered -Power Paths in Graphs......Page 428
11 A Bipartite Hypergraph Ramsey Problem of Erdős......Page 429
References......Page 430
1 Introduction......Page 435
2 Preliminaries......Page 436
3 Main Results......Page 437
4 Example Problems......Page 441
References......Page 444
1 Introduction......Page 446
2 Preliminaries......Page 447
3.1 A Method of Generating Fuzzy Implications from Two Fuzzy Implications and a Fuzzy Negation......Page 449
3.2 A Method of Generating Fuzzy Implications from Two Fuzzy Implications, a Fuzzy Negation, and an IncreasingFunction......Page 453
3.3 A Method of Generating Fuzzy Implications from Two Fuzzy Implications and Two Fuzzy Negations......Page 455
3.4 A Method of Generating Fuzzy Implications from Two Fuzzy Negations and an Increasing Function......Page 457
3.5 A Method of Generating Fuzzy Implications from a t-Conorm, an Increasing Function, a Decreasing Function, and Two Fuzzy Implications......Page 460
References......Page 462
1 Introduction......Page 464
2 Average Degree......Page 466
3 Median Degree......Page 468
4 Minimum Degree......Page 470
5 Maximum and Minimum Degree......Page 472
6 Expanders and Random Graphs......Page 475
7 Ramsey Numbers......Page 477
8 Directed Graphs......Page 480
9.1 Tight Hypertrees......Page 484
9.2 Expansions of Trees and Linear Paths......Page 485
9.3 Berge Hypertrees......Page 486
References......Page 487
1 Introduction and Preliminaries......Page 492
2 Extremal Graphs with Regard to Their Nullity/Rank......Page 493
2.1 Trees......Page 495
2.2 Bipartite Graphs......Page 496
2.3 Unicyclic, Bicyclic, and Tricyclic Graphs......Page 497
3 Characterization of Singular Graphs with Other Given Parameters......Page 500
References......Page 502