Source author record

Gholamreza Omidi

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

12works

1topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2016arXiv

Decompositions of complete uniform multi-hypergraphs into Berge paths and cycles of arbitrary lengths

In 1981, Alspach conjectured that the complete graph $K_{n}$ could be decomposed into cycles of arbitrary lengths, provided that the obvious necessary conditions would hold. This conjecture was proved completely by Bryant, Horsley and Pettersson in 2014. Moreover, in 1983, Tarsi conjectured that the obvious necessary conditions for packing pairwise edge-disjoint paths of arbitrary lengths in the complete multigraphs were also sufficient. The conjecture was confirmed by Bryant in 2010. In this paper, we investigate an analogous problem as the decomposition of the complete uniform multi-hypergraph $μK_{n}^{(k)}$ into Berge cycles and Berge paths of arbitrary given lengths. We show that for every integer $μ\geq 1$ , $n\geq 108$ and $3\leq k<n$ , $μK_{n}^{(k)}$ can be decomposed into Berge cycles and Berge paths of arbitrary lengths, provided that the obvious necessary conditions hold, thereby generalizing a result by Kühn and Osthus on the decomposition of $K_{n}^{(k)}$ into Hamilton Berge cycles. Furthermore, we obtain the necessary and sufficient conditions for packing the cycles of arbitrary lengths in the complete multigraphs.

preprint2016arXiv

Ramsey numbers of uniform loose paths and cycles

Recently, determining the Ramsey numbers of loose paths and cycles in uniform hypergraphs has received considerable attention. It has been shown that the $2$ -color Ramsey number of a $k$ -uniform loose cycle $\mathcal{C}^k_n$ , $R(\mathcal{C}^k_n,\mathcal{C}^k_n)$ , is asymptotically $\frac{1}{2}(2k-1)n$ . Here we conjecture that for any $n\geq m\geq 3$ and $k\geq 3,$ $R(\mathcal{P}^k_n,\mathcal{P}^k_m)=R(\mathcal{P}^k_n,\mathcal{C}^k_m)=R(\mathcal{C}^k_n,\mathcal{C}^k_m)+1=(k-1)n+\lfloor\frac{m+1}{2}\rfloor.$ Recently the case $k=3$ is proved by the authors. In this paper, first we show that this conjecture is true for $k=3$ with a much shorter proof. Then, we show that for fixed $m\geq 3$ and $k\geq 4$ the conjecture is equivalent to (only) the last equality for any $2m\geq n\geq m\geq 3$ . Consequently, the proof for $m=3$ follows.

preprint2016arXiv

Size Ramsey numbers of stars versus cliques

