Source author record

Zur Luria

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

ResearcherUnclaimed source record

math.CO math.PR math.GR

Catalog footprint

Research overview

10works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Discrepancy of High-Dimensional Permutations

Let $L$ be an order- $n$ Latin square. For $X, Y, Z \subseteq \{1, ... ,n\}$ , let $L(X, Y. Z)$ be the number of triples $i\in X, j\in Y, k\in Z$ such that $L(i,j) = k$ . We conjecture that asymptotically almost every Latin square satisfies $|L(X, Y, Z) - \frac 1n |X||Y||Z||\le O(\sqrt{|X||Y||Z|})$ for every $X, Y$ and $Z$ . Let $\varepsilon(L):= \max |X||Y||Z|$ when $L(X, Y, Z)=0$ . The above conjecture implies that $\varepsilon(L) \le O(n^2)$ holds asymptotically almost surely (this bound is obviously tight). We show that there exist Latin squares with $\varepsilon(L) \le O(n^2)$ , and that $\varepsilon(L) \le O(n^2 \log^2 n)$ for almost every order- $n$ Latin square. On the other hand, we recall that $\varepsilon(L)\geq Ω(n^{33/14})$ if $L$ is the multiplication table of an order- $n$ group. Some of these results extend to higher dimensions. Many open problems remain.

preprint2016arXiv

On groups and simplicial complexes

The theory of $k$ -regular graphs is closely related to group theory. Every $k$ -regular, bipartite graph is a Schreier graph with respect to some group $G$ , a set of generators $S$ (depending only on $k$ ) and a subgroup $H$ . The goal of this paper is to begin to develop such a framework for $k$ -regular simplicial complexes of general dimension $d$ . Our approach does not directly generalize the concept of a Schreier graph, but still presents an extensive family of $k$ -regular simplicial complexes as quotients of one universal object: the $k$ -regular $d$ -dimensional arboreal complex, which is itself a simplicial complex originating in one specific group depending only on $d$ and $k$ . Along the way we answer a question from [PR12] on the spectral gap of higher dimensional Laplacians and prove a high dimensional analogue of Leighton's graph covering theorem. This approach also suggests a random model for $k$ -regular $d$ -dimensional multicomplexes.

preprint2016arXiv

The number of Hamiltonian decompositions of regular graphs

A Hamilton cycle in a graph $Γ$ is a cycle passing through every vertex of $Γ$ . A Hamiltonian decomposition of $Γ$ is a partition of its edge set into disjoint Hamilton cycles. One of the oldest results in graph theory is Walecki's theorem from the 19th century, showing that a complete graph $K_n$ on an odd number of vertices $n$ has a Hamiltonian decomposition. This result was recently greatly extended by Kühn and Osthus. They proved that every $r$ -regular $n$ -vertex graph $Γ$ with even degree $r=cn$ for some fixed $c>1/2$ has a Hamiltonian decomposition, provided $n=n(c)$ is sufficiently large. In this paper we address the natural question of estimating $H(Γ)$ , the number of such decompositions of $Γ$ . Our main result is that $H(Γ)=r^{(1+o(1))nr/2}$ . In particular, the number of Hamiltonian decompositions of $K_n$ is $n^{(1-o(1))n^2/2}$ .

preprint2015arXiv

On the maximum number of Latin transversals

Let $T(n)$ denote the maximal number of transversals in an order- $n$ Latin square. Improving on the bounds obtained by McKay et al., Taranenko recently proved that $T(n) \leq \left((1+o(1))\frac{n}{e^2}\right)^{n}$ , and conjectured that this bound is tight. We prove via a probabilistic construction that indeed $T(n) = \left((1+o(1))\frac{n}{e^2}\right)^{n}$ . Until the present paper, no superexponential lower bound for $T(n)$ was known. We also give a simpler proof of the upper bound.

preprint2015arXiv

Random Steiner systems and bounded degree coboundary expanders of every dimension

We introduce a new model of random $d$ -dimensional simplicial complexes, for $d\geq 2$ , whose $(d-1)$ -cells have bounded degrees. We show that with high probability, complexes sampled according to this model are coboundary expanders. The construction relies on Keevash's recent result on designs [Ke14], and the proof of the expansion uses techniques developed by Evra and Kaufman in [EK15]. This gives a full solution to a question raised in [DK12], which was solved in the two-dimensional case by Lubotzky and Meshulam [LM13].

