Source author record

Jonathan Tidor

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Computational Complexity Discrete Mathematics Data Structures and Algorithms math.AG math.CA math.MG

Catalog footprint

Research overview

11works

7topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2023arXiv

Ramsey and Turán numbers of sparse hypergraphs

Degeneracy plays an important role in understanding Turán- and Ramsey-type properties of graphs. Unfortunately, the usual hypergraphical generalization of degeneracy fails to capture these properties. We define the skeletal degeneracy of a $k$ -uniform hypergraph as the degeneracy of its $1$ -skeleton (i.e., the graph formed by replacing every $k$ -edge by a $k$ -clique). We prove that skeletal degeneracy controls hypergraph Turán and Ramsey numbers in a similar manner to (graphical) degeneracy. Specifically, we show that $k$ -uniform hypergraphs with bounded skeletal degeneracy have linear Ramsey number. This is the hypergraph analogue of the Burr-Erdős conjecture (proved by Lee). In addition, we give upper and lower bounds of the same shape for the Turán number of a $k$ -uniform $k$ -partite hypergraph in terms of its skeletal degeneracy. The proofs of both results use the technique of dependent random choice. In addition, the proof of our Ramsey result uses the `random greedy process' introduced by Lee in his resolution of the Burr-Erdős conjecture.

preprint2022arXiv

Equiangular lines with a fixed angle

Solving a longstanding problem on equiangular lines, we determine, for each given fixed angle and in all sufficiently large dimensions, the maximum number of lines pairwise separated by the given angle. Fix $0 < α< 1$ . Let $N_α(d)$ denote the maximum number of lines through the origin in $\mathbb{R}^d$ with pairwise common angle $\arccos α$ . Let $k$ denote the minimum number (if it exists) of vertices in a graph whose adjacency matrix has spectral radius exactly $(1-α)/(2α)$ . If $k < \infty$ , then $N_α(d) = \lfloor k(d-1)/(k-1) \rfloor$ for all sufficiently large $d$ , and otherwise $N_α(d) = d + o(d)$ . In particular, $N_{1/(2k-1)}(d) = \lfloor k(d-1)/(k-1) \rfloor$ for every integer $k\ge 2$ and all sufficiently large $d$ . A key ingredient is a new result in spectral graph theory: the adjacency matrix of a connected bounded degree graph has sublinear second eigenvalue multiplicity.

preprint2022arXiv

Joints of varieties

We generalize the Guth--Katz joints theorem from lines to varieties. A special case says that $N$ planes (2-flats) in 6 dimensions (over any field) have $O(N^{3/2})$ joints, where a joint is a point contained in a triple of these planes not all lying in some hyperplane. More generally, we prove the same bound when the set of $N$ planes is replaced by a set of 2-dimensional algebraic varieties of total degree $N$ , and a joint is a point that is regular for three varieties whose tangent planes at that point are not all contained in some hyperplane. Our most general result gives upper bounds, tight up to constant factors, for joints with multiplicities for several sets of varieties of arbitrary dimensions (known as Carbery's conjecture). Our main innovation is a new way to extend the polynomial method to higher dimensional objects, relating the degree of a polynomial and its orders of vanishing on a given set of points on a variety.

preprint2022arXiv

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

We study the basic problem of assigning memoryless workers to tasks with dynamically changing demands. Given a set of $w$ workers and a multiset $T \subseteq[t]$ of $|T|=w$ tasks, a memoryless worker-task assignment function is any function $ϕ$ that assigns the workers $[w]$ to the tasks $T$ based only on the current value of $T$ . The assignment function $ϕ$ is said to have switching cost at most $k$ if, for every task multiset $T$ , changing the contents of $T$ by one task changes $ϕ(T)$ by at most $k$ worker assignments. The goal of memoryless worker task assignment is to construct an assignment function with the smallest possible switching cost. In past work, the problem of determining the optimal switching cost has been posed as an open question. There are no known sub-linear upper bounds, and after considerable effort, the best known lower bound remains 4 (ICALP 2020). We show that it is possible to achieve polylogarithmic switching cost. We give a construction via the probabilistic method that achieves switching cost $O(\log w \log (wt))$ and an explicit construction that achieves switching cost $\operatorname{polylog} (wt)$ . We also prove a super-constant lower bound on switching cost: we show that for any value of $w$ , there exists a value of $t$ for which the optimal switching cost is $w$ . Thus it is not possible to achieve a switching cost that is sublinear strictly as a function of $w$ . Finally, we present an application of the worker-task assignment problem to a metric embeddings problem. In particular, we use our results to give the first low-distortion embedding from sparse binary vectors into low-dimensional Hamming space.

preprint2021arXiv

Popular differences for matrix patterns

The following combinatorial conjecture arises naturally from recent ergodic-theoretic work of Ackelsberg, Bergelson, and Best. Let $M_1$ , $M_2$ be $k\times k$ integer matrices, $G$ be a finite abelian group of order $N$ , and $A\subseteq G^k$ with $|A|\geαN^k$ . If $M_1$ , $M_2$ , $M_1-M_2$ , and $M_1+M_2$ are automorphisms of $G^k$ , is it true that there exists a popular difference $d \in G^k\setminus\{0\}$ such that $\#\{x \in G^k: x, x+M_1d, x+M_2d, x+(M_1+M_2)d \in A\} \ge (α^4-o(1))N^k.$ We show that this conjecture is false in general, but holds for $G = \mathbb{F}_p^n$ with $p$ an odd prime given the additional spectral condition that no pair of eigenvalues of $M_1M_2^{-1}$ (over $\overline{\mathbb{F}}_p$ ) are negatives of each other. In particular, the "rotated squares" pattern does not satisfy this eigenvalue condition, and we give a construction of a set of positive density in $(\mathbb{F}_5^n)^2$ for which that pattern has no nonzero popular difference. This is in surprising contrast to three-point patterns, which we handle over all compact abelian groups and which do not require an additional spectral condition.

preprint2020arXiv

Hypergraph expanders of all uniformities from Cayley graphs

Hypergraph expanders are hypergraphs with surprising, non-intuitive expansion properties. In a recent paper, the first author gave a simple construction, which can be randomized, of $3$ -uniform hypergraph expanders with polylogarithmic degree. We generalize this construction, giving a simple construction of $r$ -uniform hypergraph expanders for all $r \geq 3$ .

preprint2020arXiv

Testing linear-invariant properties

Fix a prime $p$ and a positive integer $R$ . We study the property testing of functions $\mathbb F_p^n\to[R]$ . We say that a property is testable if there exists an oblivious tester for this property with one-sided error and constant query complexity. Furthermore, a property is proximity oblivious-testable (PO-testable) if the test is also independent of the proximity parameter $ε$ . It is known that a number of natural properties such as linearity and being a low degree polynomial are PO-testable. These properties are examples of linear-invariant properties, meaning that they are preserved under linear automorphisms of the domain. Following work of Kaufman and Sudan, the study of linear-invariant properties has been an important problem in arithmetic property testing. A central conjecture in this field, proposed by Bhattacharyya, Grigorescu, and Shapira, is that a linear-invariant property is testable if and only if it is semi subspace-hereditary. We prove two results, the first resolves this conjecture and the second classifies PO-testable properties. (1) A linear-invariant property is testable if and only if it is semi subspace-hereditary. (2) A linear-invariant property is PO-testable if and only if it is locally characterized. Our innovations are two-fold. We give a more powerful version of the compactness argument first introduced by Alon and Shapira. This relies on a new strong arithmetic regularity lemma in which one mixes different levels of Gowers uniformity. This allows us to extend the work of Bhattacharyya, Fischer, Hatami, Hatami, and Lovett by removing the bounded complexity restriction in their work. Our second innovation is a novel recoloring technique called patching. This Ramsey-theoretic technique is critical for working in the linear-invariant setting and allows us to remove the translation-invariant restriction present in previous work.

preprint2019arXiv

Induced arithmetic removal: complexity 1 patterns over finite fields

We prove an arithmetic analog of the induced graph removal lemma for complexity 1 patterns over finite fields. Informally speaking, we show that given a fixed collection of $r$ -colored complexity 1 arithmetic patterns over $\mathbb F_q$ , every coloring $ϕ\colon \mathbb F_q^n \setminus\{0\} \to [r]$ with $o(1)$ density of every such pattern can be recolored on an $o(1)$ -fraction of the space so that no such pattern remains.

preprint2016arXiv

1-color-avoiding paths, special tournaments, and incidence geometry

We discuss two approaches to a recent question of Loh: must a 3-colored transitive tournament on $N$ vertices have a 1-color-\emph{avoiding} path of vertex-length at least $N^{2/3}$ ? This question generalizes the Erdős--Szekeres theorem on monotone subsequences. First, we define three canonical transformations on these tournaments called Color, Record, and Dual. We use these to establish a reduction to special tournaments with natural geometric and combinatorial properties. In many cases (including all known tight examples), these tournaments have recursive Gallai decompositions. Not all relevant tournaments have Gallai decompositions, but those that do satisfy the desired $N^{2/3}$ bound by recent work of Wagner, roughly analogous to earlier work of Fox, Grinshpun, and Pach on a similar \emph{undirected} problem. Second, we consider the related geometric problem of bounding \emph{slice-increasing} sets $S\subseteq [n]^3$ , which---under an additional ordering hypothesis on $S$ ---was shown by Loh to be equivalent to the original question. In particular, we establish a rigorous connection from a problem of Szabó and Tardos, raise a stronger $L^2$ -question on slice-counts, and mention a surprising overlap with the joints problem.

preprint2014arXiv

Bounding sequence extremal functions with formations

An $(r, s)$ -formation is a concatenation of $s$ permutations of $r$ letters. If $u$ is a sequence with $r$ distinct letters, then let $\mathit{Ex}(u, n)$ be the maximum length of any $r$ -sparse sequence with $n$ distinct letters which has no subsequence isomorphic to $u$ . For every sequence $u$ define $\mathit{fw}(u)$ , the formation width of $u$ , to be the minimum $s$ for which there exists $r$ such that there is a subsequence isomorphic to $u$ in every $(r, s)$ -formation. We use $\mathit{fw}(u)$ to prove upper bounds on $\mathit{Ex}(u, n)$ for sequences $u$ such that $u$ contains an alternation with the same formation width as $u$ . We generalize Nivasch's bounds on $\mathit{Ex}((ab)^{t}, n)$ by showing that $\mathit{fw}((12 \ldots l)^{t})=2t-1$ and $\mathit{Ex}((12\ldots l)^{t}, n) =n2^{\frac{1}{(t-2)!}α(n)^{t-2}\pm O(α(n)^{t-3})}$ for every $l \geq 2$ and $t\geq 3$ , such that $α(n)$ denotes the inverse Ackermann function. Upper bounds on $\mathit{Ex}((12 \ldots l)^{t} , n)$ have been used in other papers to bound the maximum number of edges in $k$ -quasiplanar graphs on $n$ vertices with no pair of edges intersecting in more than $O(1)$ points. If $u$ is any sequence of the form $a v a v' a$ such that $a$ is a letter, $v$ is a nonempty sequence excluding $a$ with no repeated letters and $v'$ is obtained from $v$ by only moving the first letter of $v$ to another place in $v$ , then we show that $\mathit{fw}(u)=4$ and $\mathit{Ex}(u, n) =Θ(nα(n))$ . Furthermore we prove that $\mathit{fw}(abc(acb)^{t})=2t+1$ and $\mathit{Ex}(abc(acb)^{t}, n) = n2^{\frac{1}{(t-1)!}α(n)^{t-1}\pm O(α(n)^{t-2})}$ for every $t\geq 2$ .

preprint2013arXiv

Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs

We examine semi-bar visibility graphs in the plane and on a cylinder in which sightlines can pass through k objects. We show every semi-bar k-visibility graph has a (k+2)-quasiplanar representation in the plane with vertices drawn as points in convex position and edges drawn as segments. We also show that the graphs having cylindrical semi-bar k-visibility representations with semi-bars of different lengths are the same as the (2k+2)-degenerate graphs having edge-maximal (k+2)-quasiplanar representations in the plane with vertices drawn as points in convex position and edges drawn as segments.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Jonathan Tidor

Research overview

Is this your work?

11 publications

Ramsey and Turán numbers of sparse hypergraphs

Equiangular lines with a fixed angle

Joints of varieties

Memoryless Worker-Task Assignment with Polylogarithmic Switching Cost

Popular differences for matrix patterns

Hypergraph expanders of all uniformities from Cayley graphs

Testing linear-invariant properties

Induced arithmetic removal: complexity 1 patterns over finite fields

1-color-avoiding paths, special tournaments, and incidence geometry

Bounding sequence extremal functions with formations

Convex geometric (k+2)-quasiplanar representations of semi-bar k-visibility graphs

See the researcher in context

Building this map preview