Source author record

Eoin Long

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

ResearcherUnclaimed source record

math.CO Information Theory math.IT math.PR

Catalog footprint

Research overview

15works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2021arXiv

Global hypercontractivity and its applications

The hypercontractive inequality on the discrete cube plays a crucial role in many fundamental results in the Analysis of Boolean functions, such as the KKL theorem, Friedgut's junta theorem and the invariance principle. In these results the cube is equipped with the uniform measure, but it is desirable, particularly for applications to the theory of sharp thresholds, to also obtain such results for general $p$ -biased measures. However, simple examples show that when $p = o(1)$ , there is no hypercontractive inequality that is strong enough. In this paper, we establish an effective hypercontractive inequality for general $p$ that applies to `global functions', i.e. functions that are not significantly affected by a restriction of a small set of coordinates. This class of functions appears naturally, e.g. in Bourgain's sharp threshold theorem, which states that such functions exhibit a sharp threshold. We demonstrate the power of our tool by strengthening Bourgain's theorem, thereby making progress on a conjecture of Kahn and Kalai and by establishing a $p$ -biased analog of the invariance principle. Our results have significant applications in Extremal Combinatorics. Here we obtain new results on the Turán number of any bounded degree uniform hypergraph obtained as the expansion of a hypergraph of bounded uniformity. These are asymptotically sharp over an essentially optimal regime for both the uniformity and the number of edges and solve a number of open problems in the area. In particular, we give general conditions under which the crosscut parameter asymptotically determines the Turán number, answering a question of Mubayi and Verstraëte. We also apply the Junta Method to refine our asymptotic results and obtain several exact results, including proofs of the Huang--Loh--Sudakov conjecture on cross matchings and the Füredi--Jiang--Seiver conjecture on path expansions.

preprint2020arXiv

Correlation for permutations

