Extended Abstracts EuroComb 2021 : European Conference on Combinatorics, Graph Theory and Applications

Preface to the Abstracts Volume of EuroComb21
Contents
Size of Local Finite Field Kakeya Sets
	1 Introduction
	2 Local Kakeya Sets
	References
Coloring of Graphs Avoiding Bicolored Paths of a Fixed Length
	1 Introduction
		1.1 Related Work
	2 General Bounds
	3 Coloring of Products of Paths and Cycles
	References
Nested Cycles with No Geometric Crossings
	1 Introduction
		1.1 Notation
		1.2 Sublinear Expander
		1.3 Auxiliary Definitions and Results
	2 Proof of Theorem 1
	References
Cut Vertices in Random Planar Graphs
	1 Introduction and Main Results
	2 Cut Vertices in the Erdős-Rényi Random Graph
	3 Cut Vertices in the Random Planar Graph
		3.1 Proof of Theorem 1
		3.2 Graph Decomposition and Conditional Random Graphs
		3.3 Cut Vertices in the Complex Part
		3.4 Cut Vertices in the Non-complex Part
		3.5 Proof of Theorem 2
	References
Extremal Density for Sparse Minors and Subdivisions
	1 Introduction
		1.1 Main Result
	2 Applications
	3 Outline of the Proof
		3.1 Embeddings in Dense Graphs
		3.2 Embeddings in Robust Expanders with Medium Density
		3.3 Embeddings in Sparse Robust Expanders
	References
Enumerating Descents on Quasi-Stirling Permutations and Plane Trees
	1 Introduction
		1.1 Stirling Permutations
		1.2 Quasi-Stirling Permutations
		1.3 A Bijection to Plane Trees
	2 Descents on Quasi-Stirling Permutations
	3 Properties of Quasi-Stirling Polynomials
	4 Generalization to k-Quasi-Stirling Permutations
	References
Hamiltonicity of Randomly Perturbed Graphs
	1 Introduction
	2 Hamiltonicity of Graphs Perturbed by a Random Geometric Graph
	3 Hamiltonicity of Graphs Perturbed by a Random Regular Graph
	References
The Largest Hole in Sparse Random Graphs
	1 Introduction
	2 Long Induced Paths
	3 Induced Forests with Small Components
	4 Concluding Remarks
	References
On 13-Crossing-Critical Graphs with Arbitrarily Large Degrees
	1 Introduction
	2 Analyzing Optimal Drawings of G13
	3 Counting Selected Crossings in a Drawing of G13
	4 Conclusion
	References
Local Convergence of Random Planar Graphs
	1 Summary of Proof
	References
Some Results on the Laplacian Spectra of Token Graphs
	1 Introduction
	2 The Laplacian Spectra of Token Graphs
	3 A More General Result
	4 A Graph, Its Complement, and Their Token Graphs
	References
On the Number of Compositions of Two Polycubes
	1 Introduction
	2 Two Dimensions
		2.1 Minimum Number of Compositions
		2.2 Maximum Number of Compositions
	3 Higher Dimensions
		3.1 Minimum Number of Compositions
		3.2 Maximum Number of Compositions in d 3 Dimensions
	4 Counting Compositions and Distribution Analysis
	References
Halin\'s End Degree Conjecture
	1 Introduction
		1.1 Halin\'s End Degree Conjecture
		1.2 Our Results
		1.3 Proof Sketch
		1.4 Open Problems
	References
Coloring Circle Arrangements: New 4-Chromatic Planar Graphs
	1 Introduction
	2 -Saturated Arrangements are 3-Colorable
	3 Constructing 4-Chromatic Arrangement Graphs
	4 Fractional Colorings
	5 Fractionally 3-Colorable 4-Edge-Critical Planar Graphs
	6 Discussion
	References
A Short Proof of Euler–Poincaré Formula
	1 Introduction
	2 New Combinatorial Proof
	3 Final Remarks
	References
Approximate MDS Property of Linear Codes
	1 Introduction
	2 Approximate MDS Property of Linear Codes
	References
