BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Andrzej Dudek

Andrzej Dudek appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
math.COmath.PR

Catalog footprint

What is connected

32works
2topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

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.

Published work

32 published item(s)

preprint2025arXiv

Powers of Hamiltonian cycles in randomly augmented Pósa-Seymour graphs

We study the question of the least number of random edges that need to be added to a Pósa-Seymour graph, that is, a graph with minimum degree exceeding $\frac k{k+1}n$, to secure the existence of the $m$-th power of a Hamiltonian cycle, $m>k$. It turns out that, depending on $k$ and $m$, this quantity may be captured by two types of thresholds, with one of them, called over-threshold, becoming dominant for large $m$. Indeed, for each $k\ge2$ and $m>m_0(k)$, we establish asymptotically tight lower and upper bounds on the over-thresholds (provided they exist) and show that for infinitely many instances of $m$ the two bounds coincide. In addition, we also determine the thresholds for some small values of $k$ and $m$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

The Erdős-Gyárfás function $f(n, 4, 5) = \frac 56 n + o(n)$ -- so Gyárfás was right

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 and Gyárfás reported in their 1997 paper. Our construction uses a randomized process which we analyze using the so-called differential equation method to establish dynamic concentration. In particular, our coloring process uses random triangle removal, a process first introduced by Bollobás and Erdős, and analyzed by Bohman, Frieze and Lubetzky.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

An analogue of the Erdős-Gallai theorem for random graphs

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, the maximum number of edges in a $P_n$-free subgraph of $G(N,p)$, practically for all values of $N,n$ and $p$. Our work is also motivated by the recent progress on the size-Ramsey number of paths.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Closing the Random Graph Gap in Tuza's Conjecture Through the Online Triangle Packing Process

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 in $G$ and the triangle covering number $τ(G)$ is the minimal size of a set of edges intersecting all triangles. In this paper, we prove that Tuza's conjecture holds in the Erdős-Rényi random graph $G(n,m)$ for all range of $m$, closing the gap in what was previously known. (Recently, this result was also independently proved by Jeff Kahn and Jinyoung Park.) We employ a random greedy process called the online triangle packing process to produce a triangle packing in $G(n,m)$ and analyze this process by using the differential equations method.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large triangle packings and Tuza's conjecture in sparse random graphs

