The minimal degree of a permutation group G is the minimum number of points not fixed by non-identity elements of G. Lower bounds on the minimal degree have strong structural consequences on G. Babai ...conjectured that if a primitive coherent configuration with n vertices is not a Cameron scheme, then its automorphism group has minimal degree ≥cn for some constant c>0. In 2014, Babai proved the desired lower bound on the minimal degree of the automorphism groups of strongly regular graphs, thus confirming the conjecture for primitive coherent configurations of rank 3.
In this paper, we extend Babai's result to primitive coherent configurations of rank 4, confirming the conjecture in this special case. The proofs combine structural and spectral methods.
Recently (March 2022) Sean Eberhard published a class of counterexamples of rank 28 to Babai's conjecture and suggested to replace “Cameron schemes” in the conjecture with a more general class he calls “Cameron sandwiches”. Naturally, our result also confirms the rank 4 case of Eberhard's version of the conjecture.
•In this paper, we characterize Hamming and Johnson graphs by their spectral gap.•We confirm Babai's conjecture on the motion of distance-regular graphs of bounded diameter.•Our characterization of ...Hamming graphs involves only inequality constraints.
One of the central results in the representation theory of distance-regular graphs classifies distance-regular graphs with μ≥2 and second largest eigenvalue θ1=b1−1. In this paper we give a classification under the (weaker) approximate eigenvalue constraint θ1≥(1−ε)b1 for the class of geometric distance-regular graphs. As an application, we confirm Babai's conjecture on the minimal degree of the automorphism group of distance-regular graphs of bounded diameter. This conjecture asserts that if X is a primitive distance-regular graph with n vertices, and X is not a Hamming graph or a Johnson graph, then the automorphism group Aut(X) has minimal degree ≥cn for some constant c>0. It follows that Aut(X) satisfies strong structural constraints.
We prove that a distance-regular graph with a dominant distance is a spectral expander. The key ingredient of the proof is a new inequality on the intersection numbers. We use the spectral gap bound ...to study the structure of the automorphism group.
The minimal degree of a permutation group G is the minimum number of points not fixed by non-identity elements of G. Lower bounds on the minimal degree have strong structural consequences on G. In 2014 Babai proved that the automorphism group of a strongly regular graph with n vertices has minimal degree ≥cn, with known exceptions. Strongly regular graphs correspond to distance-regular graphs of diameter 2. Babai conjectured that Hamming and Johnson graphs are the only primitive distance-regular graphs of diameter d≥3 whose automorphism group has sublinear minimal degree. We confirm this conjecture for non-geometric primitive distance-regular graphs of bounded diameter. We also show if the primitivity assumption is removed, then only one additional family of exceptions arises, the crown graphs. We settle the geometric case in a companion paper.
The first example of a non-residually finite group in the classes of finitely presented small-cancelation groups, automatic groups, and CAT(O) groups was constructed by Wise as the fundamental group ...of a complete square complex (CSC for short) with twelve squares. At the same time, Janzen and Wise proved that CSCs with at most three, five or seven squares have residually finite fundamental group. The smallest open cases were CSCs with four squares and directed complete VM complexes with six squares. We prove that the CSC with four squares studied by Janzen and Wise has a non-residually finite fundamental group. For the class of complete directed VM complexes, we prove that there are exactly two complexes with six squares having a non-residually finite fundamental group. In particular, this positively answers to a question of Wise. Our approach relies on the connection between square complexes and automata discovered by Glasner and Mozes, where complete V M complexes with one vertex correspond to bireversible automata. We prove that the square complex associated to a bireversible automaton with two states or over the binary alphabet generating an infinite automaton group has a non-residually finite fundamental group. We describe automaton groups associated to CSCs with four squares and get two simple automaton representations of the free group F2.
The principal theme of this thesis is the interplay between symmetry and regularity in discrete structures. The most general class of structures we consider are coherent configurations, certain ...highly regular colorings of complete graphs. This class includes such diverse structures as the orbital configurations of permutation groups and association schemes originating from the design of experiments in statistics. Metric schemes, a subclass of association schemes, are derived from distance-regular graphs. Johnson, Hamming, and Grassman schemes are special classes of great importance among metric schemes. We study structural and spectral properties of coherent configurations. As a culmination of this analysis, we confirm Babai's conjecture on the minimal degree of the automorphism group for distance-regular graphs of bounded diameter and primitive coherent configurations of rank 4.The minimal degree of a permutation group G is the minimum number of points not fixed by non-identity elements of G. Lower bounds on the minimal degree have strong structural consequences on G. Babai conjectured that for some constant c > 0 the automorphism group of a primitive coherent configuration on n vertices has minimal degree ≥ cn with known exceptions. If confirmed, this conjecture gives a CFSG2-free proof of the Liebeck-Saxl classification of primitive groups with sublinear minimal degree. In this thesis, we confirm Babai's conjecture for distance-regular graphs (metric schemes) of bounded diameter and primitive coherent configurations of rank 4. Central to our approach is the study of spectral parameters of distance-regular graphs, such as spectral gap and smallest eigenvalue. The spectral gap of a graph is known to be tightly related to expansion properties of the graph. Hence, lower bounds on the spectral gap are widely applicable in various areas of mathematics and theoretical computer science. We prove that a distance-regular graph with a dominant distance is a spectral expander. The key ingredient of the proof is a new inequality on the intersection numbers. At the same time, graphs of which the smallest eigenvalue has a small absolute value are known to enjoy a rich geometric structure. We characterize Hamming graphs as distance-regular graphs of diameter d with smallest eigenvalue -d and3 μ ≤ 3, under mild additional assumptions. We also characterize Johnson and Hamming graphs as geometric distance-regular graphs satisfying certain inequality constraints on the spectral gap and the smallest eigenvalue. Finally, we study robustness properties of certain classes of coherent configurations. For instance, we show that the family of Johnson schemes is robust in the following sense. If a homogeneous coherent configuration X on n vertices or its fission contains a Johnson scheme J(s, d) as a subconfiguration on at least 5n/6 vertices and s > 250d4, then X is a Johnson scheme. This result strengthens a 1972 Kaluzhnin-Klin theorem that corresponds to the case where the subconfiguration itself has n vertices.Our result is also related to Babai's "Split-or-Johnson lemma'' and in particular to the philosophy in the theory of Graph Isomorphism testing that we can either find structure or find efficiently verifiable asymmetry.We show that similar robustness results hold for Hamming and Grassmann schemes.
The minimal degree of a permutation group \(G\) is the minimum number of points not fixed by non-identity elements of \(G\). Lower bounds on the minimal degree have strong structural consequences on ...\(G\). Babai conjectured that if a primitive coherent configuration with \(n\) vertices is not a Cameron scheme, then its automorphism group has minimal degree \(\geq cn\) for some constant \(c>0\). In 2014, Babai proved the desired lower bound on the minimal degree of the automorphism groups of strongly regular graphs, thus confirming the conjecture for primitive coherent configurations of rank 3. In this paper, we extend Babai's result to primitive coherent configurations of rank 4, confirming the conjecture in this special case. The proofs combine structural and spectral methods.
The rigidity of a matrix \(A\) for target rank \(r\) is the minimum number of entries of \(A\) that need to be changed in order to obtain a matrix of rank at most \(r\). At MFCS'77, Valiant ...introduced matrix rigidity as a tool to prove circuit lower bounds for linear functions and since then this notion received much attention and found applications in other areas of complexity theory. The problem of constructing an explicit family of matrices that are sufficiently rigid for Valiant's reduction (Valiant-rigid) still remains open. Moreover, since 2017 most of the long-studied candidates have been shown not to be Valiant-rigid. Some of those former candidates for rigidity are Kronecker products of small matrices. In a recent paper (STOC'21), Alman gave a general non-rigidity result for such matrices: he showed that if an \(n\times n\) matrix \(A\) (over any field) is a Kronecker product of \(d\times d\) matrices \(M_1,\dots, M_k\) (so \(n=d^k\)) \((d\ge 2)\) then changing only \(n^{1+\varepsilon}\) entries of \(A\) one can reduce its rank to \(\le n^{1-\gamma}\), where \(1/\gamma\) is roughly \(2^d/\varepsilon^2\). In this note we improve this result in two directions. First, we do not require the matrices \(M_i\) to have equal size. Second, we reduce \(1/\gamma\) from exponential in \(d\) to roughly \(d^{3/2}/\varepsilon^2\) (where \(d\) is the maximum size of the matrices \(M_i\)), and to nearly linear (roughly \(d/\varepsilon^2\)) for matrices \(M_i\) of sizes within a constant factor of each other. As an application of our results we significantly expand the class of Hadamard matrices that are known not to be Valiant-rigid; these now include the Kronecker products of Paley-Hadamard matrices and Hadamard matrices of bounded size.
One of the central results in the representation theory of distance-regular graphs classifies distance-regular graphs with \(\mu\geq 2\) and second largest eigenvalue \(\theta_1= b_1-1\). In this ...paper we give a classification under the (weaker) approximate eigenvalue constraint \(\theta_1\geq (1-\varepsilon)b_1\) for the class of geometric distance-regular graphs. As an application, we confirm Babai's conjecture on the minimal degree of the automorphism group of distance-regular graphs.
We prove that a distance-regular graph with a dominant distance is a spectral expander. The key ingredient of the proof is a new inequality on the intersection numbers. We use the spectral gap bound ...to study the structure of the automorphism group. The minimal degree of a permutation group \(G\) is the minimum number of points not fixed by non-identity elements of \(G\). Lower bounds on the minimal degree have strong structural consequences on \(G\). In 2014 Babai proved that the automorphism group of a strongly regular graph with \(n\) vertices has minimal degree \(\geq c n\), with known exceptions. Strongly regular graphs correspond to distance-regular graphs of diameter 2. Babai conjectured that Hamming and Johnson graphs are the only primitive distance-regular graphs of diameter \(d\geq 3\) whose automorphism group has sublinear minimal degree. We confirm this conjecture for non-geometric primitive distance-regular graphs of bounded diameter. We also show if the primitivity assumption is removed, then only one additional family of exceptions arises, the cocktail-party graphs. We settle the geometric case in a companion paper.
The rigidity of a matrix A for target rank r is the minimum number of entries of A that need to be changed in order to obtain a matrix of rank at most r (Valiant, 1977).
We study the dependence of ...rigidity on the target field. We consider especially two natural regimes: when one is allowed to make changes only from the field of definition of the matrix ("strict rigidity"), and when the changes are allowed to be in an arbitrary extension field ("absolute rigidity").
We demonstrate, apparently for the first time, a separation between these two concepts. We establish a gap of a factor of 3/2 − o(1) between strict and absolute rigidities.
The question seems especially timely because of recent results by Dvir and Liu (Theory of Computing, 2020) where important families of matrices, previously expected to be rigid, are shown not to be absolutely rigid, while their strict rigidity remains open. Our lower-bound method combines elementary arguments from algebraic geometry with "untouched minors" arguments.
Finally, we point out that more families of long-time rigidity candidates fall as a consequence of the results of Dvir and Liu. These include the incidence matrices of projective planes over finite fields, proposed by Valiant as candidates for rigidity over F2.
PDF
