Source author record

Timothy F. N. Chan

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

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics math.OC

Catalog footprint

Research overview

3works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Characterization of quasirandom permutations by a pattern sum

It is known that a sequence Pi_i of permutations is quasirandom if and only if the pattern density of every 4-point permutation in Pi_i converges to 1/24. We show that there is a set S of 4-point permutations such that the sum of the pattern densities of the permutations from S in the permutations Pi_i converges to |S|/24 if and only if the sequence is quasirandom. Moreover, we are able to completely characterize the sets S with this property. In particular, there are exactly ten such sets, the smallest of which has cardinality eight.

preprint2022arXiv

Inducibility and universality for trees

We answer three questions posed by Bubeck and Linial on the limit densities of subtrees in trees. We prove there exist positive $\varepsilon_1$ and $\varepsilon_2$ such that every tree that is neither a path nor a star has inducibility at most $1-\varepsilon_1$ , where the inducibility of a tree $T$ is defined as the maximum limit density of $T$ , and that there are infinitely many trees with inducibility at least $\varepsilon_2$ . Finally, we construct a universal sequence of trees; that is, a sequence in which the limit density of any tree is positive.

preprint2022arXiv

Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming

A long line of research on fixed parameter tractability of integer programming culminated with showing that integer programs with n variables and a constraint matrix with dual tree-depth d and largest entry D are solvable in time g(d,D)poly(n) for some function g. However, the dual tree-depth of a constraint matrix is not preserved by row operations, i.e., a given integer program can be equivalent to another with a smaller dual tree-depth, and thus does not reflect its geometric structure. We prove that the minimum dual tree-depth of a row-equivalent matrix is equal to the branch-depth of the matroid defined by the columns of the matrix. We design a fixed parameter algorithm for computing branch-depth of matroids represented over a finite field and a fixed parameter algorithm for computing a row-equivalent matrix with minimum dual tree-depth. Finally, we use these results to obtain an algorithm for integer programming running in time g(d*,D)poly(n) where d* is the branch-depth of the constraint matrix; the branch-depth cannot be replaced by the more permissive notion of branch-width.

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.

Timothy F. N. Chan

Research overview

Is this your work?

3 publications

Characterization of quasirandom permutations by a pattern sum

Inducibility and universality for trees

Matrices of optimal tree-depth and a row-invariant parameterized algorithm for integer programming

See the researcher in context

Building this map preview