A SAT Attack on Higher Dimensional Erdős–Szekeres Numbers
	1 Introduction
		1.1 Planar k-Holes
		1.2 Higher Dimensions
		1.3 Higher Dimensional Holes
		1.4 Precise Values
		1.5 Our Results
	2 Preliminaries
		2.1 Gons and Holes
	3 The SAT Framework
		3.1 Running Times and Resources
	4 Discussion
	References
Improved Bounds on the Cop Number of a Graph Drawn on a Surface
	1 Introduction
	2 Sketch of Proof
	References
Stability of Extremal Connected Hypergraphs Avoiding Berge-Paths
	1 Introduction
	2 A Sketch of the Proof
	References
On Tangencies Among Planar Curves with an Application to Coloring L-Shapes
	1 Introduction
	References
Semi-random Process Without Replacement
	1 Introduction
	2 Results
		2.1 General Bounds
		2.2 Minimum Degree
		2.3 Building Regular Graphs
		2.4 Trees
		2.5 Edge-Connectivity
	3 Urn Models
	4 Concluding Remarks and Open Problems
	References
The Intersection Spectrum of 3-Chromatic Intersecting Hypergraphs
	1 Introduction
	2 Preliminaries
	3 Proof Ideas
	References
On Ordered Ramsey Numbers of Tripartite 3-Uniform Hypergraphs
	1 Introduction
		1.1 Preliminaries
		1.2 Previous Results
	2 Our Results
	References
Hypergraphs with Minimum Positive Uniform Turán Density
	1 Introduction
	2 Main Result
	3 Hypergraphs with Uniform Turán Density Equal to 1/27
	4 Conclusion
	References
Rainbow Cliques in Randomly Perturbed Dense Graphs
	1 Introduction
		1.1 Our Results
	References
Universal Singular Exponents in Catalytic Variable Equations
	1 Introduction and Statement of Results
		1.1 The Linear Case
		1.2 The Non-linear Case
	2 Some Examples
	References
The Expected Number of Perfect Matchings in Cubic Planar Graphs
	1 Introduction
	2 Preliminaries
	3 The Ising Model on Rooted Triangulations and Perfect Matchings in Cubic Maps
	4 From the Ising Model to 3-Connected Cubic Graphs
	5 From 3-Connected Cubic Maps to Cubic Planar Graphs
	6 Proofs of the Main Results
	7 Concluding Remarks
	References
Gallai-Ramsey Number for Complete Graphs
	1 Introduction
	2 Preliminaries
	3 Three Colors
	4 Proof of Theorem 4 (and Theorem 3)
	References
On the Dichromatic Number of Surfaces
	1 Introduction
	2 The Dichromatic Number of N1, N2, N3, and S1
		2.1 The Dichromatic Number of S5 and N10
	References
Supersaturation, Counting, and Randomness in Forbidden Subposet Problems
	References
Path Decompositions of Tournaments
	1 Introduction
		1.1 Background
		1.2 New Results
	2 Proof Overview
		2.1 Robust Outexpanders
		2.2 Simplified Approach for Well Behaved Tournaments
		2.3 General Tournaments
	References
Sorting by Shuffling Methods and a Queue
	1 Introduction and Definitions
		1.1 Notation
		1.2 Motivation
	2 Shuffle Queues Equivalent to Deque and Stack
	3 Sorting by Cuts
	4 Permutations of Higher Cost
	5 A Conjecture on Two Pop Shuffle Queues
	References
Circular Coloring of Signed Bipartite Planar Graphs
	1 Introduction
		1.1 Circular Coloring of Signed Graphs
		1.2 Homomorphism of Signed Bipartite Graphs
	2 Circular Coloring of Signed Bipartite Planar Graphs
		2.1 Signed Bipartite Planar Graphs of Negative-Girth at Least 6
		2.2 Signed Bipartite Planar Graphs of Negative-Girth at Least 8
	References
