Surveys in Combinatorics 2021 / edited by Konrad K. Dabrowski [and others].

Format:

Book

Contributor:

Dabrowski, Konrad, editor.

Series:

London Mathematical Society lecture note series.

London Mathematical Society lecture note series

Language:

English

Subjects (All):

Combinatorial analysis--Congresses.

Combinatorial analysis.

Physical Description:

1 online resource (vii, 369 pages) : digital, PDF file(s).

Place of Publication:

Cambridge : Cambridge University Press, 2021.

Summary:

This volume contains nine survey articles based on plenary lectures given at the 28th British Combinatorial Conference, hosted online by Durham University in July 2021. This biennial conference is a well-established international event, attracting speakers from around the world. Written by some of the foremost researchers in the field, these surveys provide up-to-date overviews of several areas of contemporary interest in combinatorics. Topics discussed include maximal subgroups of finite simple groups, Hasse-Weil type theorems and relevant classes of polynomial functions, the partition complex, the graph isomorphism problem, and Borel combinatorics. Representing a snapshot of current developments in combinatorics, this book will be of interest to researchers and graduate students in mathematics and theoretical computer science.

Contents:

Cover

Series information

Title page

Copyright information

Contents

Preface

The partition complex: an invitation to combinatorial commutative algebra

1 Introduction

1.1 Overview

2 Preliminaries

2.1 Simplicial complexes and face rings

2.2 Chain complexes

2.3 Double complexes

3 Cohen-Macaulay Complexes and why we care

3.1 The Basic Idea

3.2 The Koszul Complex

4 The Partition Complex &amp

Reisner's Theorem

4.1 The Partition Complex

4.2 Reisner's Theorem

5 Partition of Unity

5.1 The homology of Tot(P[sup(*)] [otimes] K[sup(*)])

6 Schenzel's Formula

7 Poincar[acute(e)] duality

7.1 Poincar[acute(e)] duality algebras in general

7.2 Poincar[acute(e)] duality for face rings of manifolds

7.3 Further remarks on Poincar[acute(e)] duality

8 Applications: Triangulations and a conjecture of K[ddot(u)]hnel

8.1 The inductive principle and partition of unity

8.2 K[ddot(u)]hnel's efficient triangulations of manifolds

9 Applications: Subdivisions and the almost-Lefschetz property

9.1 Complexes and subdivisions

9.2 Partition of unity for disks with induced boundary

9.3 The Koszul complex and the Lefschetz property

9.4 A modified partition complex

9.5 Proof of the subdivision theorem

Hasse-Weil type theorems and relevant classes of polynomial functions

2 Hasse-Weil type theorems

3 Preliminaries on algebraic varieties and function fields

3.1 Plane curves

3.2 Link with function field theory

3.3 Equivalence of curves

3.4 Kummer or Artin-Schreier covers of curves

4 Strategies to investigate the algebraic variety

4.1 A method based on intersection multiplicities

4.2 Connection with algebraic hypersurfaces

5 Permutation polynomials and permutation rational functions.

5.1 Basic definitions and connections with algebraic curves

5.2 Exceptional polynomials and Carlitz Conjecture

5.3 A way to decrease the degree of the curve C[sub(f)]

5.4 PPs of index [ell] = q + 1 in F[sub(q[sup(2)])] and generalized Niho exponents

5.5 Carlitz rank of a permutation polynomial

5.6 Complete permutation polynomials and generalization

5.7 Permutation rational functions

6 Minimal value set polynomials and minimal value set rational functions

7 Kloosterman polynomials

8 o-polynomials

9 Scattered polynomials and maximum scattered linear sets

9.1 Exceptional scattered polynomials

9.2 Families of non-exceptional scattered polynomials

10 Planar functions in odd characteristic

10.1 Planar monomials

10.2 Planar polynomials

10.3 A generalization of planar functions

11 Planar functions in even characteristic

11.1 Planar monomials

11.2 Planar polynomials

11.3 Non-exceptional planar polynomials

12 APN functions

12.1 APN monomials

12.2 APN polynomials

Decomposing the edges of a graph into simpler structures

2 What is a discharging argument?

3 A toy problem for discharging

4 Local arguments in discharging

4.1 One reducible configuration, no discharging rule

4.2 Two configurations, two discharging rules

4.3 Three reducible configurations, two discharging rules

4.4 Shifting the density argument to a subgraph of G

4.5 Shifting the notion of minimality

4.6 Ghost vertices

5 Global arguments in discharging

5.1 Alternating cycles

5.2 Beyond alternating cycles

6 Re-colouring

6.1 As an intermediary step

6.2 As a more general tool