The size Ramsey number $\hat{r}(G,H)$ of two graphs $G$ and $H$ is the smallest integer $m$ such that there exists a graph $F$ on $m$ edges with the property that every red-blue colouring of the edges of $F$ , yields a red copy of $G$ or a blue copy of $H$ . In $1981$ , Erdős observed that $\hat{r}(K_{1,k},K_{3})\leq \binom{2k+1}{2}-\binom{k}{2}$ and he conjectured that the corresponding upper bound on $\hat{r}(K_{1,k},K_{3})$ is sharp. In $1983$ , Faudree and Sheehan extended this conjecture as follows: \hat{r}(K_{1,k},K_{n})=\left \{ {lr} \binom{k(n-1)+1}{2}-\binom{k}{2} & ~k\geq n~ \text{or}~ k~ \text{odd}. \binom{k(n-1)+1}{2}-k(n-1)/2 & \text{otherwise}. \right. They proved the case $k=2$ . In $2001$ , Pikhurko showed that this conjecture is not true for $n=3$ and $k\geq 5$ , disproving the mentioned conjecture of Erdős. Here we prove Faudree and Sheehan's conjecture for a given $k\geq 2$ and $n\geq k^{3}+2k^{2}+2k$ .

preprint2015arXiv

Diagonal Ramsey numbers of loose cycles in uniform hypergraphs

A $k$ -uniform loose cycle $\mathcal{C}_n^k$ is a hypergraph with vertex set $\{v_1,v_2,\ldots,v_{n(k-1)}\}$ and with the set of $n$ edges $e_i=\{v_{(i-1)(k-1)+1},v_{(i-1)(k-1)+2},\ldots,v_{(i-1)(k-1)+k}\}$ , $1\leq i\leq n$ , where we use mod $n(k-1)$ arithmetic. The Ramsey number $R(\mathcal{C}^k_n,\mathcal{C}^k_n)$ is asymptotically $\frac{1}{2}(2k-1)n$ as has been proved by Gyárfás, Sárközy and Szemerédi. In this paper, we investigate to determining the exact value of diagonal Ramsey number of $\mathcal{C}^k_n$ and we show that for $n\geq 2$ and $k\geq 8$ $R(\mathcal{C}^k_n,\mathcal{C}^k_n)=(k-1)n+\lfloor\frac{n-1}{2}\rfloor.$

preprint2013arXiv

Strongly walk-regular graphs

We study a generalization of strongly regular graphs. We call a graph strongly walk-regular if there is an $\ell >1$ such that the number of walks of length $\ell$ from a vertex to another vertex depends only on whether the two vertices are the same, adjacent, or not adjacent. We will show that a strongly walk-regular graph must be an empty graph, a complete graph, a strongly regular graph, a disjoint union of complete bipartite graphs of the same size and isolated vertices, or a regular graph with four eigenvalues. Graphs from the first three families in this list are indeed strongly $\ell$ -walk-regular for all $\ell$ , whereas the graphs from the fourth family are $\ell$ -walk-regular for every odd $\ell$ . The case of regular graphs with four eigenvalues is the most interesting (and complicated) one. Such graphs cannot be strongly $\ell$ -walk-regular for even $\ell$ . We will characterize the case that regular four-eigenvalue graphs are strongly $\ell$ -walk-regular for every odd $\ell$ , in terms of the eigenvalues. There are several examples of infinite families of such graphs. We will show that every other regular four-eigenvalue graph can be strongly $\ell$ -walk-regular for at most one $\ell$ . There are several examples of infinite families of such graphs that are strongly 3-walk-regular. It however remains open whether there are any graphs that are strongly $\ell$ -walk-regular for only one particular $\ell$ different from 3.

preprint2012arXiv

A generalization of Ramsey theory for stars and one matching

A recent question in generalized Ramsey theory is that for fixed positive integers $s\leq t$ , at least how many vertices can be covered by the vertices of no more than $s$ monochromatic members of the family $\cal F$ in every edge coloring of $K_n$ with $t$ colors. This is related to { $d$ -chromatic Ramsey numbers} introduced by Chung and Liu. In this paper, we first compute these numbers for stars generalizing the well-known result of Burr and Roberts. Then we extend a result of Cockayne and Lorimer to compute $d$ -chromatic Ramsey numbers for stars and one matching.

preprint2012arXiv

Around a conjecture of ErdH{o}s on graph Ramsey numbers

For given graphs G1 and G2 the Ramsey number R(G1,G2), is the smallest positive integer n such that each blue-red edge coloring of the complete graph Kn contains a blue copy of G1 or a red copy of G2. In 1983, Erdos conjectured that there is an absolute constant c such that R(G) = R(G,G) < 2c p m for any graph G with m edges and no isolated vertices. Recently this conjecture was proved by B. Sudakov. In this note, using the Sudakovs ideas we give an extension of his result and some interesting corollaries.

preprint2012arXiv

Graphs whose normalized Laplacian has three eigenvalues

We give a combinatorial characterization of graphs whose normalized Laplacian has three distinct eigenvalues. Strongly regular graphs and complete bipartite graphs are examples of such graphs, but we also construct more exotic families of examples from conference graphs, projective planes, and certain quasi-symmetric designs.

preprint2012arXiv

On three-color Ramsey number of paths

Let $G_1, G_2, ..., G_t$ be graphs. The multicolor Ramsey number $R(G_1, G_2, ..., G_t)$ is the smallest positive integer $n$ such that if the edges of complete graph $K_n$ are partitioned into $t$ disjoint color classes giving $t$ graphs $H_1,H_2,...,H_t$ , then at least one $H_i$ has a subgraph isomorphic to $G_i$ . In this paper, we prove that if $(n,m)\neq (3,3), (3,4)$ and $m\geq n$ , then $R(P_3,P_n,P_m)=R(P_n,P_m)=m+\lfloor \frac{n}{2}\rfloor-1$ . Consequently $R(P_3,mK_2,nK_2)=2m+n-1$ for $m\geq n\geq 3$ .

preprint2012arXiv

Ramsey numbers of 3-uniform loose paths and loose cycles

Haxell et. al. [%P. Haxell, T. Luczak, Y. Peng, V. Rödl, A. %Ruciński, M. Simonovits, J. Skokan, The Ramsey number for hypergraph cycles I, J. Combin. Theory, Ser. A, 113 (2006), 67-83] proved that the 2-color Ramsey number of 3-uniform loose cycles on $2n$ vertices is asymptotically $\frac{5n}{2}$ . Their proof is based on the method of Regularity Lemma. Here, without using this method, we generalize their result by determining the exact values of 2-color Ramsey numbers involving loose paths and cycles in 3-uniform hypergraphs. More precisely, we prove that for every $n\geq m\geq 3$ , $R(\mathcal{P}^3_n,\mathcal{P}^3_m)=R(\mathcal{P}^3_n,\mathcal{C}^3_m)=R(\mathcal{C}^3_n,\mathcal{C}^3_m)+1=2n+\lfloor\frac{m+1}{2}\rfloor$ and for $n>m\geq3$ , $R(\mathcal{P}^3_m,\mathcal{C}^3_n)=2n+\lfloor\frac{m-1}{2}\rfloor$ . These give a positive answer to a question of Gyárfás and Raeisi [The Ramsey number of loose triangles and quadrangles in hypergraphs, Electron. J. Combin. 19 (2012), #R30].

preprint2012arXiv

The Ramsey number of loose paths in 3-uniform hypergraphs

Recently, asymptotic values of 2-color Ramsey numbers for loose cycles and also loose paths were determined. Here we determine the 2-color Ramsey number of 3-uniform loose paths when one of the paths is significantly larger than the other: for every $n\geq \Big\lfloor\frac{5m}{4}\Big\rfloor$ , we show that $R(\mathcal{P}^3_n,\mathcal{P}^3_m)=2n+\Big\lfloor\frac{m+1}{2}\Big\rfloor.$

preprint2011arXiv

On edge-group choosability of graphs

In this paper, we study the concept of edge-group choosability of graphs. We say that G is edge k-group choosable if its line graph is k-group choosable. An edge-group choosability version of Vizing conjecture is given. The evidence of our claim are graphs with maximum degree less than 4, planar graphs with maximum degree at least 11, planar graphs without small cycles, outerplanar graphs and near-outerplanar graphs.

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.

Gholamreza Omidi

Research overview

Is this your work?

12 publications

Decompositions of complete uniform multi-hypergraphs into Berge paths and cycles of arbitrary lengths

Ramsey numbers of uniform loose paths and cycles

Size Ramsey numbers of stars versus cliques

Diagonal Ramsey numbers of loose cycles in uniform hypergraphs

Strongly walk-regular graphs

A generalization of Ramsey theory for stars and one matching

Around a conjecture of ErdH{o}s on graph Ramsey numbers

Graphs whose normalized Laplacian has three eigenvalues

On three-color Ramsey number of paths

Ramsey numbers of 3-uniform loose paths and loose cycles

The Ramsey number of loose paths in 3-uniform hypergraphs

On edge-group choosability of graphs

See the researcher in context

Building this map preview