Results on the Graceful Game and Range-Relaxed Graceful Game
	1 Introduction
	2 Basic Notation and Auxiliary Lemmas
	3 Graceful Game on Graph Products
	4 Results on the Range-Relaxed Graceful Game
	5 Concluding Remarks
	References
New Bounds on the Modularity of Johnson Graphs and Random Subgraphs of Johnson Graphs
	1 Introduction
	References
On Bipartite Sum Basic Equilibria
	1 Introduction
	2 Local Swap Deviations
	3 2-Edge-Connectivity in the Sum Basic Equilibria
	4 Conclusion
	References
Characterization and Enumeration of Preimages Under the Queuesort Algorithm
	1 Introduction
	2 A Recursive Characterization of Preimages
	3 Enumerative Results
	4 Conclusions and Further Work
	References
On Off-Diagonal Ordered Ramsey Numbers of Nested Matchings
	1 Introduction
	2 Our Results
		2.1 Nested Matchings Versus Complete Graphs
		2.2 Ramsey Goodness for Ordered Graphs
	References
Bounds on Half Graph Orders in Powers of Sparse Graphs
	1 Introduction
	2 Our Results
		2.1 Upper Bounds on Half Graphs in Planar Graphs
		2.2 Fully Polynomial Upper Bound on Neighborhood Complexity
		2.3 Upper Bounds on Half Graphs in Other Classes of Graphs
		2.4 Lower Bounds on Half Graphs
	References
The Homotopy Type of the Independence Complex of Graphs with No Induced Cycles of Length Divisible by 3
	1 Introduction
	2 Preliminaries
		2.1 Mayer-Vietoris Sequences
		2.2 Homotopy Type Theory
	3 Proof of Theorem 1
	References
The Maximum Number of Paths of Length Three in a Planar Graph
	1 Introduction
	References
Strongly Pfaffian Graphs
	1 Introduction
	2 A Structural Characterisation of Strongly Pfaffian Graphs
	References
Strong Modeling Limits of Graphs with Bounded Tree-Width
	1 Introduction
	2 Statement of the Main Result
	References
Loose Cores and Cycles in Random Hypergraphs
	1 Motivation and Main Results
	2 Sketch Proofs of Theorems 1 and 2
	3 Reduced Core: Proof of Theorem 3
	4 CoreConstruct: Proofs of Lemmas 1 and 2
	References
Building a Larger Class of Graphs for Efficient Reconfiguration of Vertex Colouring
	1 Introduction
	2 Recolouring OAT Graphs
	References
A Refinement of Cauchy-Schwarz Complexity, with Applications
	1 Introduction
	2 New Results
	3 Proof of the Main Result
	References
The Ising Antiferromagnet in the Replica Symmetric Phase
	1 Introduction
		1.1 Motivation
		1.2 Result
	2 Techniques
		2.1 Notation
		2.2 Outline
		2.3 Short Cycles
		2.4 The First and Second Moment
		2.5 Proof of Theorem1
	3 Discussion
	References
A Simple (2+)-Approximation Algorithm for Split Vertex Deletion
	References
On Graphs Without an Induced Path on 5 Vertices and Without an Induced Dart or Kite
	1 Introduction
	2 Sketch of the Proof
		2.1 (P5,Kite)-Free Graphs
		2.2 (P5,Dart)-Free Graphs
	References
Constant Congestion Brambles in Directed Graphs
	1 Introduction
	2 Sketch of the Proof of Theorem 1
	References
Component Behaviour of Random Bipartite Graphs
	1 Introduction
		1.1 Background and Motivation
		1.2 Main Results
	2 Enumerative Estimates
	3 A Finer Look at Component Structure of G(n,n,p)
	References
Maximising Line Subgraphs of Diameter at Most t
	1 Introduction
		1.1 Notation
	2 Results
	References
Unavoidable Hypergraphs
	1 Introduction
		1.1 Sunflowers
		1.2 General Proof Strategy
	2 Turán Numbers of 3-Uniform Sunflowers
	References
2-Distance (+1)-Coloring of Sparse Graphs Using the Potential Method
	References
