Andrzej Dudek
YOU?
Author Swipe
View article: A Random Coloring Process Gives Improved Bounds for the Erdős-Gyárfás Problem on Generalized Ramsey Numbers
A Random Coloring Process Gives Improved Bounds for the Erdős-Gyárfás Problem on Generalized Ramsey Numbers Open
The Erdős-Gyárfás number $f(n, p, q)$ is the smallest number of colors needed to color the edges of the complete graph $K_n$ so that all of its $p$-clique spans at least $q$ colors. In this paper we improve the best known upper bound on $f…
View article: Loose paths in random ordered hypergraphs
Loose paths in random ordered hypergraphs Open
We consider the length of {\em ordered loose paths} in the random $r$-uniform hypergraph $H=H^{(r)}(n, p)$. A ordered loose path is a sequence of edges $E_1,E_2,\ldots,E_\ell$ where $\max\{j\in E_i\}=\min\{j\in E_{i+1}\}$ for $1\leq i<\ell…
View article: Generalized Ramsey Numbers at the Linear and Quadratic Thresholds
Generalized Ramsey Numbers at the Linear and Quadratic Thresholds Open
The generalized Ramsey number $f(n, p, q)$ is the smallest number of colors needed to color the edges of the complete graph $K_n$ so that every $p$-clique spans at least $q$ colors. Erdős and Gyárfás showed that $f(n, p, q)$ grows linearly…
View article: The generalized Ramsey number $f(n, 5, 8) = \frac 67 n + o(n)$
The generalized Ramsey number $f(n, 5, 8) = \frac 67 n + o(n)$ Open
A $(p, q)$-coloring of $K_n$ is a coloring of the edges of $K_n$ such that every $p$-clique has at least $q$ distinct colors among its edges. The generalized Ramsey number $f(n, p, q)$ is the minimum number of colors such that $K_n$ has a …
View article: Ordered Unavoidable Sub-Structures in Matchings and Random Matchings
Ordered Unavoidable Sub-Structures in Matchings and Random Matchings Open
An ordered matching of size $n$ is a graph on a linearly ordered vertex set $V$, $|V|=2n$, consisting of $n$ pairwise disjoint edges. There are three different ordered matchings of size two on $V=\{1,2,3,4\}$: an alignment $\{1,2\},\{3,4\}…
View article: Largest bipartite sub-matchings of a random ordered matching or a problem with socks
Largest bipartite sub-matchings of a random ordered matching or a problem with socks Open
Let M be an ordered matching of size n, that is, a partition of the set r2ns into 2-element subsets.The sock number of M is the maximum size of a sub-matching of M in which all left-ends of the edges precede all the right-ends (such matchi…
View article: Largest bipartite sub-matchings of a random ordered matching or a problem with socks
Largest bipartite sub-matchings of a random ordered matching or a problem with socks Open
Let $M$ be an ordered matching of size $n$, that is, a partition of the set $[2n]$ into 2-element subsets. The sock number of $M$ is the maximum size of a sub-matching of $M$ in which all left-ends of the edges precede all the right-ends (…
View article: Twins in ordered hyper-matchings
Twins in ordered hyper-matchings Open
An ordered r-matching of size n is an r-uniform hypergraph on a linearly ordered set of vertices, consisting of n pairwise disjoint edges.Two ordered r-matchings are isomorphic if there is an order-preserving isomorphism between them.A pai…
View article: Twins in ordered hyper-matchings
Twins in ordered hyper-matchings Open
An ordered $r$-matching of size $n$ is an $r$-uniform hypergraph on a linearly ordered set of vertices, consisting of $n$ pairwise disjoint edges. Two ordered $r$-matchings are isomorphic if there is an order-preserving isomorphism between…
View article: Generalized Ramsey numbers at the linear and quadratic thresholds
Generalized Ramsey numbers at the linear and quadratic thresholds Open
The generalized Ramsey number $f(n, p, q)$ is the smallest number of colors needed to color the edges of the complete graph $K_n$ so that every $p$-clique spans at least $q$ colors. Erdős and Gyárfás showed that $f(n, p, q)$ grows linearly…
View article: Erdős-Szekeres type Theorems for ordered uniform matchings
Erdős-Szekeres type Theorems for ordered uniform matchings Open
For $r,n\ge2$, an ordered $r$-uniform matching of size $n$ is an $r$-uniform hypergraph on a linearly ordered vertex set $V$, with $|V|=rn$, consisting of $n$ pairwise disjoint edges. There are $\tfrac12\binom{2r}r$ different ways two edge…
View article: A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers
A random coloring process gives improved bounds for the Erdős-Gyárfás problem on generalized Ramsey numbers Open
The Erdős-Gyárfás number $f(n, p, q)$ is the smallest number of colors needed to color the edges of the complete graph $K_n$ so that all of its $p$-clique spans at least $q$ colors. In this paper we improve the best known upper bound on $f…
View article: Ordered unavoidable sub-structures in matchings and random matchings
Ordered unavoidable sub-structures in matchings and random matchings Open
An ordered matching of size $n$ is a graph on a linearly ordered vertex set $V$, $|V|=2n$, consisting of $n$ pairwise disjoint edges. There are three different ordered matchings of size two on $V=\{1,2,3,4\}$: an alignment $\{1,2\},\{3,4\}…
View article: A note on non-isomorphic edge-color classes in random graphs
A note on non-isomorphic edge-color classes in random graphs Open
For a graph $G$, let $τ(G)$ be the maximum number of colors such that there exists an edge-coloring of $G$ with no two color classes being isomorphic. We investigate the behavior of $τ(G)$ when $G=G(n, p)$ is the classical Erdős-Rényi rand…
View article: The Erdős-Gyárfás function $f(n, 4, 5) = \frac 56 n + o(n)$ -- so Gyárfás was right
The Erdős-Gyárfás function $f(n, 4, 5) = \frac 56 n + o(n)$ -- so Gyárfás was right Open
A $(4, 5)$-coloring of $K_n$ is an edge-coloring of $K_n$ where every $4$-clique spans at least five colors. We show that there exist $(4, 5)$-colorings of $K_n$ using $\frac 56 n + o(n)$ colors. This settles a disagreement between Erdős a…
View article: Powers of Hamiltonian cycles in randomly augmented Dirac graphs -- the complete collection
Powers of Hamiltonian cycles in randomly augmented Dirac graphs -- the complete collection Open
We study the powers of Hamiltonian cycles in randomly augmented Dirac graphs, that is, $n$-vertex graphs $G$ with minimum degree at least $(1/2+\varepsilon)n$ to which some random edges are added. For any Dirac graph and every integer $m\g…
View article: Variations on Twins in Permutations
Variations on Twins in Permutations Open
Let $\pi$ be a permutation of the set $[n]=\{1,2,\dots, n\}$. Two disjoint order-isomorphic subsequences of $\pi$ are called twins. How long twins are contained in every permutation? The well known Erdős-Szekeres theorem implies that there…
View article: Multiple twins in permutations
Multiple twins in permutations Open
By an $r$-tuplet in a permutation we mean a family of $r$ pairwise disjoint subsequences with the same relative order. The length of an $r$-tuplet is defined as the length of any single subsequence in the family. Let $t^{(r)}(n)$ denote th…
View article: Closing the Random Graph Gap in Tuza's Conjecture through the Online Triangle Packing Process
Closing the Random Graph Gap in Tuza's Conjecture through the Online Triangle Packing Process Open
A long-standing conjecture of Zsolt Tuza asserts that the triangle covering number $τ(G)$ is at most twice the triangle packing number $ν(G)$, where the triangle packing number $ν(G)$ is the maximum size of a set of edge-disjoint triangles…
View article: On weak twins and up-and-down sub-permutations
On weak twins and up-and-down sub-permutations Open
Two permutations $(x_1,\dots,x_w)$ and $(y_1,\dots,y_w)$ are weakly similar if $x_iπ(i_2)...$ or $π(i_1)π(i_3)
View article: Large triangle packings and Tuza’s conjecture in sparse random graphs
Large triangle packings and Tuza’s conjecture in sparse random graphs Open
The triangle packing number v ( G ) of a graph G is the maximum size of a set of edge-disjoint triangles in G . Tuza conjectured that in any graph G there exists a set of at most 2 v ( G ) edges intersecting every triangle in G . We show t…
View article: A gentle introduction to the differential equation method and dynamic concentration
A gentle introduction to the differential equation method and dynamic concentration Open
We discuss the differential equation method for establishing dynamic concentration of discrete random processes. We present several relatively simple examples of it and aim to make the method understandable to the unfamiliar reader who has…
View article: High powers of Hamiltonian cycles in randomly augmented graphs
High powers of Hamiltonian cycles in randomly augmented graphs Open
We investigate the existence of powers of Hamiltonian cycles in graphs with large minimum degree to which some additional edges have been added in a random manner. For all integers $k\geq1$, $r\geq 0$, and $\ell\geq (r+1)r$, and for any $α…
View article: Monochromatic loose paths in multicolored $k$-uniform cliques
Monochromatic loose paths in multicolored $k$-uniform cliques Open
For integers $k\ge 2$ and $\ell\ge 0$, a $k$-uniform hypergraph is called a loose path of length $\ell$, and denoted by $P_\ell^{(k)}$, if it consists of $\ell $ edges $e_1,\dots,e_\ell$ such that $|e_i\cap e_j|=1$ if $|i-j|=1$ and $e_i\ca…
View article: An analogue of the Erdős-Gallai theorem for random graphs
An analogue of the Erdős-Gallai theorem for random graphs Open
Recently, variants of many classical extremal theorems have been proved in the random environment. We, complementing existing results, extend the Erdős-Gallai Theorem in random graphs. In particular, we determine, up to a constant factor, …
View article: An analogue of the Erd\H{o}s-Gallai theorem for random graphs
An analogue of the Erd\H{o}s-Gallai theorem for random graphs Open
Recently, variants of many classical extremal theorems have been proved in\nthe random environment. We, complementing existing results, extend the\nErd\\H{o}s-Gallai Theorem in random graphs. In particular, we determine, up to a\nconstant …