(YES) - included; (NO) - explicitly excluded;
as stated from the IOI syllabus(2019);
5.2 Discrete Structures (DS)
DS1. Functions, relations, and sets
(YES)Functions (surjections, injections, inverses, composition)
(YES) Relations (reflexivity, symmetry, transitivity, equivalence relations, total/linear order relations, lexicographic order)
(YES) Sets (inclusion/exclusion, complements, Cartesian products, power sets)
(NO) Cardinality and countability (of infinite sets)
DS2. Basic logic
(YES) First-order logic
(YES) Logical connectives (incl. their basic properties)
(YES) Truth tables
(YES)Universal and existential quantification(Note: statements should avoid definitions with nested quantifiers whenever possible.)
(YES) Modus ponens and modus tollens
(YES)Normal forms
(NO) Validity
(NO) Limitations of predicate logic
DS3. Proof techniques
(YES) Notions of implication, converse, inverse, contrapositive, negation, and contradiction Direct proofs, proofs by: counterexample, contraposition, contradiction
(YES) Mathematical induction
(YES)Strong induction (also known as complete induction)
(YES)Recursive mathematical definitions (incl. mutually recursive definitions)
DS4. Basics of counting
(YES) Counting arguments (sum and product rule, arithmetic and geometric progressions, Fibonacci numbers)
(YES) Permutations and combinations (basic definitions)
(YES)Factorial function, binomial coefficients
(YES) Inclusion-exclusion principle
(YES) Pigeonhole principle
(YES) Pascal’s identity, Binomial theorem
(NO)Solving of recurrence relations
(NO)Burnside lemma
DS5. Graphs and trees
(YES)Trees and their basic properties, rooted trees
(YES)Undirected graphs (degree, path, cycle, connectedness,
Euler/Hamilton path/cycle, handshaking lemma)
(YES) Directed graphs (in-degree, out-degree, directed path/cycle, Euler/Hamilton path/cycle) (YES) Spanning trees
(YES) Traversal strategies
(YES) ‘Decorated’ graphs with edge/node labels, weights, colors
(YES) Multigraphs, graphs with self-loops
(YES) Bipartite graphs
(YES) Planar graphs
(NO)Hypergraphs
(NO)Specific graph classes such as perfect graphs
(NO)Structural parameters such as treewidth and expansion
(NO)Planarity testing
(NO)Finding separators for planar graphs
DS6. Discrete probability
Applications where everything is finite (and thus arguments about probability can be easily turned into combinatorial arguments) are (YES), everything more complicated is (NO)
I am preparing for IOI and want a good discrete structure book/resource to learn the above mentioned subjects.
I am currently taking Pre-Calculus relevant Mathematics in my country. I am in 10th grade, India.
I have searched for courses and books but I don't how to find a good one.
Any recommendations and edits are welcome.