Graphs Where Search Methods Are Indistinguishable
	1 Introduction
	2 Preliminaries
	3 Problem Description and Results
	4 Proof of Theorem 1
	5 Conclusion and Further Work
	References
Discrete Helly-Type Theorems for Pseudohalfplanes
	1 Introduction
		1.1 Pseudohalfplanes and Pseudohalfplane Hypergraphs
		1.2 Helly-Type Theorems for Halfplanes
		1.3 Helly-Type Theorems for Pseudohalfplanes
	References
Cycles of Many Lengths in Hamiltonian Graphs
	1 Introduction
	2 A Sketch and Main Ideas
	3 Concluding Remarks
	References
Maximal k-Wise -Divisible Set Families Are Atomic
	1 Introduction
	2 Dimensionality
	References
A Trivariate Dichromate Polynomial for Digraphs
	1 Introduction
		1.1 Notation and Previous Results
	2 Setting
		2.1 Cocircuits and Covectors
		2.2 The Face Lattice of
	3 A New Polynomial
	4 Outlook
	References
Schur\'s Theorem for Randomly Perturbed Sets
	1 Introduction
		1.1 Randomly Perturbed Sets of Integers
	2 Proof Sketch
	References
Unit Disk Visibility Graphs
	1 Introduction
	2 Preliminary Results
	3 Main Results
	4 Conclusion
	References
Waiter-Client Games on Randomly Perturbed Graphs
	1 Introduction
		1.1 Randomly Perturbed Graphs
		1.2 Waiter-Client Games
		1.3 Our Results
	2 Hamiltonicity Game
		2.1 Sketch of the Proof for b n0.49
		2.2 Sketch of the Proof for b ln(n)
	3 k-connectivity Game
	References
Vector Choosability in Bipartite Graphs
	1 Introduction
		1.1 Our Contribution
	2 Proof of Theorem 2
	3 Hardness Result
	References
Tight Bounds on the Expected Number of Holes in Random Point Sets
	1 Introduction
	2 Our Results
	References
The Game of Toucher and Isolator
	1 Introduction
	2 General Graphs
	3 Specific Graphs
	4 Concluding Remarks
	References
Hermitian Rank-Metric Codes
	1 Preliminaries on Hermitian Rank-Metric Codes
	2 The Association Scheme of Hermitian Matrices
	3 The Equivalence Issue
		3.1 A Partial Solution for Maximum Additive Hermitian d-codes
	4 Idealisers Are Not Distinguishers in Hn(q2)
	References
The Flat Wall Theorem for Bipartite Graphs with Perfect Matchings
	1 Introduction
	2 A Matching Theoretic Version of Flatness
	3 The Matching Flat Wall Theorem for Bipartite Graphs
	References
Big Ramsey Degrees and Forbidden Cycles
	1 Introduction
	2 Preliminaries
	3 Proof of Theorem 1
	References
The Ramsey Number for 4-Uniform Tight Cycles
	1 Introduction
		1.1 Sketch of the Proof of Theorem 1
	References
Chip-Firing on the Complete Split Graph: Motzkin Words and Tiered Parking Functions
	1 Introduction
	2 Recurrent States for Chip-Firing on a Graph
	3 Motzkin Words and Recurrent States for a Clique-Sink
		3.1 Prüfer Code Decomposition for Spanning Trees of Sm,n
	4 Tiered Parking Functions
	References
Long Shortest Cycle Covers in Cubic Graphs
	1 Introduction
	2 Results
	3 Concluding Remarks
	References
Powers of Hamilton Cycles of High Discrepancy Are Unavoidable
	1 Introduction
	2 Lower Bound Examples
	3 Outline of the Proofs
	References
Low Diameter Algebraic Graphs
	1 Introduction
	2 General Linear Groups
	3 Almost Subnormal Subgroups and Cyclic Subgroups
	4 Conclusion and Perspectives
	References
Complexity of 3+1/m-coloring Pt-free Graphs
	1 Introduction
	2 Proof
	References
Integer Covering Problems and Max-Norm Ramsey Theorems
	1 Integer Covering Problems
	2 Max-Norm Ramsey Theorems
	References