In this note we investigate correlation inequalities for `up-sets' of permutations, in the spirit of the Harris--Kleitman inequality. We focus on two well-studied partial orders on $S_n$ , giving rise to differing notions of up-sets. Our first result shows that, under the strong Bruhat order on $S_n$ , up-sets are positively correlated (in the Harris--Kleitman sense). Thus, for example, for a (uniformly) random permutation $π$ , the event that no point is displaced by more than a fixed distance $d$ and the event that $π$ is the product of at most $k$ adjacent transpositions are positively correlated. In contrast, under the weak Bruhat order we show that this completely fails: surprisingly, there are two up-sets each of measure $1/2$ whose intersection has arbitrarily small measure. We also prove analogous correlation results for a class of non-uniform measures, which includes the Mallows measures. Some applications and open problems are discussed.

preprint2016arXiv

Counting Hamilton decompositions of oriented graphs

A Hamilton cycle in a directed graph $G$ is a cycle that passes through every vertex of $G$ . A Hamiltonian decomposition of $G$ is a partition of its edge set into disjoint Hamilton cycles. In the late $60$ s Kelly conjectured that every regular tournament has a Hamilton decomposition. This conjecture was recently settled by Kühn and Osthus, who proved more generally that every $r$ -regular $n$ -vertex oriented graph $G$ (without antiparallel edges) with $r=cn$ for some fixed $c>3/8$ has a Hamiltonian decomposition, provided $n=n(c)$ is sufficiently large. In this paper we address the natural question of estimating the number of such decompositions of $G$ and show that this number is $n^{(1-o(1))cn^2}$ . In addition, we also obtain a new and much simpler proof for the approximate version of Kelly's conjecture.

preprint2016arXiv

Large unavoidable subtournaments

Let $D_k$ denote the tournament on $3k$ vertices consisting of three disjoint vertex classes $V_1, V_2$ and $V_3$ of size $k$ , each of which is oriented as a transitive subtournament, and with edges directed from $V_1$ to $V_2$ , from $V_2$ to $V_3$ and from $V_3$ to $V_1$ . Fox and Sudakov proved that given a natural number $k$ and $ε> 0$ there is $n_0(k,ε)$ such that every tournament of order $n_0(k,ε)$ which is $ε$ -far from being transitive contains $D_k$ as a subtournament. Their proof showed that $n_0(k,ε) \leq ε^{-O(k/ε^2)}$ and they conjectured that this could be reduced to $n_0(k,ε) \leq ε^{-O(k)}$ . Here we prove this conjecture.

preprint2016arXiv

On the normalized Shannon capacity of a union

Let $G_1 \times G_2$ denote the strong product of graphs $G_1$ and $G_2$ , i.e. the graph on $V(G_1) \times V(G_2)$ in which $(u_1,u_2)$ and $(v_1,v_2)$ are adjacent if for each $i=1,2$ we have $u_i=v_i$ or $u_iv_i \in E(G_i)$ . The Shannon capacity of $G$ is $c(G) = \lim_{n\to \infty} α(G^n)^{1/n}$ , where $G^n$ denotes the $n$ -fold strong power of $G$ , and $α(H)$ denotes the independence number of a graph $H$ . The normalized Shannon capacity of $G$ is $C(G) = \frac {\log c(G)}{\log |V(G)|}$ . Alon asked whether for every $ε> 0$ there are graphs $G$ and $G'$ satisfying $C(G), C(G') < ε$ but with $C(G + G') > 1 - ε$ . We show that the answer is no.

preprint2016arXiv

Packing and counting arbitrary Hamilton cycles in random digraphs

We prove packing and counting theorems for arbitrarily oriented Hamilton cycles in ${\cal D}(n,p)$ for nearly optimal $p$ (up to a $\log ^cn$ factor). In particular, we show that given $t = (1-o(1))np$ Hamilton cycles $C_1,\ldots ,C_{t}$ , each of which is oriented arbitrarily, a digraph $D \sim {\cal D}(n,p)$ w.h.p. contains edge disjoint copies of $C_1,\ldots ,C_t$ , provided $p=ω(\log ^3 n/n)$ . We also show that given an arbitrarily oriented $n$ -vertex cycle $C$ , a random digraph $D \sim {\cal D}(n,p)$ w.h.p. contains $(1\pm o(1))n!p^n$ copies of $C$ , provided $p \geq \log ^{1 + o(1)}n/n$ .

preprint2015arXiv

Forbidding intersection patterns between layers of the cube

A family ${\mathcal A} \subset {\mathcal P} [n]$ is said to be an antichain if $A \not \subset B$ for all distinct $A,B \in {\mathcal A}$ . A classic result of Sperner shows that such families satisfy $|{\mathcal A}| \leq \binom {n}{\lfloor n/2\rfloor}$ , which is easily seen to be best possible. One can view the antichain condition as a restriction on the intersection sizes between sets in different layers of ${\mathcal P} [n]$ . More generally one can ask, given a collection of intersection restrictions between the layers, how large can families respecting these restrictions be? Answering a question of Kalai, we show that for most collections of such restrictions, layered families are asymptotically largest. This extends results of Leader and the author.

preprint2015arXiv

Long paths and cycles in subgraphs of the cube

Let $Q_n$ denote the graph of the $n$ -dimensional cube with vertex set $\{0,1\}^n$ in which two vertices are adjacent if they differ in exactly one coordinate. Suppose $G$ is a subgraph of $Q_n$ with average degree at least $d$ . How long a path can we guarantee to find in $G$ ? Our aim in this paper is to show that $G$ must contain an exponentially long path. In fact, we show that if $G$ has minimum degree at least $d$ then $G$ must contain a path of length $2^d-1$ . Note that this bound is tight, as shown by a $d$ -dimensional subcube of $Q_n$ . We also obtain the slightly stronger result that $G$ must contain a cycle of length at least $2^d$ and prove analogous results for other `product-type' graphs.

preprint2015arXiv

Packing, Counting and Covering Hamilton cycles in random directed graphs

