Source author record

Avraham Morgenstern

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

ResearcherUnclaimed source record

math.CO

Catalog footprint

Research overview

4works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

On the local structure of oriented graphs -- a case study in flag algebras

Let $G$ be an $n$ -vertex oriented graph. Let $t(G)$ (respectively $i(G)$ ) be the probability that a random set of $3$ vertices of $G$ spans a transitive triangle (respectively an independent set). We prove that $t(G) + i(G) \geq \frac{1}{9}-o_n(1)$ . Our proof uses the method of flag algebras that we supplement with several steps that make it more easily comprehensible. We also prove a stability result and an exact result. Namely, we describe an extremal construction, prove that it is essentially unique, and prove that if $H$ is sufficiently far from that construction, then $t(H) + i(H)$ is significantly larger than $\frac{1}{9}$ . We go to greater technical detail than is usually done in papers that rely on flag algebras. Our hope is that as a result this text can serve others as a useful introduction to this powerful and beautiful method.

preprint2015arXiv

On the number of 4-cycles in a tournament

If $T$ is an $n$ -vertex tournament with a given number of $3$ -cycles, what can be said about the number of its $4$ -cycles? The most interesting range of this problem is where $T$ is assumed to have $c\cdot n^3$ cyclic triples for some $c>0$ and we seek to minimize the number of $4$ -cycles. We conjecture that the (asymptotic) minimizing $T$ is a random blow-up of a constant-sized transitive tournament. Using the method of flag algebras, we derive a lower bound that almost matches the conjectured value. We are able to answer the easier problem of maximizing the number of $4$ -cycles. These questions can be equivalently stated in terms of transitive subtournaments. Namely, given the number of transitive triples in $T$ , how many transitive quadruples can it have? As far as we know, this is the first study of inducibility in tournaments.

preprint2014arXiv

Graphs with few 3-cliques and 3-anticliques are 3-universal

For given integers k, l we ask whether every large graph with a sufficiently small number of k-cliques and k-anticliques must contain an induced copy of every l-vertex graph. Here we prove this claim for k=l=3 with a sharp bound. A similar phenomenon is established as well for tournaments with k=l=4.

preprint2013arXiv

On high-dimensional acyclic tournaments

We study a high-dimensional analog for the notion of an acyclic (aka transitive) tournament. We give upper and lower bounds on the number of $d$ -dimensional $n$ -vertex acyclic tournaments. In addition, we prove that every $n$ -vertex $d$ -dimensional tournament contains an acyclic subtournament of $Ω(\log^{1/d}n)$ vertices and the bound is tight. This statement for tournaments (i.e., the case $d=1$ ) is a well-known fact. We indicate a connection between acyclic high-dimensional tournaments and Ramsey numbers of hypergraphs. We investigate as well the inter-relations among various other notions of acyclicity in high-dimensional to tournaments. These include combinatorial, geometric and topological concepts.

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.