Spring School 2024

Welcome to Spring School of Combinatorics 2024

You are not logged in! (LOGIN) or (SIGNUP) or (RESET PASSWORD)

List of papers and series for Spring School 2024




Series

STREAMING

A series of papers regarding streaming algorithms. For more details, ask Pavel Veselý.
Old and new approaches to counting distinct elements
Given a massive stream (sequence of items), we would like to process it in one pass using a small amount of memory (logarithmic in the stream length and universe size) and at the end, get an estimate of the number of distinct items seen. This is one of the core problems in the streaming area, with many applications in practice (say, counting distinct users that saw an advertisement). The talk should have two parts: (1) an overview of algorithms based on hash functions, which are studied since 80s, and (2) a new approach based on sampling, from paper "Distinct Elements in Streams: An Algorithm for the (Text) Book" (S. Chakraborty, N. V. Vinodchandran and K. S. Meel; ESA'22; https://arxiv.org/abs/2301.10191 ). The former approaches are well described in the lecture notes by A. Chakrabarti ( Units 2 and 3 in https://www.cs.dartmouth.edu/~ac/Teach/CS35-Spring20/Notes/lecnotes.pdf ). Please contact Pavel Vesely regarding this talk.
J. Nelson, H. Yu: Optimal bounds for approximate counting
We can maintain a counter incremented N times using O(log N) bits. However, what if we only have a smaller number of bits, that is O(log log N), but allow to return an approximation of N? This paper gives an optimal space upper and lower bounds for the approximate counting problem. It is suitable for a PhD or master student (some experience with randomized algorithms is an advantage). For more background, see reference [CY20] or ask Pavel Vesely.
J. B. T. Houen, R. Pagh, S. Walzer: Simple Set Sketching
Imagine you have a set that undergoes changes (insertions and deletions of elements). We would like to process the update sequence using a limited memory, say with M memory words. At some point the set may be huge, much larger than M. However, if the final set has at most cM elements (for a suitable constant c < 1), then we would like to recover the whole set with high probability. The talk should have two parts: (1) an overview of algorithms based on algebraic techniques or checksums, and (2) a new approach based on hashing and the XOR operation, from paper "Simple Set Sketching" (SOSA'23; https://arxiv.org/abs/2211.03683 ). The former approaches are well described in the lecture notes by A. Chakrabarti (Unit 9 in https://www.cs.dartmouth.edu/~ac/Teach/CS35-Spring20/Notes/lecnotes.pdf ). Please contact Pavel Vesely regarding this talk.
Rajesh Jayaram and John Kallaugher: An Optimal Algorithm for Triangle Counting in the Stream
This paper presents a streaming algorithm for counting the number of triangles (subgraphs isomorphic to K_3) in a large graph. The graph is given by a stream of edges, which the algorithm processes only once using a limited memory. The algorithm is based on sampling and achieves an optimal space bound to accurately estimate the number of triangles. For inquiries, you may contact Pavel Veselý.

Papers

Joseph Gubeladze: Normal polytopes and ellipsoids
This a paper which relates combinatorics, polytope theory and algebra. It is suitable for a PhD student or an experienced Master's student. If you need any help with this paper, contact Martin Tancer.
Sebastian M. Cioabă, Sean Dewar, Xiaofeng Gu: Spectral conditions for graph rigidity in the Euclidean plane
This paper relates rigidity theory of a graph with its spectral properties. Rigidity, roughly speaking, describes how flexible the graph is during a continuous motion. Spectral properties are properties of eigenvalues of the adjacency matrix of the graph and some related matrices. The paper contains a small bit of technical computations. It would be desirable to sketch only the main ideas in this part while possibly skipping some computations. The paper is suitable for a PhD student or an experienced Master's student. If you need any help with this paper, contact Martin Tancer.
Robert Kleinberg, Daniel Mitropolsky, Christos Papadimitriou: Total Functions in the Polynomial Hierarchy
We identify several genres of search problems beyond NP for which existence of solutions is guaranteed. One class that seems especially rich in such problems is PEPP (for "polynomial empty pigeonhole principle"), which includes problems related to existence theorems proved through the union bound, such as finding a bit string that is far from all codewords, finding an explicit rigid matrix, as well as a problem we call Complexity, capturing Complexity Theory's quest. When the union bound is generous, in that solutions constitute at least a polynomial fraction of the domain, we have a family of seemingly weaker classes -PEPP, which are inside FP^NP|poly. Higher in the hierarchy, we identify the constructive version of the Sauer-Shelah lemma and the appropriate generalization of PPP that contains it. The resulting total function hierarchy turns out to be more stable than the polynomial hierarchy: it is known that, under oracles, total functions within FNP may be easy, but total functions a level higher may still be harder than FP^NP. If you need any help with this paper, contact Pavel Hubáček.
Nir Bitansky and Idan Gerichter: On the Cryptographic Hardness of Local Search
We show new hardness results for the class of Polynomial Local Search problems (PLS): * Hardness of PLS based on a falsifiable assumption on bilinear groups introduced by Kalai, Paneth, and Yang (STOC 2019), and the Exponential Time Hypothesis for randomized algorithms. Previous standard model constructions relied on non-falsifiable and non-standard assumptions. * Hardness of PLS relative to random oracles. The construction is essentially different than previous constructions, and in particular is unconditionally secure. The construction also demonstrates the hardness of parallelizing local search. The core observation behind the results is that the unique proofs property of incrementally- verifiable computations previously used to demonstrate hardness in PLS can be traded with a simple incremental completeness property. If you need help with this paper, contact Pavel Hubáček.
Aysel Erey: On the average order of a dominating set of a forest
The title essential is self-explanatory: The aim of the paper is to provide a lower bound on the average order of a dominating set in a forest. There is a bit of computation in the paper; however, otherwise it is elementary. Therefore it should be accessible for Bc and Ms students. For any inquiries on this paper contact Martin Tancer.
Ce Jin, Virginia Vassilevska Williams, and Renfei Zhou: Listing 6-Cycles
The authors present a simple algorithm, based on color coding, that lists t (non-induced) 6-cycles in an n-node undirected graph in time O((n^2 + # of 6-cycles)*log(n)). For inquiries about this paper, feel free to contact Pavel Vesely.
Alexander Golovnev, Tom Gur, Igor Shinkar: Derandomization of Cell Sampling
This paper improves lower bounds on static data structures. The proof is using graph theory, in particular showing that every dense-enough hypergraph contains a small dense subgraph. For inquiries about this paper, feel free to contact Pavel Vesely.
Thomas Richthammer: Bunkbed conjecture for complete bipartite graphs and related classes of graphs
For a graph G=(V,E), its corresponding bunkbed graph G± consists of two copies G+=(V+,E+),G−=(V−,E−) of G and additional edges connecting any two vertices v+∈V+,v−∈V− that are the copies of a vertex v∈V. The bunkbed conjecture states that for independent bond percolation on G±, for all v,w∈V, it is more likely for v−,w− to be connected than for v−,w+ to be connected. While this seems very plausible, so far surprisingly little is known rigorously. Recently the conjecture has been proved for complete graphs. The paper extends this for complete bipartite graphs, complete graphs minus the edges of a complete subgraph, and symmetric complete k-partite graphs. For inquiries about this paper, feel free to contact Mykhaylo Tyomkyn.
Olha Silina: Covering the edges of a graph with perfect matchings
An r-graph is an r-regular graph with no odd cut of size less than r. A well-celebrated result due to Lovász says that for such graphs the linear system Ax=1 has a solution in Z/2, where A is the 0,1 edge to perfect matching incidence matrix. Note that we allow x to have negative entries. In this paper, the author presents an improved version of Lovász's result, proving that, in fact, there is a solution x with all entries being either integer or +1/2 and corresponding to a linearly independent set of perfect matchings. Moreover, the total number of +1/2's is at most 6k, where k is the number of Petersen bricks in the tight cut decomposition of the graph. For inquiries about this paper, feel free to contact Mykhaylo Tyomkyn.
Bill Jackson, Shin-ichi Tanigawa: Maximal matroids in weak order posets
Given a family of sets, can this family be a set of circuits of matroid? Is there the maximal matroid with these circuits? The aim of the paper is to provide partial answers for the question above. The paper is long thus it would be desired to select a small subset of the results of the paper to be presented. The paper is suitable for a PhD student or an enthusiastic Master student. If you need any help regarding this paper (including the choice of topics), please contact Martin Tancer. If desired, it could be also shared by more students. It has enough content for two talks.
Jialei Song Baogang Xu: Divisibility and coloring of some $P_5$-free graphs
The authors study graph classes where they forbid $P_5$ and some other graphs. For graphs in these classes, they for example show that it is possible to split such into a perfect part and a part with a smaller clique number. They also obtain results on the chromatic number of a slightly more restricted class. For inquiries on this paper, please contact Irena Penev.
Simón Piga, Marcelo Sales and Bjarne Schülke: The codegree Turán density of tight cycles minus one edge
This is a variant of a Turán density problem: If we have many edges in a hypergraph, then it contains a certain subhypergraph (in this case so called tight cycle minus an edge). Here the condition on many edges is given via codegree condition: every pair of vertices is contained in alpha n edges and the target is to optimize alpha. The paper is the most suitable for Bc students, or possibly Ms students. For inquiries, contact Martin Tancer
Robert E. Tarjan & Uri Zwick: Optimal resizable arrays
RESERVED
This paper considers maintaining a dynamic array such we can add or remove elements at the end of the array. Notable examples include Java’s ArrayList, Python’s PyListObject, C++ STL’s Vector all of which use a simple geometric technique to grow or shrink the allocated segment of memory for the array. Such a geometric growing/shrinking, however, may result in, say, half of the allocated memory being unused. The paper proposes a resizable array that uses only sublinear unused space and moreover, proves it optimal. The presentation doesn't need to cover the details and should focus primarily on their resizable array. For inquiries, you may contact Pavel Veselý.
Greg Bodwin: An Alternate Proof of Near-Optimal Light Spanners
RESERVED
A spanner of a (possibly dense) weighted graph G is a subgraph H of G that has close to linear number of edges but preserves distances up to a small constant distortion. Spanners find applications in efficient algorithms for large graphs, such as streaming algorithms. While it is relatively simple to prove that such spanners exist, this work focuses on constructing light spanners in a simple greedy way, where lightness is measured as the weight of H divided by the weight of MST of G. En route to the result, the paper gives two "Hiker puzzles". For inquiries about this paper, feel free to contact Pavel Vesely.
D Dorfman, H Kaplan, RE Tarjan, M Thorup, U Zwick: Minimum-cost paths for electric cars
RESERVED
This paper considers finding minimum-cost travel plans for a car with a battery of bounded capacity in a road network. The travel plan includes a path and a recharging schedule that specifies how much energy to charge at each charging station on the path. The cost of the plan is the total charging cost along the chosen path. The paper studies the all-pairs version of the problem and in particular, provides a O(n^3)-time algorithm for computing the cheapest travel plan between every two junctions of the network. For inquiries about this paper, feel free to contact Pavel Veselý.
Alexandr Grebennikov, João Pedro Marciano: C_10 has positive Turán density in the hypercube
RESERVED
The n-dimensional hypercube Q_n is a graph with vertex set {0,1}^n and there is an edge between two vertices if they differ in exactly one coordinate. For any graph H, define ex(Q_n,H) to be the maximum number of edges of a subgraph of Q_n without a copy of H. The authors prove that for any n∈N, ex(Q_n,C_{10})>0.024⋅e(Q_n). For inquiries about this paper, feel free to contact Mykhaylo Tyomkyn.
Yangyang Cheng, Peter Keevash: On the length of directed paths in digraphs
RESERVED
Thomassé conjectured the following strengthening of the well-known Caccetta-Haggkvist Conjecture: any digraph with minimum out-degree δ and girth g contains a directed path of length δ(g−1). Bai and Manoussakis gave counterexamples to Thomassé's conjecture for every even g≥4. In this note, the authors first generalize their counterexamples to show that Thomassé's conjecture is false for every g≥4. They also obtain the positive result that any digraph with minimum out-degree δ and girth g contains a directed path of 2δ(1−2g). For small g even better bounds are obtained, e.g. for g=3, any oriented graph with minimum out-degree δ contains a directed path of length 1.5δ. Furthermore, they show that each d-regular digraph with girth g contains a directed path of length Ω(dg/log d). These results give the first non-trivial bounds for these problems. For inquiries about this paper, feel free to contact Mykhaylo Tyomkyn.
Richard Montgomery, Rajko Nenadov, Tibor Szabó: Global rigidity of random graphs in R
RESERVED
Consider the Erdős-Rényi random graph process {G_m}m≥0 in which we start with an empty graph G_0 on the vertex set [n], and in each step form G_i from G_{i−1} by adding one new edge chosen uniformly at random. Resolving a conjecture by Benjamini and Tzalik, the authors give a simple proof that w.h.p. as soon as Gm has minimum degree 2 it is globally rigid in the following sense: For any function d:E(G_m)→R, there exists at most one injective function f:[n]→R (up to isometry) such that d(ij)=|f(i)−f(j)| for every ij∈E(Gm). They also resolve a related question of Girão, Illingworth, Michel, Powierski, and Scott in the sparse regime for the random graph and give some open problems. For inquiries about this paper, feel free to contact Mykhaylo Tyomkyn.
Vjekoslav Kovač: Monochromatic boxes of unit volume
RESERVED
Erdős and Graham asked whether, for any coloring of the Euclidean plane R2 in finitely many colors, some color class contains the vertices of a rectangle of every given area. The author gives the negative answer to this question and its higher-dimensional generalization: there exists a finite coloring of the Euclidean space Rn, n≥2, such that no color class contains the 2n vertices of a rectangular box of volume 1. The present note is a very preliminary version of a longer treatise on similar problems. For inquiries about this paper, feel free to contact Mykhaylo Tyomkyn.
Torsten Mütze: A book proof of the middle levels theorem
RESERVED
The paper gives a short constructive proof for the existence of a Hamilton cycle in the subgraph of the (2n+1)-dimensional hypercube induced by all vertices with exactly n or n+1 many 1s. For inquiries about this paper, feel free to contact Mykhaylo Tyomkyn.
Tung Nguyen, Alex Scott, Paul Seymour: A note on the Gyárfás-Sumner conjecture
RESERVED
The Gyárfás-Sumner conjecture says that for every tree T and every integer t≥1, if G is a graph with no clique of size t and with sufficiently large chromatic number, then G contains an induced subgraph isomorphic to T. This remains open, but the authors prove that under the same hypotheses, G contains a subgraph H isomorphic to T that is ``path-induced''; that is, for some distinguished vertex~r, every path of H with one end r is an induced path of G.
Matt DeVos, Jessica McDonald, Kathryn Nurse: Another proof of Seymour's 6-flow theorem
RESERVED
In 1981 Seymour proved his famous 6-flow theorem asserting that every 2-edge-connected graph has a nowhere-zero flow in the group Z_2×Z_3 (in fact, he offers two proofs of this result). In this note the authors give a new short proof of a generalization of this theorem where Z_2×Z_3-valued functions are found subject to certain boundary constraints. For inquiries about this paper, feel free to contact Mykhaylo Tyomkyn.
Johannes Pardey, Dieter Rautenbach: Vertex degrees close to the average degree
RESERVED
Given a graph, the aim of the paper is to provide some intervals which have to contain a vertex of a given degree. A trivial example: a graph with n vertices has to contain a vertex of degree between the average degree and n-1. In case of inquiries on the contents, contact Martin Tancer
Tereza Klimošová and Maya Stein: Antipaths in oriented graphs
RESERVED
The paper provides a sufficient condition for a directed graph to contain a so call antipath (antidirected path) of length k. The paper is suitable for Bc or Ms students. For inquiries, contact Irena Penev.
Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl: Detecting an Odd Hole
RESERVED
The authors investigate the task of algorithmically finding an induced cycle of odd length strictly greater than three in the graph and they give a polynomial algorithm to do so. For inquiries on this paper, please contact Irena Penev.