7 Conclusion

Generating graphs randomly

2 Preliminaries and Background

2.1 Notation and assumptions

2.2 Which graph families?

2.3 What kind of sampling algorithm?.

2.4 Sampling graphs with given degrees: an overview

3 The configuration model

4 Sequential algorithms and graph processes

4.1 The regular case

4.2 The irregular case, and an almost-FPAUS

4.3 Other graph processes

5 Switchings-based algorithms

5.1 Improvements and extensions

6 Markov chain algorithms

6.1 Markov chain background

6.2 The Jerrum-Sinclair chain

6.3 The multicommodity flow method

6.4 The switch chain

6.6 Restricted graph classes

Recent advances on the graph isomorphism problem

3 The Weisfeiler-Leman Algorithm

3.1 The Color Refinement Algorithm

3.2 Higher Dimensions

3.3 The Power of WL and the WL Dimension

3.4 Characterisations of WL

4 The Group-Theoretic Graph Isomorphism Machinery

4.1 Basics

4.2 Luks's Algorithm

4.3 Babai's Algorithm

4.4 Faster Certificates for Groups with Restricted Composition Factors

4.5 From Strings to Hypergraphs

5 Quasi-Polynomial Parameterized Algorithms for Isomorphism Testing

5.1 Allowing Color Refinement to Split Small Classes

5.2 Graphs of Small Genus

5.3 Graphs of Small Tree Width

5.4 Graphs Excluding Small (Topological) Minors

6 Concluding Remarks

Extremal aspects of graph and hypergraph decomposition problems

1.1 Organisation of this survey

1.2 Notation

2 Approximate and fractional decompositions

2.1 From fractional to approximate decompositions

2.2 Fractional decomposition thresholds

2.3 Bandwidth theorem for approximate decompositions

3 Decomposition thresholds for fixed graphs F

3.1 Turning approximate decompositions into exact ones

3.2 Bipartite graphs

3.3 A discretisation result

3.4 Decompositions of partite graphs and Latin squares

4 F-decompositions of hypergraphs

4.1 Minimum degree versions.

5 Euler tours in hypergraphs

5.1 Euler tours: Proof sketch

5.2 Open problems on hypergraph decompositions and Euler tours

6 Oberwolfach problem

6.1 Open problems related to the Oberwolfach problem

7 Related decomposition problems

7.1 Weighted decompositions into triangles and edges

7.2 Packing and covering number

7.3 Decomposing highly connected graphs into trees

7.4 Tree packings

7.5 Sparse decompositions of dense graphs: Erd[H(o)]s meets Nash-Williams

Borel combinatorics of locally finite graphs

2 Notation

3 Some Background and Standard Results

3.1 Algebras and [sigma]-Algebras

3.2 Polish Spaces

3.3 The Borel [sigma]-Algebra of a Polish Space

3.4 Standard Borel Spaces

4 Borel Graphs: Definition and Some Examples

5 Basic Properties of Locally Finite Borel Graphs

5.1 Borel Colourings

5.2 Local Rules

5.3 Graphs with a Borel Transversal

5.4 Borel Assignments without Small Augmenting Sets

6 Negative Results via Borel Determinacy

7 Borel Equivalence Relations

8 Baire Measurable Combinatorics

9 [mu]-Measurable Combinatorics

10 Borel Colourings from LOCAL Algorithms

11 Borel Results that Use Measures or Baire Category

12 Graphs of Subexponential Growth

13 Applications to Equidecomposability

14 Concluding Remarks

Codes and designs in Johnson graphs with high symmetry

1.1 Codes in Johnson graphs

1.2 Designs in Johnson graphs: Delandtsheer designs

1.3 Imprimitive examples and a dichotomy

1.4 Primitive examples: towards a classi cation

2 Completely regular codes and a blow-up Construction

3 Sporadic SIT-codes and Delandtsheer 2-designs

4 Classical SIT-codes and Delandtsheer designs

5 Affine SIT-codes and Delandtsheer designs

6 Symplectic SIT-codes and Delandtsheer designs.

7 Related codes and designs

7.1 Transitivity properties on flags and antiflags of designs

7.2 SIT-codes and codes in binary Hamming graphs

Maximal subgroups of nite simple groups: classifications and applications

2 The maximal subgroups

2.1 Alternating groups

2.2 Classical groups

2.3 Exceptional groups

2.4 Sporadic groups

3 Generation and the generating graph

4 Base size

5 Graph isomorphism and related problems.

Notes:

Title from publisher's bibliographic system (viewed on 11 Jun 2021).

ISBN:

9781009041812

1009041819

9781009036214

1009036211

OCLC:

1256446696