Raphael Yuster
YOU?
Author Swipe
View article: On Tournament Inversion
On Tournament Inversion Open
An inversion of a tournament is obtained by reversing the direction of all edges with both endpoints in some set of vertices. Let be the minimum length of a sequence of inversions using sets of size at most that result in the transitive to…
View article: On the Minimum Density of Monotone Subwords
On the Minimum Density of Monotone Subwords Open
We consider the asymptotic minimum density $f(s,k)$ of monotone $k$-subwords of words over a totally ordered alphabet of size $s$. The unrestricted alphabet case, $f(\infty,k)$, is well-studied, known for $f(\infty,3)$ and $f(\infty,4)$, a…
View article: On the minimum density of monotone subwords
On the minimum density of monotone subwords Open
We consider the asymptotic minimum density $f(s,k)$ of monotone $k$-subwords of words over a totally ordered alphabet of size $s$. The unrestricted alphabet case, $f(\infty,k)$, is well-studied, known for $f(\infty,3)$ and $f(\infty,4)$, a…
View article: Highly Connected Graphs Have Highly Connected Spanning Bipartite Subgraphs
Highly Connected Graphs Have Highly Connected Spanning Bipartite Subgraphs Open
For integers $k,n$ with $1 \le k \le n/2$, let $f(k,n)$ be the smallest integer $t$ such that every $t$-connected $n$-vertex graph has a spanning bipartite $k$-connected subgraph. A conjecture of Thomassen asserts that $f(k,n)$ is upper bo…
View article: Flip colouring of graphs
Flip colouring of graphs Open
It is proved that for integers $b, r$ such that $3 \leq b < r \leq \binom{b+1}{2} - 1$, there exists a red/blue edge-colored graph such that the red degree of every vertex is $r$, the blue degree of every vertex is $b$, yet in the closed n…
View article: On tournament inversion
On tournament inversion Open
An {\it inversion} of a tournament $T$ is obtained by reversing the direction of all edges with both endpoints in some set of vertices. Let ${\rm inv}_k(T)$ be the minimum length of a sequence of inversions using sets of size at most $k$ t…
View article: Packing and covering a given directed graph in a directed graph
Packing and covering a given directed graph in a directed graph Open
For every fixed $k \ge 4$, it is proved that if an $n$-vertex directed graph has at most $t$ pairwise arc-disjoint directed $k$-cycles, then there exists a set of at most $\frac{2}{3}kt+ o(n^2)$ arcs that meets all directed $k$-cycles and …
View article: Finding and counting small tournaments in large tournaments
Finding and counting small tournaments in large tournaments Open
We present new algorithms for counting and detecting small tournaments in a given tournament. In particular, it is proved that every tournament on four vertices (there are four) can be detected in $O(n^2)$ time and counted in $O(n^ω)$ time…
View article: Almost $k$-union closed set systems
Almost $k$-union closed set systems Open
In a recent breakthrough, Gilmer proved the union closed conjecture up to a constant factor. Using Gilmer's method and additional ideas, Chase and Lovett proved an optimal result for almost union-closed set systems. Here that result is ext…
View article: The Covering Threshold of a Directed Acyclic Graph by Directed Acyclic Subgraphs
The Covering Threshold of a Directed Acyclic Graph by Directed Acyclic Subgraphs Open
Let $H$ be a directed acyclic graph (dag) that is not a rooted star. It is known that there are constants $c=c(H)$ and $C=C(H)$ such that the following holds for $D_n$, the complete directed graph on $n$ vertices. There is a set of at most…
View article: The number of bounded-degree spanning trees
The number of bounded-degree spanning trees Open
For a graph $G$, let $c_k(G)$ be the number of spanning trees of $G$ with maximum degree at most $k$. For $k \ge 3$, it is proved that every connected $n$-vertex $r$-regular graph $G$ with $r \ge \frac{n}{k+1}$ satisfies $$ c_k(G)^{1/n} \g…
View article: Ramsey number of 1-subdivisions of transitive tournaments
Ramsey number of 1-subdivisions of transitive tournaments Open
The study of problems concerning subdivisions of graphs has a rich history in extremal combinatorics. Confirming a conjecture of Burr and Erdős, Alon proved in 1994 that subdivided graphs have linear Ramsey numbers. Later, Alon, Krivelevic…
View article: The covering threshold of a directed acyclic graph by directed acyclic subgraphs
The covering threshold of a directed acyclic graph by directed acyclic subgraphs Open
Let $H$ be a directed acyclic graph other than a rooted star. It is known that there are constants $c(H)$ and $C(H)$ such that the following holds for the complete directed graph $D_n$. There are at most $C\log n$ directed acyclic subgraph…
View article: On the quartet distance given partial information
On the quartet distance given partial information Open
Let $T$ be an arbitrary phylogenetic tree with $n$ leaves. It is well-known that the average quartet distance between two assignments of taxa to the leaves of $T$ is $\frac 23 \binom{n}{4}$. However, a longstanding conjecture of Bandelt an…
View article: On Factors of Independent Transversals in $k$-Partite Graphs
On Factors of Independent Transversals in $k$-Partite Graphs Open
A $[k,n,1]$-graph is a $k$-partite graph with parts of order $n$ such that the bipartite graph induced by any pair of parts is a matching. An independent transversal in such a graph is an independent set that intersects each part in a sing…
View article: Ramsey number of 1-subdivisions of transitive tournaments
Ramsey number of 1-subdivisions of transitive tournaments Open
The study of problems concerning subdivisions of graphs has a rich history in extremal combinatorics. Confirming a conjecture of Burr and Erdős, Alon proved in 1994 that subdivided graphs have linear Ramsey numbers. Later, Alon, Krivelevic…
View article: Issue Information
Issue Information Open
Rest of World), €4415 (Europe), £3495 (UK).Prices are exclusive of tax.Asia-Pacifi
View article: Perfect and nearly perfect separation dimension of complete and random graphs
Perfect and nearly perfect separation dimension of complete and random graphs Open
The separation dimension of a hypergraph is the smallest natural number for which there is an embedding of into , such that any pair of disjoint edges is separated by some hyperplane normal to one of the axes. The perfect separation dimens…
View article: Sum-distinguishing number of sparse hypergraphs
Sum-distinguishing number of sparse hypergraphs Open
A vertex labeling of a hypergraph is sum distinguishing if it uses positive integers and the sums of labels taken over the distinct hyperedges are distinct. Let s(H) be the smallest integer N such that there is a sum-distinguishing labelin…
View article: Counting Homomorphic Cycles in Degenerate Graphs
Counting Homomorphic Cycles in Degenerate Graphs Open
Since counting subgraphs in general graphs is, by and large, a computationally demanding problem, it is natural to try and design fast algorithms for restricted families of graphs. One such family that has been extensively studied is that …
View article: Covering Small Subgraphs of (Hyper)Tournaments with Spanning Acyclic Subgraphs
Covering Small Subgraphs of (Hyper)Tournaments with Spanning Acyclic Subgraphs Open
While the edges of every tournament can be covered with two spanning acyclic subgraphs, this is not so if we set out to cover all acyclic $H$-subgraphs of a tournament with spanning acyclic subgraphs, even for very simple $H$ such as the $…
View article: Dominant tournament families
Dominant tournament families Open
For a tournament $H$ with $h$ vertices, its typical density is $h!2^{-\binom{h}{2}}/aut(H)$, i.e. this is the expected density of $H$ in a random tournament. A family ${\mathcal F}$ of $h$-vertex tournaments is {\em dominant} if for all su…
View article: Perfect sequence covering arrays
Perfect sequence covering arrays Open
An $(n,k)$ sequence covering array is a set of permutations of $[n]$ such that each sequence of $k$ distinct elements of $[n]$ is a subsequence of at least one of the permutations. An $(n,k)$ sequence covering array is perfect if there is …
View article: Clumsy Packings of Graphs
Clumsy Packings of Graphs Open
Let $G$ and $H$ be graphs. We say that $P$ is an $H$-packing of $G$ if $P$ is a set of edge-disjoint copies of $H$ in $G$. An $H$-packing $P$ is maximal if there is no other $H$-packing of $G$ that properly contains P. Packings of maximum …