A Hamilton cycle in a digraph is a cycle that passes through all the vertices, where all the arcs are oriented in the same direction. The problem of finding Hamilton cycles in directed graphs is well studied and is known to be hard. One of the main reasons for this, is that there is no general tool for finding Hamilton cycles in directed graphs comparable to the so called Pos?a `rotation-extension' technique for the undirected analogue. Let ${\mathcal D}(n,p)$ denote the random digraph on vertex set $[n]$ , obtained by adding each directed edge independently with probability $p$ . Here, we present a general and a very simple method, using known results, to attack problems of packing and counting Hamilton cycles in random directed graphs, for every edge-probability $p>\log^C(n)/n$ . Our results are asymptotically optimal with respect to all parameters and apply equally well to the undirected case.

preprint2015arXiv

Set families with a forbidden pattern

A balanced pattern of order $2d$ is an element $P \in \{+,-\}^{2d}$ , where both signs appear $d$ times. Two sets $A,B \subset [n]$ form $P$ -pattern, which we denote by $\operatorname{pat}(A,B) = P$ , if $A\triangle B = \{j_1,\ldots ,j_{2d}\}$ with $1\leq j_1<\cdots < j_{2d}\leq n$ and $\{i\in [2d]: P_i = + \} = \{i\in [2d]: j_i \in A \setminus B\}$ . We say ${\cal A} \subset {\cal P}[n]$ is $P$ -free if $\operatorname{pat}(A,B)\neq P$ for all $A,B \in {\cal A}$ . We consider the following extremal question: how large can a family ${\cal A} \subset {\cal P}[n]$ be if ${\cal A}$ is $P$ -free? We prove a number of results on the sizes of such families. In particular, we show that for some fixed $c>0$ , if $P$ is a $d$ -balanced pattern with $d < c \log \log n$ then $|{\cal A}| = o(2^n)$ . We then give stronger bounds in the cases when (i) $P$ consists of $d$ $+$ signs, followed by $d$ $-$ signs and (ii) $P$ consists of alternating signs. In both cases, if $d = o(\sqrt n)$ then $|{\cal A} | = o(2^n)$ . In the case of (i), this is tight. .

preprint2014arXiv

Frankl-Rödl type theorems for codes and permutations

We give a new proof of the Frankl-Rödl theorem on forbidden intersections, via the probabilistic method of dependent random choice. Our method extends to codes with forbidden distances, where over large alphabets our bound is significantly better than that obtained by Frankl and Rödl. We also apply our bound to a question of Ellis on sets of permutations with forbidden distances, and to establish a weak form of a conjecture of Alon, Shpilka and Umans on sunflowers.

preprint2013arXiv

Forbidding a Set Difference of Size 1

How large can a family \cal A \subset \cal P [n] be if it does not contain A,B with |A\setminus B| = 1? Our aim in this paper is to show that any such family has size at most \frac{2+o(1)}{n} \binom {n}{\lfloor n/2\rfloor }. This is tight up to a multiplicative constant of $2$ . We also obtain similar results for families \cal A \subset \cal P[n] with |A\setminus B| \neq k, showing that they satisfy |{\mathcal A}| \leq \frac{C_k}{n^k}\binom {n}{\lfloor n/2\rfloor }, where C_k is a constant depending only on k.

preprint2013arXiv

Long geodesics in subgraphs of the cube

A path in the hypercube $Q_n$ is said to be a geodesic if no two of its edges are in the same direction. Let $G$ be a subgraph of $Q_n$ with average degree $d$ . How long a geodesic must $G$ contain? We show that $G$ must contain a geodesic of length $d$ . This result, which is best possible, strengthens a theorem of Feder and Subi. It is also related to the `antipodal colourings' conjecture of Norine.

preprint2013arXiv

Random walks on quasirandom graphs

Let G be a quasirandom graph on n vertices, and let W be a random walk on G of length alpha n^2. Must the set of edges traversed by W form a quasirandom graph? This question was asked by Böttcher, Hladký, Piguet and Taraz. Our aim in this paper is to give a positive answer to this question. We also prove a similar result for random embeddings of trees.

preprint2011arXiv

Tilted Sperner Families

Let \cal A be a family of subsets of an n-set such that \cal A does not contain distinct sets A and B with |A\B| = 2|B\A|. How large can \cal A be? Our aim in this note is to determine the maximum size of such an \cal A. This answers a question of Kalai. We also give some related results and conjectures.

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.

Eoin Long

Research overview

Is this your work?

15 publications

Global hypercontractivity and its applications

Correlation for permutations

Counting Hamilton decompositions of oriented graphs

Large unavoidable subtournaments

On the normalized Shannon capacity of a union

Packing and counting arbitrary Hamilton cycles in random digraphs

Forbidding intersection patterns between layers of the cube

Long paths and cycles in subgraphs of the cube

Packing, Counting and Covering Hamilton cycles in random directed graphs

Set families with a forbidden pattern

Frankl-Rödl type theorems for codes and permutations

Forbidding a Set Difference of Size 1

Long geodesics in subgraphs of the cube

Random walks on quasirandom graphs

Tilted Sperner Families

See the researcher in context

Building this map preview