The triangle packing number $ν(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ν(G)$ edges intersecting every triangle in $G$. We show that Tuza's conjecture holds in the random graph $G=G(n,m)$, when $m \le 0.2403n^{3/2}$ or $m\ge 2.1243n^{3/2}$. This is done by analyzing a greedy algorithm for finding large triangle packings in random graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Localization Game for Random Graphs

We consider the localization game played on graphs in which a cop tries to determine the exact location of an invisible robber by exploiting distance probes. The corresponding graph parameter $ζ(G)$ for a given graph $G$ is called the localization number. In this paper, we improve the bounds for dense random graphs determining an asymptotic behaviour of $ζ(G)$. Moreover, we extend the argument to sparse graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

On the number of alternating paths in random graphs

In the noisy channel model from coding theory, we wish to detect errors introduced during transmission by optimizing various parameters of the code. Bennett, Dudek, and LaForge framed a variation of this problem in the language of alternating paths in edge-colored complete bipartite graphs in 2016. Here, we extend this problem to the random graph $\mathbb{G}(n,p)$. We seek the alternating connectivity, $κ_{r,\ell}(G)$, which is the maximum $t$ such that there is an $r$-edge-coloring of $G$ such that any pair of vertices is connected by $t$ internally disjoint and alternating (i.e. no consecutive edges of the same color) paths of length $\ell$. We have three main results about how this parameter behaves in $\mathbb{G}(n,p)$ that basically cover all ranges of $p$: one for paths of length two, one for the dense case, and one for the sparse case. For paths of length two, we found that $κ_{r,\ell}(G)$ is essentially the codegree of a pair of vertices. For the dense case when $p$ is constant, we were able to achieve the natural upper bounds of minimum degree (minus some intersection) or the total number of disjoint paths between a pair of vertices. For the sparse case, we were able to find colorings that achieved the natural obstructions of minimum degree or (in a slightly less precise result) the total number of paths of a certain length in a graph. We broke up this sparse case into ranges of $p$ corresponding to when $\mathbb{G}(n,p)$ has diameter $k$ or $k+1$. We close with some remarks about a similar parameter and a generalization to pseudorandom graphs.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Variations on twins in permutations

Let $π$ be a permutation of the set $[n]=\{1,2,\dots, n\}$. Two disjoint order-isomorphic subsequences of $π$ are called twins. How long twins are contained in every permutation? The well known Erdős-Szekeres theorem implies that there is always a pair of twins of length $Ω(\sqrt{n})$. On the other hand, by a simple probabilistic argument Gawron proved that for every $n\geqslant 1$ there exist permutations with all twins having length $O(n^{2/3})$. He conjectured that the latter bound is the correct size of the longest twins guaranteed in every permutation. We support this conjecture by showing that almost all permutations contain twins of length $Ω(n^{2/3}/\log n^{1/3})$. Recently, Bukh and Rudenko have tweaked our proof and removed the log-factor. For completeness, we also present our version of their proof (see Remark 1.2 below on the interrelation between the two proofs). In addition, we study several variants of the problem with diverse restrictions imposed on the twins. For instance, if we restrict attention to twins avoiding a fixed permutation $τ$, then the corresponding extremal function equals $Θ(\sqrt{n})$, provided that $τ$ is not monotone. In case of block twins (each twin occupies a segment) we prove that it is $(1+o(1))\frac{\log n}{\log\log n}$, while for random permutations it is twice as large. For twins that jointly occupy a segment (tight twins), we prove that for every $n$ there are permutations avoiding them on all segments of length greater than $24$.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Minimizing the number of 5-cycles in graphs with given edge-density

Motivated by the work of Razborov about the minimal density of triangles in graphs we study the minimal density of the 5-cycle $C_5$. We show that every graph of order $n$ and size $\left( 1-\frac{1}{k}\right)\binom{n}{2}$, where $k\ge 3$ is an integer, contains at least \[ \left( \frac{1}{10} -\frac{1}{2k} + \frac{1}{k^2} - \frac{1}{k^3} + \frac{2}{5 k^4} \right)n^5 +o(n^5) \] copies of $C_5$. This bound is optimal, since a matching upper bound is given by the balanced complete $k$-partite graph. The proof is based on the flag algebras framework. We also provide a stability result. An SDP solver is not necessary to verify our proofs.

0 citations0 reviewsNo code linkedOpen access
preprint2019arXiv

Powers of Hamiltonian cycles in randomly augmented graphs

We study 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. It follows from the theorems of Dirac and of Komlós, Sarközy, and Szemerédi that for every $k\geq 1$ and sufficiently large $n$ already the minimum degree $δ(G)\ge\tfrac{k}{k+1}n$ for an $n$-vertex graph $G$ alone suffices to ensure the existence of a $k$-th power of a Hamiltonian cycle. Here we show that under essentially the same degree assumption the addition of just $O(n)$ random edges ensures the presence of the $(k+1)$-st power of a Hamiltonian cycle with probability close to one.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On some multicolour Ramsey properties of random graphs

The size-Ramsey number $\hat{R}(F)$ of a graph $F$ is the smallest integer $m$ such that there exists a graph $G$ on $m$ edges with the property that any colouring of the edges of $G$ with two colours yields a monochromatic copy of $F$. In this paper, first we focus on the size-Ramsey number of a path $P_n$ on $n$ vertices. In particular, we show that $5n/2-15/2 \le \hat{R}(P_n) \le 74n$ for $n$ sufficiently large. (The upper bound uses expansion properties of random $d$-regular graphs.) This improves the previous lower bound, $\hat{R}(P_n) \ge (1+\sqrt{2})n-O(1)$, due to Bollobás, and the upper bound, $\hat{R}(P_n) \le 91n$, due to Letzter. Next we study long monochromatic paths in edge-coloured random graph $G(n,p)$ with $pn \to \infty$. Let $α> 0$ be an arbitrarily small constant. Recently, Letzter showed that a.a.s.\ any $2$-edge colouring of $G(n,p)$ yields a monochromatic path of length $(2/3-α)n$, which is optimal. Extending this result, we show that a.a.s.\ any $3$-edge colouring of $G(n,p)$ yields a monochromatic path of length $(1/2-α)n$, which is also optimal. In general, we prove that for $r\ge 4$ a.a.s.\ any $r$-edge colouring of $G(n,p)$ yields a monochromatic path of length $(1/r-α)n$. We also consider a related problem and show that for any $r \ge 2$, a.a.s.\ any $r$-edge colouring of $G(n,p)$ yields a monochromatic connected subgraph on $(1/(r-1)-α)n$ vertices, which is also tight.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

On the number of alternating paths in bipartite complete graphs

Let $C \subseteq [r]^m$ be a code such that any two words of $C$ have Hamming distance at least $t$. It is not difficult to see that determining a code $C$ with the maximum number of words is equivalent to finding the largest $n$ such that there is an $r$-edge-coloring of $K_{m, n}$ with the property that any pair of vertices in the class of size $n$ has at least $t$ alternating paths (with adjacent edges having different colors) of length $2$. In this paper we consider a more general problem from a slightly different direction. We are interested in finding maximum $t$ such that there is an $r$-edge-coloring of $K_{m,n}$ such that any pair of vertices in class of size $n$ is connected by $t$ internally disjoint and alternating paths of length $2k$. We also study a related problem in which we drop the assumption that paths are internally disjoint. Finally, we introduce a new concept, which we call alternating connectivity. Our proofs make use of random colorings combined with some integer programs.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Size-Ramsey numbers of cycles versus a path

The size-Ramsey number $\hat{R}(\mathcal{F},H)$ of a family of graphs $\mathcal{F}$ and a graph $H$ is the smallest integer $m$ such that there exists a graph $G$ on $m$ edges with the property that any colouring of the edges of $G$ with two colours, say, red and blue, yields a red copy of a graph from $\mathcal{F}$ or a blue copy of $H$. In this paper we first focus on $\mathcal{F} = \mathcal{C}_{\le cn}$, where $\mathcal{C}_{\le cn}$ is the family of cycles of length at most $cn$, and $H = P_n$. In particular, we show that $2.00365 n \le \hat{R}(\mathcal{C}_{\le n},P_n) \le 31n$. Using similar techniques, we also managed to analyze $\hat{R}(C_n,P_n)$, which was investigated before but only using the regularity method.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Ramsey-Turán number with small $s$-independence number

Let $s$ be an integer, $f=f(n)$ a function, and $H$ a graph. Define the Ramsey-Turán number $RT_s(n,H, f)$ as the maximum number of edges in an $H$-free graph $G$ of order $n$ with $α_s(G) < f$, where $α_s(G)$ is the maximum number of vertices in a $K_s$-free induced subgraph of $G$. The Ramsey-Turán number attracted a considerable amount of attention and has been mainly studied for $f$ not too much smaller than $n$. In this paper we consider $RT_s(n,K_t, n^δ)$ for fixed $δ<1$. We show that for an arbitrarily small $\varepsilon>0$ and $1/2<δ< 1$, $RT_s(n,K_{s+1}, n^δ) = Ω(n^{1+δ-\varepsilon})$ for all sufficiently large $s$. This is nearly optimal, since a trivial upper bound yields $RT_s(n,K_{s+1}, n^δ) = O(n^{1+δ})$. Furthermore, the range of $δ$ is as large as possible. We also consider more general cases and find bounds on $RT_s(n,K_{s+r},n^δ)$ for fixed $r\ge2$. Finally, we discuss a phase transition of $RT_s(n, K_{2s+1}, f)$ extending some recent result of Balogh, Hu and Simonovits.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the size-Ramsey number of hypergraphs

The size-Ramsey number of a graph $G$ is the minimum number of edges in a graph $H$ such that every 2-edge-coloring of $H$ yields a monochromatic copy of $G$. Size-Ramsey numbers of graphs have been studied for almost 40 years with particular focus on the case of trees and bounded degree graphs. We initiate the study of size-Ramsey numbers for $k$-uniform hypergraphs. Analogous to the graph case, we consider the size-Ramsey number of cliques, paths, trees, and bounded degree hypergraphs. Our results suggest that size-Ramsey numbers for hypergraphs are extremely difficult to determine, and many open problems remain.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

The Total Acquisition Number of Random Graphs

Let $G$ be a graph in which each vertex initially has weight 1. In each step, the weight from a vertex $u$ can be moved to a neighbouring vertex $v$, provided that the weight on $v$ is at least as large as the weight on $u$. The total acquisition number of $G$, denoted by $a_t(G)$, is the minimum possible size of the set of vertices with positive weight at the end of the process. LeSaulnier, Prince, Wenger, West, and Worah asked for the minimum value of $p=p(n)$ such that $a_t(\mathcal{G}(n,p)) = 1$ with high probability, where $\mathcal{G}(n,p)$ is a binomial random graph. We show that $p = \frac{\log_2 n}{n} \approx 1.4427 \ \frac{\log n}{n}$ is a sharp threshold for this property. We also show that almost all trees $T$ satisfy $a_t(T) = Θ(n)$, confirming a conjecture of West.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Weak and strong versions of the 1-2-3 conjecture for uniform hypergraphs

Given an $r$-uniform hypergraph $H=(V,E)$ and a weight function $ω:E\to\{1,\dots,w\}$, a coloring of vertices of $H$, induced by $ω$, is defined by $c(v) = \sum_{e\ni v} w(e)$ for all $v\in V$. If there exists such a coloring that is strong (that means in each edge no color appears more than once), then we say that $H$ is strongly $w$-weighted. Similarly, if the coloring is weak (that means there is no monochromatic edge), then we say that $H$ is weakly $w$-weighted. In this paper, we show that almost all 3 or 4-uniform hypergraphs are strongly 2-weighted (but not 1-weighted) and almost all $5$-uniform hypergraphs are either 1 or 2 strongly weighted (with a nontrivial distribution). Furthermore, for $r\ge 6$ we show that almost all $r$-uniform hypergraphs are strongly 1-weighted. We complement these results by showing that almost all 3-uniform hypergraphs are weakly 2-weighted but not 1-weighted and for $r\ge 4$ almost all $r$-uniform hypergraphs are weakly 1-weighted. These results extend a previous work of Addario-Berry, Dalal and Reed for graphs. We also prove general lower bounds and show that there are $r$-uniform hypergraphs which are not strongly $(r^2-r)$-weighted and not weakly 2-weighted. Finally, we show that determining whether a particular uniform hypergraph is strongly 2-weighted is NP-complete.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Acquaintance time of random graphs near connectivity threshold

Benjamini, Shinkar, and Tsur stated the following conjecture on the acquaintance time: asymptotically almost surely $AC(G) \le p^{-1} \log^{O(1)} n$ for a random graph $G \in G(n,p)$, provided that $G$ is connected. Recently, Kinnersley, Mitsche, and the second author made a major step towards this conjecture by showing that asymptotically almost surely $AC(G) = O(\log n / p)$, provided that $G$ has a Hamiltonian cycle. In this paper, we finish the task by showing that the conjecture holds in the strongest possible sense, that is, it holds right at the time the random graph process creates a connected graph. Moreover, we generalize and investigate the problem for random hypergraphs.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Rainbow Connection of Random Regular Graphs

An edge colored graph $G$ is rainbow edge connected if any two vertices are connected by a path whose edges have distinct colors. The rainbow connection of a connected graph $G$, denoted by $rc(G)$, is the smallest number of colors that are needed in order to make $G$ rainbow connected. In this work we study the rainbow connection of the random $r$-regular graph $G=G(n,r)$ of order $n$, where $r\ge 4$ is a constant. We prove that with probability tending to one as $n$ goes to infinity the rainbow connection of $G$ satisfies $rc(G)=O(\log n)$, which is best possible up to a hidden constant.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Maker-Breaker games on random geometric graphs

In a Maker-Breaker game on a graph $G$, Breaker and Maker alternately claim edges of $G$. Maker wins if, after all edges have been claimed, the graph induced by his edges has some desired property. We consider four Maker-Breaker games played on random geometric graphs. For each of our four games we show that if we add edges between $n$ points chosen uniformly at random in the unit square by order of increasing edge-length then, with probability tending to one as $n\to\infty$, the graph becomes Maker-win the very moment it satisfies a simple necessary condition. In particular, with high probability, Maker wins the connectivity game as soon as the minimum degree is at least two; Maker wins the Hamilton cycle game as soon as the minimum degree is at least four; Maker wins the perfect matching game as soon as the minimum degree is at least two and every edge has at least three neighbouring vertices; and Maker wins the $H$-game as soon as there is a subgraph from a finite list of "minimal graphs". These results also allow us to give precise expressions for the limiting probability that $G(n,r)$ is Maker-win in each case, where $G(n,r)$ is the graph on $n$ points chosen uniformly at random on the unit square with an edge between two points if and only if their distance is at most $r$.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On generalized Ramsey numbers for 3-uniform hypergraphs

The well-known Ramsey number $r(t,u)$ is the smallest integer $n$ such that every $K_t$-free graph of order $n$ contains an independent set of size $u$. In other words, it contains a subset of $u$ vertices with no $K_2$. Erd{\H o}s and Rogers introduced a more general problem replacing $K_2$ by $K_s$ for $2\le s<t$. Extending the problem of determining Ramsey numbers they defined the numbers $$ f_{s,t}(n)=\min \big{\{} \max \{|W| : W\subseteq V(G) \text{and} G[W] \text{contains no} K_s\}\big{\}}, $$ where the minimum is taken over all $K_t$-free graphs $G$ of order $n$. In this note, we study an analogous function $f_{s,t}^{(3)}(n)$ for 3-uniform hypergraphs. In particular, we show that there are constants $c_1$ and $c_2$ depending only on $s$ such that $$ c_1(\log n)^{1/4} \left(\frac{\log\log n}{\log\log\log n}\right)^{1/2} < f_{s, s+1}^{(3)}(n) < c_2 \log n. $$

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

On generalized Ramsey numbers of Erdős and Rogers

Extending the concept of Ramsey numbers, Erd{\H o}s and Rogers introduced the following function. For given integers $2\le s<t$ let $$ f_{s,t}(n)=\min \{\max \{|W| : W\subseteq V(G) {and} G[W] {contains no} K_s\} \}, $$ where the minimum is taken over all $K_t$-free graphs $G$ of order $n$. In this paper, we show that for every $s\ge 3$ there exist constants $c_1=c_1(s)$ and $c_2=c_2(s)$ such that $f_{s,s+1}(n) \le c_1 (\log n)^{c_2} \sqrt{n}$. This result is best possible up to a polylogarithmic factor. We also show for all $t-2 \geq s \geq 4$, there exists a constant $c_3$ such that $f_{s,t}(n) \le c_3 \sqrt{n}$. In doing so, we partially answer a question of Erdős by showing that $\lim_{n\to \infty} \frac{f_{s+1,s+2}(n)}{f_{s,s+2}(n)}=\infty$ for any $s\ge 4$.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

On Minimum Saturated Matrices

Motivated by the work of Anstee, Griggs, and Sali on forbidden submatrices and the extremal sat-function for graphs, we introduce sat-type problems for matrices. Let F be a family of k-row matrices. A matrix M is called F-admissible if M contains no submatrix G\in F (as a row and column permutation of G). A matrix M without repeated columns is F-saturated if M is F-admissible but the addition of any column not present in M violates this property. In this paper we consider the function sat(n,F) which is the minimum number of columns of an F-saturated matrix with n rows. We establish the estimate sat(n,F)=O(n^{k-1}) for any family F of k-row matrices and also compute the sat-function for a few small forbidden matrices.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

The t-tone chromatic number of random graphs

A proper 2-tone $k$-coloring of a graph is a labeling of the vertices with elements from $\binom{[k]}{2}$ such that adjacent vertices receive disjoint labels and vertices distance 2 apart receive distinct labels. The 2-tone chromatic number of a graph $G$, denoted $τ_2(G)$ is the smallest $k$ such that $G$ admits a proper 2-tone $k$ coloring. In this paper, we prove that w.h.p. for $p\ge Cn^{-1/4}\ln^{9/4}n$, $τ_2(G_{n,p})=(2+o(1))χ(G_{n,p})$ where $χ$ represents the ordinary chromatic number. For sparse random graphs with $p=c/n$, $c$ constant, we prove that $τ_2(G_{n,p}) = \lceil{{\sqrt{8Δ+1} +5}/{2}}\rceil$ where $Δ$ represents the maximum degree. For the more general concept of $t$-tone coloring, we achieve similar results.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Cops and Robbers on Geometric Graphs

Cops and robbers is a turn-based pursuit game played on a graph $G$. One robber is pursued by a set of cops. In each round, these agents move between vertices along the edges of the graph. The cop number $c(G)$ denotes the minimum number of cops required to catch the robber in finite time. We study the cop number of geometric graphs. For points $x_1, ..., x_n \in \R^2$, and $r \in \R^+$, the vertex set of the geometric graph $G(x_1, ..., x_n; r)$ is the graph on these $n$ points, with $x_i, x_j$ adjacent when $ \norm{x_i -x_j} \leq r$. We prove that $c(G) \leq 9$ for any connected geometric graph $G$ in $R^2$ and we give an example of a connected geometric graph with $c(G) = 3$. We improve on our upper bound for random geometric graphs that are sufficiently dense. Let $G(n,r)$ denote the probability space of geometric graphs with $n$ vertices chosen uniformly and independently from $[0,1]^2$. For $G \in G(n,r)$, we show that with high probability (whp), if $r \geq K_1 (\log n/n)^{1/4}$, then $c(G) \leq 2$, and if $r \geq K_2(\log n/n)^{1/5}$, then $c(G) = 1$ where $K_1, K_2 > 0$ are absolute constants. Finally, we provide a lower bound near the connectivity regime of $G(n,r)$: if $r \leq K_3 \log n / \sqrt{n} $ then $c(G) > 1$ whp, where $K_3 > 0$ is an absolute constant.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Loose Hamilton Cycles in Random Uniform Hypergraphs

In the random hypergraph $H_{n,p;k}$ each possible $k$-tuple appears independently with probability $p$. A loose Hamilton cycle is a cycle in which every pair of adjacent edges intersects in a single vertex. We prove that if $p n^{k-1}/\log n$ tends to infinity with $n$ then $$\lim_{\substack{n\to \infty 2(k-1) |n}}\Pr(H_{n,p;k}\ contains\ a\ loose\ Hamilton\ cycle)=1.$$ This is asymptotically best possible.

0 citations0 reviewsNo code linkedOpen access