Unit Disks Hypergraphs Are Three-Colorable
	1 Introduction
	2 Hypergraph Colorings
	3 Proof of Theorem1
	4 Concluding Remarks
	References
Characterization of FS-Double Squares Ending with Two Distinct Squares
	1 Introduction
	2 Background
	3 FS-Double Squares Ending with Two Distinct Squares
	4 Consecutive Bordered FS Squares
	References
On Asymmetric Hypergraphs
	1 Introduction
	2 The Proof of Theorem2
	3 Proofs of Theorem4
	4 Concluding Remarks
	References
On Multicolour Ramsey Numbers and Subset-Colouring of Hypergraphs
	1 Introduction
		1.1 Previous Results
	2 A Stepping-Up Lemma
		2.1 Description of the Colouring
	3 Lower Bounds on Multicolour Hypergraph Ramsey Numbers
	4 Subset Colouring in Hypergraphs
	References
Max Cuts in Triangle-Free Graphs
	1 Introduction
	2 Proof Sketch of Theorem 2
		2.1 Setup for Flag Algebras
		2.2 High Density Range
		2.3 Concluding Remarks
	References
On the Cycle Rank Conjecture About Metric Dimension and Zero Forcing Number in Graphs
	1 Introduction
	2 Cactus Graphs
	3 General Bound
	References
Tight Bounds for Powers of Hamilton Cycles in Tournaments
	1 Introduction
	2 Proof Outline of Theorem 2
	3 Concluding Remarks
	References
On Sufficient Conditions for Hamiltonicity in Dense Graphs
	1 Introduction
	2 Results
		2.1 Ore-Type Conditions
		2.2 Pósa-Type Conditions
		2.3 Other Results
	3 Hamilton Frameworks
	References
On the Maximum Number of Weakly-Rainbow-Free Edge-Colorings
	1 Introduction
	2 Main Results
	3 Concluding Remarks
	References
Degree Conditions for Tight Hamilton Cycles
	1 Introduction
	2 Results
		2.1 Overview of Our Methods
	3 Open Problems
	References
An Approximate Structure Theorem for Small Sumsets
	1 Introduction and Main Result
	2 An Overview of the Proof
	3 Conclusions
	References
Classification of Local Problems on Paths from the Perspective of Descriptive Combinatorics
	1 Introduction
		1.1 Our Contribution
	References
On the Enumeration of Plane Bipolar Posets and Transversal Structures
	1 Introduction
	2 Oriented Planar Maps and Quadrant Tandem Walks
	3 Exact Counting Results
	4 Asymptotic Counting Results
	References
The Characterization of Graphs Whose Sandpile Group has Fixed Number of Generators
	1 Introduction
	2 Previous Sandpile Groups Characterizations
	3 Regular Graphs in K3
	References
Kissing Number in Non-Euclidean Spaces of Constant Sectional Curvature
	1 Preliminaries
	2 Kissing Number in Hyperbolic Space
		2.1 Upper and Lower Bounds
		2.2 Asymptotic Behaviour
	3 Kissing Number in Spherical Space
	4 Semidefinite Programming Bounds
	References
Decomposing Cubic Graphs with Cyclic Connectivity 5
	1 Introduciton
	2 Preliminaries
	3 Extensions Without Small Cycles
	4 Main Result
	5 Concluding Remarks
	References
Dirac-Type Conditions for Spanning Bounded-Degree Hypertrees
	1 Introduction
	2 Lower Bounds
	3 The Structure of Tight Hypertrees
	4 Sketch of the Proof of Theorem 1
		4.1 Step One: The Absorber
		4.2 Step Two: Embedding the Bulk of the Tree
		4.3 Step Three: Finalising the Embedding
	5 Open Questions
	References
Outer 1-String Graphs of Girth at Least Five are 3-Colorable
	1 Overview
	2 Definition and Notations
	3 Outline of Proof of Theorem 4
		3.1 Outline of Proof of Claim [cl:7]7
	References