preprint2014arXiv

Chernoff's Inequality - A very elementary proof

We give a very simple proof of a strengthened version of Chernoff's Inequality. We derive the same conclusion from much weaker assumptions.

preprint2012arXiv

An upper bound on the number of high-dimensional permutations

What is the higher-dimensional analog of a permutation? If we think of a permutation as given by a permutation matrix, then the following definition suggests itself: A d-dimensional permutation of order n is an [n]^(d+1) array of zeros and ones in which every "line" contains a unique 1 entry. A line here is a set of entries of the form {(x_1,...,x_{i-1},y,x_{i+1},...,x_{d+1})}, for y between 1 and n, some index i between 1 and d+1 and some choice of x_j in [n] for all j except i. It is easy to observe that a one-dimensional permutation is simply a permutation matrix and that a two-dimensional permutation is synonymous with an order-n Latin square. We seek an estimate for the number of d-dimensional permutations. Our main result is the following upper bound on their number: ((1+o(1))(n/e^d))^(n^d). We tend to believe that this is actually the correct number, but the problem of proving the complementary lower bound remains open. Our main tool is an adaptation of Bregman's proof of the Minc conjecture on permanents. More concretely, our approach is very close in spirit to Radhakrishnan's proof of Bregman's theorem.

preprint2012arXiv

On the vertices of the d-dimensional Birkhoff polytope

Consider the Birkhoff polytope of n by n doubly-stochastic matrices. As the Birkhoff-von Neumann theorem famously states, its vertex set coincides with the set of all n by n permutation matrices. Here we seek a higher-dimensional analog of this basic fact. Namely, consider the polytope which consists of all tristochastic arrays of order n. These are n by n by n arrays with nonnegative entries in which every line sums to 1. What can be said about its vertex set? It is well-known that an order-n Latin square may be viewed as a tristochastic array where every line contains n-1 zeros and a single 1 entry. Indeed, every Latin square of order n is a vertex, but as we show, such vertices constitute only a vanishingly small part of the total number of vertices. More concretely, we show that the number of vertices is at least (L_n)^{3/2-o(1)}, where L_n is the number of order-n Latin squares. We also briefly consider similar problems concerning the polytope of n by n by n arrays where the entries in every coordinate hyperplane sum to 1. Several open questions are presented as well.

preprint2011arXiv

An Upper bound on the number of Steiner triple systems

Let STS(n) denote the number of Steiner triple systems on n vertices, and let F(n) denote the number of 1-factorizations of the complete graph on n vertices. We prove the following upper bound. STS(n) <= ((1 + o(1)) (n/e^2))^(n^2/6) F(n) <= ((1 + o(1)) (n/e^2))^(n^2/2) We conjecture that the bound is sharp. Our main tool is the entropy method.

preprint2008arXiv

An approximation algorithm for counting contingency tables

We present a randomized approximation algorithm for counting contingency tables, mxn non-negative integer matrices with given row sums R=(r_1, ..., r_m) and column sums C=(c_1, ..., c_n). We define smooth margins (R,C) in terms of the typical table and prove that for such margins the algorithm has quasi-polynomial N^{O(ln N)} complexity, where N=r_1+...+r_m=c_1+...+c_n. Various classes of margins are smooth, e.g., when m=O(n), n=O(m) and the ratios between the largest and the smallest row sums as well as between the largest and the smallest column sums are strictly smaller than the golden ratio (1+sqrt{5})/2 = 1.618. The algorithm builds on Monte Carlo integration and sampling algorithms for log-concave densities, the matrix scaling algorithm, the permanent approximation algorithm, and an integral representation for the number of contingency tables.

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.

Zur Luria

Research overview

Is this your work?

10 publications

Discrepancy of High-Dimensional Permutations

On groups and simplicial complexes

The number of Hamiltonian decompositions of regular graphs

On the maximum number of Latin transversals

Random Steiner systems and bounded degree coboundary expanders of every dimension

Chernoff's Inequality - A very elementary proof

An upper bound on the number of high-dimensional permutations

On the vertices of the d-dimensional Birkhoff polytope

An Upper bound on the number of Steiner triple systems

An approximation algorithm for counting contingency tables

See the researcher in context

Building this map preview