Bachelor
2021/2022

# Combinatorics, Graphs and Computational Logic

Type:
Elective course (Applied Mathematics and Information Science)

Area of studies:
Applied Mathematics and Information Science

Delivered by:
School of Data Analysis and Artificial Intelligence

Where:
Faculty of Computer Science

When:
3 year, 3, 4 module

Mode of studies:
offline

Open to:
students of one campus

Instructors:
Denis Fedyanin

Language:
English

ECTS credits:
6

Contact hours:
80

### Course Syllabus

#### Abstract

The course «Combinatorics, Graphs, and Computational Logic» provides strong ideas to combine logic theories (reasoning, arguments, epistemic logic, proofs), graphs theories (social networks, random graphs, transport, argumentations), and combinatorics theories (enumerations, complexity, probability) for analysis of multiagent behavior datasets. It is a high intense course and it might be recommended for advanced students who are capable to move fast through very different domains. The course contains only ideas of the proofs and many very basic facts from logic, graphs, and combinatorics are omitted assuming that students have already taken any Discrete Math Course. It was done to focus on applications to computer science rather than on the beauty of math proofs.

#### Learning Objectives

- Knowledge of the specific properties of data on multi-agent systems, including social networks.
- Ability to use combinatorics to assess the likelihood of data corruption, the presence of data properties, and assess the likelihood of a system's behavior in the future.
- The practice of evaluating the complexity of data analysis algorithms using combinatorics, including the algorithms for checking the consistency of datasets and other properties.
- Application of logic to check the correctness of algorithms.

#### Expected Learning Outcomes

- Ability to calculate the probability of a formula being satisfied according to the given probabilities of other formulas.
- Knowledge about important properties of traffic graphs and the prediction of dynamics.
- Knowledge about logic in programming, checking the correctness of programs, elements of proof theory.
- Knowledge about modal and epistemic logic, Binary Decision Tree as a partial solution to the complexity curse, making decisions in multi-agent systems, the complexity of manipulation in Social Choice problems. o Shapley vector and corporate game theory.
- Knowledge about model checking tasks for given sets, the relationship between set algebra and Boolean logic, the complexity of deducing theorems from axioms, completeness concept, connection with data compression.
- Knowledge about polysemy in linguistics and combinatorics, graphs of abstract argumentation - open problem argument extraction, properties of graphs of abstract argumentation, the problem of propagating arguments on graphs.
- Knowledge about properties of multiagent systems datasets, properties of social media data, social media metrics, text datasets of social networks, equilibrium in social systems, game theory, behavior prediction, search for anomalies in datasets
- Knowledge about the application of group theory in data analysis, Poya's theorem (without proof), indistinguishability in logic, common knowledge of robots, enumerations for graphs, the complexity of some famous algorithms.
- Knowledge about the inconsistency and incompleteness of data, evaluation of the probability of the truth of the formula (as a response to a binary query to the database) with incomplete or conflicting information, difficulty performing an assessment of inconsistency, relationship with modal logic, and classification of requests
- Knowledge about the relationship between probability and combinatorics, basic combinatorial formulas, probability of having a property in the database, social networks models, random graphs, the idea of the proof of connectivity, the concept of hypergraphs.

#### Course Contents

- Introduction to applications of Combinatorics, Graphs, and Logic
- Combinatorics and probability of having properties in datasets.
- Model-checking problems.
- Conditional probabilities and reasoning.
- The enumeration in datasets and estimation of datasets sizes.
- Complexity in social choice problems, cooperative decision making, and epistemic logic.
- Important properties of traffic graphs and prediction of dynamics.
- Inconsistency and incompleteness of data.
- Combinatorics and logic in argumentation graphs and linguistics.
- Logic in programming and automatic proofs.

#### Interim Assessment

- 2021/2022 4th module0.3 * Контрольная работа + 0.3 * Контрольная работа + 0.4 * Экзамен

#### Bibliography

#### Recommended Core Bibliography

- A course in combinatorics, Lint van, J. H., 2004
- A first course in graph theory and combinatorics, Cioaba, S. M., 2009
- Algorithms, DasGupta, S., 2018
- An introduction to mathematical reasoning : numbers, sets and functions, Eccles, P. J., 2013
- Arguments and actions in social theory, Preston, P., 2009
- Data and evidence in linguistics : a plausible argumentation model, Kertesz, A., 2012
- Discrete mathematics : proofs, structures, and applications, Garnier, R., 2010
- Enumerative combinatorics. Vol.1: ., Stanley, R. P., 2012
- Enumerative combinatorics. Vol.2: ., Stanley, R. P., 2004
- Epistemic logic for AI and computer science, Meyer, J.-J. C., 2004
- Epistemic logic planning : case-based planning adaptation, using epistemic logic revision for robot's decision making, Maghsoudi, S., 2008
- Exponential random graph models for social networks : theory, methods, and applications, , 2013
- Graph theory and combinatorial optimization, , 2005
- Graph theory and interconnection networks, Hsu, L. H., 2009
- Graph theory, combinatorics and algorithms : interdisciplinary applications, , 2005
- Handbook of social choice and welfare. Vol.1: ., , 2002
- Handbook of social choice and welfare. Vol.2: ., , 2011
- How to map arguments in political science, Parsons, C., 2010
- Human behaviour and traffic networks, , 2004
- Introduction to enumerative combinatorics, Bona, M., 2007
- Introduction to graph theory, Voloshin, V. I., 2009
- Knowledge and social structure : an introduction to the classical argument in the sociology of knowledge, Hamilton, P., 2015
- Knowledge representation and reasoning, Brachman, R. J., 2004
- Logic and social choice, Murakami, Y., 2016
- Logic in computer science : modelling and reasoning about systems, Huth, M., 2004
- Mathematical logic for computer science, Ben-Ari, M., 2012
- Mathematical structures for computer science : a modern approach to discrete mathematics, Gersting, J., 2007
- Mathematical tools for data mining : set theory, partial orders, combinatorics, Simovici, D. A., 2008
- Multiagent systems : algorithmic, game-theoretic, and logical foundations, Shoham, Y., 2009
- Propositional and predicate calculus : a model of argument, Goldrei, D., 2005
- Random graphs, Bollobas, B., 2001
- Rational choice politics. Vol.1: Social choice, equilibrium and electoral systems, , 2009
- Reasoning about knowledge, , 2003
- Structural proof theory, Negri, S., 2008
- Theory of social choice on networks : preference, aggregation, and coordination, Stirling, W. C., 2016
- Topics in structural graph theory, , 2013
- Верификация моделей программ: Model Checking, Кларк, мл., Э. М., 2002

#### Recommended Additional Bibliography

- Algorithms and complexity, Wilf, H. S., 2002
- Analogies and theories : formal models of reasoning, Gilboa, I., 2015
- Graphs, networks and algorithms, Jungnickel, D., 2005