The Rainbow Turán Number of Even Cycles
	1 Introduction
		1.1 Rainbow Turán Numbers
		1.2 Colour-Isomorphic Even Cycles in Proper Colourings
		1.3 Turán Number of Blow-Ups of Cycles
	2 Bounding Non-rainbow Homomorphic Cycles
	References
Trees with Few Leaves in Tournaments
	1 Introduction
	2 Median Orders
	3 Sketch Proof of Theorem 1
	4 Sketch Proof of Theorem 2
	References
Uncommon Systems of Equations
	1 Introduction
	2 Results
		2.1 A General Theorem and an Example
	3 Remarks and Open Problems
	References
Exchange Properties of Finite Set-Systems
	1 Introduction
	2 Proof of Theorem 1
	3 Proof of Theorem 2
	4 Proof of Theorem 3
	5 Concluding Remarks
	References
On a Question of Vera T. Sós About Size Forcing of Graphons
	1 Introduction
	2 Some Auxiliary Results
	3 Proof Outlines of Main Results
	References
On Deeply Critical Oriented Cliques
	1 Introduction and the Main Results
	2 Proof of Theorem3
	3 Proof of Theorem5
	4 Conclusions and Outlook
	References
Big Ramsey Degrees of the Generic Partial Order
	1 Introduction
	2 The Lower Bound
	References
The Square of a Hamilton Cycle in Randomly Perturbed Graphs
	1 Introduction
	2 Proof Overview
		2.1 Lower Bounds
		2.2 Stability
		2.3 Extremal Case
		2.4 Non-extremal Case
	References
On Extremal Problems Concerning the Traces of Sets
	1 Introduction
	2 Idea of the Proof
	3 Further Remarks and Open Problems
	References
The Chromatic Number of Signed Graphs with Bounded Maximum Average Degree
	1 Introduction
	2 State of the Art and Results
	3 Proof Techniques
	References
Maker–Breaker Games with Constraints
	1 Introduction
		1.1 Notation
	2 Results
	3 Concluding Remarks
	References
Parallelisms of PG(3,5) with an Automorphism Group of Order 25
	1 Introduction
	2 Construction
		2.1 The Automorphism Groups
		2.2 Spread Orbits Under the Action of G253 or G255
		2.3 Computer Search for Parallelisms
	3 Properties of the Constructed Parallelisms
		3.1 Parallelisms with G253
		3.2 Parallelisms with G255
	4 Concluding Remarks
	References
On Alternation, VC-dimension and k-fold Union of Sets
	1 Introduction
	2 VC-dimension Bounds for Functions with Alternation 1
	3 Bounds for VC-dimension in Terms of alt(f)
	4 Application to VC-dimension of k-fold Union
	References
Weak Components of the Directed Configuration Model
	1 Introduction
	2 Sketch of the Proof Of Theorem 2
		2.1 Multitype Branching Processes
		2.2 Exploration and Coupling of the Weak Components
		2.3 Expansion, Connection Probabilities and the Supercritical Case
		2.4 Subcritical Case
	References
Decomposing and Colouring Locally Out-Transitive Oriented Graphs
	1 Introduction
		1.1 Notation
		1.2 Context and Presentation of the Main Results
	2 Round and In-Round Oriented Graphs
	3 Decomposing and Colouring Locally Out-Transitive Oriented Graphs
		3.1 Statement of the Results and Outline of the Proofs
		3.2 A Short Application of Theorem 4 to the Caccetta-Häggkvist Conjecture
	References
Ramsey Expansions of 3-Hypertournaments
	1 Preliminaries
		1.1 Homogeneous 4-Constrained 3-Hypertournaments
	2 Positive Ramsey Results
	3 The H4-Free Case
	References
Path Decompositions of Random Directed Graphs
	1 Introduction
	2 Proof Sketch
	References
Large Multipartite Subgraphs in H-free Graphs
	1 Introduction
	2 Theorem 1 in Flag Algebras
	3 Tight Constructions for Conjecture 1
		3.1 Proof of Theorem 2 When r=2
	4 Concluding Remarks
	References
