A One-Day Meeting in Combinatorics will be held in the
Mathematical Institute, University of Oxford on Tuesday 21 May 2024.
The schedule can be found below.
10.30 am
Coffee
11.00 am
Carla Groenland (Delft)
Reconstructing graphs from distance queries
11.55 am
Piotr Micek (Jagiellonian University)
Planarity and dimension
12.50 pm
Lunch
2.15 pm
Shoham Letzter (UCL)
Ascending subgraph decompositions
3.10 pm
Gábor Tardos (Rényi Institute)
Forbidden acyclic patterns in 0-1 matrices
4.05 pm
Tea
4.30 pm
Nati Linial (Hebrew University of Jerusalem)
What we know and what we don't know about rate vs distance in error-correcting codes
Anyone interested is welcome to attend, and no registration is required. Some funds may be
available to contribute to the expenses of research students who wish to attend. For any inquiries, please contact Alex Scott (scott at maths.ox.ac.uk).
Support for this event by the London Mathematical Society and the British Combinatorial Committee is gratefully acknowledged.
Carla Groenland (Delft)
Reconstructing graphs from distance queries
Abstract:
Suppose you are given a vertex set V of size n together with an oracle which given u and v in V responds with the distance between u and v within a fixed hidden graph G on V. How many queries do you need to uniquely determine G? We show that n-vertex trees of maximum degree Δ can be reconstructed within Δ n logΔ(n)+O(Δ n) queries, and that up to a multiplicative constant this number of queries is also needed. For this, we improve both the previously best upper and lower bound and our techniques extend to various other settings (including randomised query complexity). I will talk about our key techniques and also survey some other techniques and open problems in reconstruction.
Based on joint work with Paul Bastide (https://arxiv.org/abs/2306.05979).
Piotr Micek (Jagiellonian University)
Planarity and dimension
Abstract:
The dimension of a partially ordered set P (poset for short) is the minimum positive integer d such that P is isomorphic to a subposet of
Rd with the natural product order. Dimension is arguably the most
widely studied measure of complexity of posets, and standard examples are the canonical structure forcing dimension to be large. In many ways, dimension for posets is analogous to chromatic number for graphs with standard examples in posets playing the role of cliques in graphs. However, planar graphs have chromatic number at most four, while posets with planar diagrams may have arbitrarily large dimension. The key feature of all known constructions is that large dimension is forced by a large standard example. The question of whether every poset of large dimension and a planar diagram contains a large standard example has been a critical challenge in posets theory since the early 1980s, with very little progress over the years. We answer the question in the affirmative, even for a much broader class of posets with planar cover graphs. Namely, we show that if P has a planar cover graph, then dim(P) <= 256 (se(P)+1)8 + 264, where dim(P) stands for the dimension of P and se(P) stands for the maximum order of a standard example in P.
Joint work with Heather S. Blake, Jędrzej Hodor, Michał T. Seweryn, and William T. Trotter.
Shoham Letzter (UCL)
Ascending subgraph decompositions
Abstract: Alavi, Boals, Chartrand, Erdős, and Oellerman conjectured (1987) that every graph on (m+1)m/2 edges can be edge-decomposed into subgraphs H_1, ..., H_m such that H_i has i edges and is isomorphic to a subgraph of H_{i+1}. We prove this conjecture for large m.
This is joint work with Kyriakos Katsamaktsis, Alexey Pokrovskiy, and Benny Sudakov.
Gábor Tardos (Rényi Institute)
Forbidden acyclic patterns in 0-1 matrices
Abstract:
A zero-one matrix M is said to contain another zero-one matrix A if we can delete some rows and columns of M and replace some 1-entries with 0-entries such that the resulting matrix is A. The extremal function of A, denoted ex(n, A), is the maximum number of 1-entries that an nxn zero-one matrix can have without containing A. The systematic study of this function for various patterns A goes back to the work of Füredi and Hajnal from 1992. The field has many connections to other areas such as classical Turán type extremal graph theory and Davenport-Schinzel theory and has many applications in mathematics and theoretical computer science. The problem has been particularly extensively studied for so-called acyclic matrices. Füredi and Hajnal conjectured an O(n log n) bound for them, while Pach and Tardos conjectured a weaker n polylog n bound. Pettie refuted the stronger conjecture with an acyclic pattern whose extremal function he showed to be Ω(n log n log log n).
In a recent joint work with Seth Pettie we found the extremal function ex(n, A_k) asymptotically for certain simple 2xk acyclic patterns to be Θ(n(log n/log log n)k-2) for k>3. This shows that the Pach-Tardos conjecture is tight if true. The conjecture itself is still wide open.
Nati Linial (Hebrew University of Jerusalem)
What we know and what we don't know about rate vs distance in
error-correcting codes
Abstract: TBA