One-Day Meeting in Combinatorics
Mathematical Institute
University of Oxford

Tuesday 21 May 2024

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.

Schedule

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)
                                     Rank-Ramsey graphs


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.


Abstracts

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) Rank-Ramsey graphs

Abstract: A graph is called Rank-Ramsey if (i) Its clique number is small, and (ii) The adjacency matrix of its complement has small rank. We initiate a systematic study of such graphs. Our main motivation is that their constructions, as well as proofs of their non-existence, are intimately related to the famous log-rank conjecture from the field of communication complexity. These investigations also open interesting new avenues in Ramsey theory.
We construct two families of Rank-Ramsey graphs exhibiting polynomial separation between order and complement rank. Graphs in the first family have bounded clique number (as low as 41). These are subgraphs of certain strong products, whose building blocks are derived from triangle-free strongly-regular graphs. Graphs in the second family are obtained by applying Boolean functions to Erdős-Rényi graphs. Their clique number is logarithmic, but their complement rank is far smaller than in the first family, about O(n2/3). A key component of this construction is our matrix-theoretic view of lifts.
We also consider lower bounds on the Rank-Ramsey numbers, and determine them in the range where the complement rank is 5 or less. We consider connections between said numbers and other graph parameters, and find that the two best known explicit constructions of triangle-free Ramsey graphs turn out to be far from Rank-Ramsey.
Joint work with Gal Beniamini and Adi Shraibman