More Like this

1. A Spanner for the Day After

   https://doi.org/10.1007/s00454-020-00228-6  

   Buchin, Kevin; Har-Peled, Sariel; Oláh, Dániel (December 2020, Discrete & Computational Geometry)

   null (Ed.)

   Abstract We show how to construct a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner over a set $${P}$$ P of n points in $${\mathbb {R}}^d$$ R d that is resilient to a catastrophic failure of nodes. Specifically, for prescribed parameters $${\vartheta },\varepsilon \in (0,1)$$ ϑ , ε ∈ ( 0 , 1 ) , the computed spanner $${G}$$ G has $$\begin{aligned} {{\mathcal {O}}}\bigl (\varepsilon ^{-O(d)} {\vartheta }^{-6} n(\log \log n)^6 \log n \bigr ) \end{aligned}$$ O ( ε - O ( d ) ϑ - 6 n ( log log n ) 6 log n ) edges. Furthermore, for any k , and any deleted set $${{B}}\subseteq {P}$$ B ⊆ P of k points, the residual graph $${G}\setminus {{B}}$$ G \ B is a $$(1+\varepsilon )$$ ( 1 + ε ) -spanner for all the points of $${P}$$ P except for $$(1+{\vartheta })k$$ ( 1 + ϑ ) k of them. No previous constructions, beyond the trivial clique with $${{\mathcal {O}}}(n^2)$$ O ( n 2 ) edges, were known with this resilience property (i.e., only a tiny additional fraction of vertices, $$\vartheta |B|$$ ϑ | B | , lose their distance preserving connectivity). Our construction works by first solving the exact problem in one dimension, and then showing a surprisingly simple and elegant construction in higher dimensions, that uses the one-dimensional construction in a black-box fashion. 

   more » « less
2. L-Systems and the Lovász Number

   https://doi.org/10.1007/s00493-025-00136-4  

   Linz, William (April 2025, Combinatorica)

   Abstract Given integers$$n> k > 0$$ $n>k>0$, and a set of integers$$L \subset [0, k-1]$$ $L\subset [0,k-1]$, anL-systemis a family of sets$$\mathcal {F}\subset \left( {\begin{array}{c}[n]\\ k\end{array}}\right) $$ $F\subset \left(\begin{array}{c}\left[n\right]\\ k\end{array}\right)$such that$$|F \cap F'| \in L$$ $|F\cap F^{\prime }|\in L$for distinct$$F, F'\in \mathcal {F}$$ $F,F^{\prime }\in F$.L-systems correspond to independent sets in a certain generalized Johnson graphG(n, k, L), so that the maximum size of anL-system is equivalent to finding the independence number of the graphG(n, k, L). TheLovász number$$\vartheta (G)$$ $\vartheta \left(G\right)$is a semidefinite programming approximation of the independence number$$\alpha $$ $\alpha$of a graphG. In this paper, we determine the leading order term of$$\vartheta (G(n, k, L))$$ $\vartheta \left(G\right(n,k,L\left)\right)$of any generalized Johnson graph withkandLfixed and$$n\rightarrow \infty $$ $n\to \infty$. As an application of this theorem, we give an explicit construction of a graphGonnvertices with a large gap between the Lovász number and the Shannon capacityc(G). Specifically, we prove that for any$$\epsilon > 0$$ $ϵ>0$, for infinitely manynthere is a generalized Johnson graphGonnvertices which has ratio$$\vartheta (G)/c(G) = \Omega (n^{1-\epsilon })$$ $\vartheta \left(G\right)/c\left(G\right)=\Omega \left(n^{1-ϵ}\right)$, which improves on all known constructions. The graphGa fortiorialso has ratio$$\vartheta (G)/\alpha (G) = \Omega (n^{1-\epsilon })$$ $\vartheta \left(G\right)/\alpha \left(G\right)=\Omega \left(n^{1-ϵ}\right)$, which greatly improves on the best known explicit construction. 

   more » « less
3. On the rank of a random binary matrix

   https://doi.org/10.1137/1.9781611975482.58  

   Cooper, Colin; Frieze, Alan; Pegden, Wesley (January 2019, Proceedings of the annual ACM-SIAM Symposium on Discrete Algorithms)

   We study the rank of a random n × m matrix An, m; k with entries from GF(2), and exactly k unit entries in each column, the other entries being zero. The columns are chosen independently and uniformly at random from the set of all (nk) such columns. We obtain an asymptotically correct estimate for the rank as a function of the number of columns m in terms of c, n, k, and where m = cn/k. The matrix An, m; k forms the vertex-edge incidence matrix of a k-uniform random hypergraph H. The rank of An, m; k can be expressed as follows. Let |C2| be the number of vertices of the 2-core of H, and | E (C2)| the number of edges. Let m* be the value of m for which |C2| = |E(C2)|. Then w.h.p. for m < m* the rank of An, m; k is asymptotic to m, and for m ≥ m* the rank is asymptotic to m – |E(C2)| + |C2|. In addition, assign i.i.d. U[0, 1] weights Xi, i ∊ 1, 2, … m to the columns, and define the weight of a set of columns S as X(S) = ∑j∊S Xj. Define a basis as a set of n – 1 (k even) linearly independent columns. We obtain an asymptotically correct estimate for the minimum weight basis. This generalises the well-known result of Frieze [On the value of a random minimum spanning tree problem, Discrete Applied Mathematics, (1985)] that, for k = 2, the expected length of a minimum weight spanning tree tends to ζ(3) ∼ 1.202. 

   more » « less
4. KSB stability is automatic in codimension $$\boldsymbol{\geq 3}$$

   https://doi.org/10.1112/mod.2024.8  

   Kollár, János; Kovács, Sándor J (January 2024, Moduli)

   Abstract KSB stability holds at codimension$$1$$points trivially, and it is quite well understood at codimension$$2$$points because we have a complete classification of$$2$$-dimensional slc singularities. We show that it is automatic in codimension$$3$$. 

   more » « less
5. Smooth rigidity for codimension one Anosov flows

   https://doi.org/10.1090/proc/16177  

   Gogolev, Andrey; Hertz, Federico (July 2023, Proceedings of the American Mathematical Society)

   We introduce the matching functions technique in the setting of Anosov flows. Then we observe that simple periodic cycle functionals (also known as temporal distances) provide a source of matching functions for conjugate Anosov flows. For conservative codimension one Anosov flows ${\mathrm{\phi <\#comment/>}}^t:<\#comment/>M\to <\#comment/>M$, $\dim <\#comment/>M\ge <\#comment/>4$, these simple periodic cycle functionals are $C^1$regular and, hence, can be used to improve regularity of the conjugacy. Specifically, we prove that a continuous conjugacy must, in fact, be a $C^1$diffeomorphism for an open and dense set of codimension one conservative Anosov flows. 

   more » « less