Kempe Changes in Bounded Treewidth Graphs
	1 Introduction
	2 Basic Notions
	3 Main Proof
	References
No Selection Lemma for Empty Triangles
	1 Introduction
	2 Horton Sets
	3 Squared Horton Sets
	4 53-Squared Horton Sets
	References
The Mod k Chromatic Index of Random Graphs
	1 Introduction
	2 Technical Lemmas
	3 Main Theorem
	4 A Lower Bound for maxk\'(G)
	5 Concluding Remarks and Future Work
	References
Constructions of Betweenness-Uniform Graphs from Trees
	References
On the Homomorphism Order of Oriented Paths and Trees
	1 Introduction
	2 Notation
	3 Proofs
	4 Final Remarks
	References
On Chromatic Number of (n,m)-graphs
	1 Introduction and Main Results
	2 Proof of Theorem 4
	3 Proof Sketch of Theorem 7
	4 Proof Sketch of Theorem 9
	References
On a Problem of Füredi and Griggs
	1 Introduction
	2 Hypergraph Representation
	References
Gallai\'s Path Decomposition for Planar Graphs
	1 Introduction
	2 Reducible Configurations
		2.1 Configurations (CI)
		2.2 Configurations (CII)
	References
Tuza\'s Conjecture for Threshold Graphs
	1 Introduction
		1.1 Preliminaries
	2 Threshold Graphs
	References
Covering Three-Tori with Cubes
	1 Introduction
	2 New Results
	3 Integer Lattices
	4 Proofs of Lemmas
	5 Proof of Theorem 2
	Reference
New Bounds on k-Geodetic Digraphs and Mixed Graphs
	1 The Degree/Geodecity Problem
	2 Results for Digraphs
	3 Bounds for Mixed Graphs
	References
Counting Ck-free Orientations of G(n,p)
	1 Introduction
	2 Outline of the Proof of Theorem 2
	3 Forbidding Directed Cycles
	References
Counting Circuit Double Covers
	1 The Framework
	2 The Number of CDCs as a Linear Representation
	3 Reducing Cycles – The General Method
	4 Reducing Cycles – Application to Planar Graphs
	References
Oriented Graphs with Lower Orientation Ramsey Thresholds
	1 Introduction
	2 Proof of Theorem 3
	3 Larger Trees (proof of Theorem 5)
	4 Inheritance by Sublinear Sets (Proof of Theorem 4)
	References
Random 2-Cell Embeddings of Multistars
	1 Introduction
	2 The Dipole
	3 Multi-stars
	4 General Graphs
	References
Cycle Saturation in Random Graphs
	References
On the Maximum Cut in Sparse Random Hypergraphs
	1 Introduction
		1.1 Definitions
		1.2 Known Results
		1.3 New Results
	2 Ideas of the Proofs
		2.1 Proof of Theorem 1
		2.2 Proof of the Upper Bound in Theorem 2
		2.3 Proof of the Lower Bound in Theorem 2
	References
Asymptotics for Connected Graphs and Irreducible Tournaments
	1 Introduction
	2 Notations, Strategy and Tools
	3 Proofs
	4 Further Results
	References
Interval Representation of Balanced Separators in Graphs Avoiding a Minor
	1 Interval Representation and Balanced Separators
	2 Thrifty Scattered Metrics
	3 Generalizations and Open Problems
	References
Lines in the Manhattan Plane
	1 Lines in Finite Metric Spaces
	2 Increasing and Decreasing Pairs, Blue and Red Arrows
	3 What Happens Around Isolated Points?
	4 The Lines Induced by Arrows are (Mostly) Distinct
	5 Counting Degrees
	6 L Metric
	References
A Rainbow Connectivity Threshold for Random Graph Families
	1 Introduction
	2 Proof of Theorem 3
		2.1 Spheres and Breadth-First Search for Rainbow Paths
		2.2 The Proof
	References
Robust Connectivity of Graphs on Surfaces
	1 Introduction
	2 Induced Subgraphs on Surfaces
	References
Author Index